澳门新葡亰信誉平台游戏aov网关键路径-关键路径算法求完善,AOV网关键路径

by admin on 2020年1月22日

//006.h

关键路径算法求完善,AOV网关键路径
#include “stdafx.h”
#include”malloc.h”
typedef int Status;
typedef int InfoType;
typedef int VertexType;
typedef int SElemType;
#define OK 1
#define ERROR -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
int adjvex;
int weight;//该边所关联的另一顶点的位置
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;

自己初始化邻接表数据有问题 如果还有其他问题也请帮忙改一下 20C
#include”stdio.h”
#include”stdlib.h”
#define MAX_VERTEX_NUM 20
#define InfoType int
#define VertexType char
#define MaxSize 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define SElemType int
#define Status int
#define OVERFLOW -1
typedef struct
{
SElemType base;
SElemType
top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S)
{
S.base = (SElemType)malloc(STACK_INIT_SIZE sizeof(SElemType));
if
exit;
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return 1;
}
Status GetTop(SqStack S, SElemType &e)
{
if (S.base == S.top)return 0;
e = (S.top – 1);
return 1;
}
Status Push(SqStack &S, SElemType e)
{
if (S.top – S.base == 0)
{
S.base = (SElemType
)realloc(S.base, (STACK_INIT_SIZE +
STACKINCREMENT) * sizeof(SElemType));
if exit;
S.top = S.base + S.stacksize;
S.stacksize = STACK_INIT_SIZE + STACKINCREMENT;
}
= e;
return 1;
}
Status Pop(SqStack &S, SElemType &e)
{
if (S.base == S.top) return 0;
e =
–S.top;
return 1;
}
Status StackEmpty(SqStack S)
{
if (S.top – S.base == 0)
return 1;
else
return 0;
}
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
int weight;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertex;
int vexnum, arcnum;
int kind;
}ALGraph;

#include <stdio.h>
#include <stdlib.h>
typedef int Status;
typedef int SElemType;

typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

int indegree[MaxSize];
int ve[MaxSize];//定义事件最早发生 (vertex earliest)
int vl[MaxSize];//定义事件最迟发生 (vertex lastest)
void CreateDGAOV(ALGraph *G)
{
int i, j, k;
ArcNode *e;
printf(“输入顶点和边:n”);
scanf_s(“%d,%d”, &G->vexnum, &G->arcnum);
getchar();
printf(“请初始化顶点n”);
for (i = 0; i < G->vexnum; i++)
{
printf(“输入顶点字符:n”);
scanf_s(“%c”, &G->vertex[i].data);
G->vertex[i].firstarc = NULL;

#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 2
typedef struct {
 SElemType *base;
 SElemType *top;
 int stacksize;
}SqStack;

typedef struct{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

getchar();
}
for (k = 0; k < G->arcnum; k++)
{
printf(“输入边上的顶点序号:n”);
scanf_s(“%d,%d”, &i, &j);
e = (ArcNode)malloc(sizeof;
e->adjvex = j;
e->nextarc = G->vertex[i].firstarc;
G->vertex[i].firstarc = e;
}
}
Status CreateDGAOE(ALGraph
G)
{

Status InitStack(SqStack &S)
{
 if(!(S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType))))
  exit(OVERFLOW);
 S.top=S.base;
 S.stacksize=STACK_INIT_SIZE;
 return OK;
}

Status InitStack(SqStack &S){
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
ifreturn;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}

VNode v1, v2;int i, j, sign1, sign2;int value;printf("创建AOEn");printf("请输入顶点数和边数:");scanf_s("%d,%d", &G->vexnum, &G->arcnum);getchar();printf("请初始化顶点n");for (i = 0; i < G->vexnum; i++){ printf("输入顶点字符:n"); scanf_s("%c", &G->vertex[i].data); G->vertex[i].firstarc = NULL; getchar();}printf("请初始化弧n");printf("输入格式:顶点1 顶点2 权值(表示顶点1邻接到顶点2)nn");for (i = 0; i < G->arcnum; i++){ ArcNode *p, *q; sign1 = -1; sign2 = -1; scanf_s("%c%c%d", &v1.data, &v2.data, &value); getchar(); for (j= 0; j< G->vexnum; j++) { if (v1.data == G->vertex[j].data) sign1 = j; if (v2.data == G->vertex[j].data) sign2 = j; } p = malloc(sizeof; if  exit; p->nextarc = NULL; p->weight = value; p->adjvex = sign2; q = G->vertex[sign1].firstarc; if  G->vertex[sign1].firstarc = p; else { while (q->nextarc != NULL) q = q->nextarc; q->nextarc = p; }}return 1;

Status StackEmpty(SqStack S)
{
 if(S.top==S.base)
  return OK;
 else
  return ERROR;
}

Status Push(SqStack &S,SElemType e){
if(S.top-S.base>=S.stacksize){
S.base=(SElemType
)realloc(S.base,(S.stacksize+STACKINCREMENT)sizeof(SElemType));
ifreturn;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e){
if(S.top==S.base)return ERROR;
e=*–S.top;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.top==S.base)
return OK;
else
return ERROR;
}

}
void FindInDegree(ALGraph G)//计算每个节点的入度;
{
ArcNode *p;
int i, k;
for (i = 0; i < G.vexnum; i++)
indegree[i] = 0;
for (i = 0; i < G.vexnum; i++)
{
p = G.vertex[i].firstarc;
while (p != NULL)
{
k = p->adjvex;
indegree[k]++;
p = p->nextarc;
}
}
}
int TopologicalSort(ALGraph &G)//拓扑排序的实现
{
int i, k, count = 0;
SqStack S;
ArcNode *p;
FindInDegree;
InitStack;
printf(“TopologicalSort:”);
for (i = 0; i < G.vexnum; i++)//将入度为0的顶点的下标号压入顺序栈S
if (!indegree[i])
Push;
while (!StackEmpty//如果栈不为空
{
Pop;//弹出栈顶存储的顶点的下标号
printf(“%3c”, G.vertex[i].data);//输出下标号为i的顶点中的数据;
count++;//每弹出一次,count就加一,全部输出后应该是vexnum的值,可由这个来判断G有没有环;
for (p = G.vertex[i].firstarc; p; p =
p->nextarc)//令p指向顶点的firstarc也就是指向顶点节点后的第一个边结点,等到p指向NULL时循环结束
{
k = p->adjvex;//令k指向p节点的下标号;
if (–indegree[k] == 0)//先将这个节点的入度-1如果=0,那么就将它入栈
Push;
}
}
if (count < G.vexnum)
{
printf(“The directed graph has a loopn”);
return 0;
}
else
return 1;
}
Status TopologicalOrder(ALGraph G, SqStack &T)
{
SqStack S;
ArcNode *p;
int i, x, k, count = 0;

Status Push(SqStack &S,SElemType e)
{
 if(S.top-S.base>=S.stacksize)
 {
  S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
  if(!S.base)
   return OVERFLOW;
  S.top=S.base+S.stacksize;
  S.stacksize+=STACKINCREMENT;
 }
 *S.top=e;
 S.top++;
 return OK;
}

int indegree[20];
void FindInDegree(ALGraph G,int indegree[])
{
int i,j,w,k=0,n=0;
ArcNode *p;
int i;
for(i=0; i for(j=0;j {
for(i=0;i {
p=G.vertices[i].firstarc;
while
{
w=p->adjvex;
if n++;
p=p->nextarc;
}
}
indegree[k++]=n;
printf(“%d”,indegree[k]);
n=0;
}
}
int ve[20],vl[20];
SqStack S;
Status TopologicalOrder(ALGraph G,SqStack &T){
int count,j,k;

FindInDegree;InitStack;for (i = 0; i < G.vexnum; i++)//将时间最早发生初始化 ve[i] = 0;for (i = 0; i < G.vexnum; i++)//将入度为0的顶点入栈;{ if (indegree[i] == 0) Push;}while (!StackEmpty{ Pop; Push;//将弹出来的顶点下标压入栈T count++; for (p = G.vertex[x].firstarc; p; p = p->nextarc)//注意p指向的是边节点 { k = p->adjvex; if (--indegree[k] == 0) { Push; } if (ve[x] + (p->weight) > ve[k])//取最早完成时间里的最大值 { ve[k] = ve[x] + (p->weight); } } if (count < G.vexnum) return 0; else return 1;}

Status Pop(SqStack &S,SElemType e)
{
  if(S.top==S.base)
   return ERROR;
  e=*S.top;
  S.top–;
  return OK;
}

FindInDegree(G,indegree);InitStack;count=0;int i;for(i=0; i<G.vexnum; i++) ve[i] = 0;/*ve[0..G.vexnum-1]=0 ;*/while(!StackEmpty{Pop;Push;++count;ArcNode *p;for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;if(--indegree[k]==0) Push;if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info);} }if(count<G.vexnum) return ERROR;else return OK;}

}
Status CriticalPath(ALGraph G)
{
int i, k, x;
int ee, el;
ArcNode *p;
SqStack T;
InitStack;
TopologicalOrder;
for (i = 0; i < G.vexnum; i++)
vl[i] = ve[G.vexnum – 1];
while (!StackEmpty
{
Pop;
for (p = G.vertex[i].firstarc; p; p = p->nextarc)
{
k = p->adjvex;
if (vl[x] > vl[k] – p->weight)//取最迟时间中最小值
vl[x] = vl[k] – p->weight;
}
}
for (i = 0; i < G.vexnum; i++);
{
for (p = G.vertex[i].firstarc; p; p = p->nextarc)
{
k = p->adjvex;
ee = ve[i];
el = vl[k] – p->weight;
}
printf(“Criticalpath:<%d,%d>length:%dn”, i, k, p->weight);
}
return 1;
}
int main()
{
//ALGraph G;
//CreateDGAOV;
//TopologicalSort;
//printf;
ALGraph N;
CreateDGAOE;
CriticalPath;
return 0;
}

//007.h

SqStack &T;
Status CriticalPath(ALGraph G){
int j; char tag;int k;int dut;
int ee;int el;
ArcNode p;
if(!TopologicalOrder return ERROR;
int i;
for(i=0; iwhile(!StackEmpty
for ,p=G.vertices[j].firstarc; p; p=p->nextarc){
k=p->adjvex; dut=
(p->info);
if (vl[k]-dut }
for(j=0;j for(p=G.vertices[j].firstarc; p; p=p->nextarc){
k=p->adjvex; dut= (p->info);
ee=ve[j]; el=vl[k]-dut;
tag=? ‘
‘:’ ‘;
printf(“%d %d %d %d %d %cn”,j,k,dut,ee,el,tag);
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

}

#include “006.h”
#define MAX_VERTEX_NUM 20
#define NULL 0
#define OK 1
#define ERROR 0

int _tmain(int argc, _TCHAR* argv[])
{
ALGraph G;

#define MAX_NAME 5
typedef int InfoType;
typedef int Status;
typedef int InfoType;
typedef char VertexType[MAX_NAME];//字符串类型

printf(“以下是查找图的关键路径的程序。n”);

int ve[MAX_VERTEX_NUM];//全局变量

TopologicalOrder;

#define MAX_VERTEX_NUM 20
struct ArcNode
{
 int adjvex;
 ArcNode *nextarc;
 InfoType *info;
};//表结点

CriticalPath;
return 0;
}

typedef struct{
 VertexType data;//顶点信息
 ArcNode *firstarc;//第一个结点的地址,指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];//头结点

struct ALGraph
{
 AdjList vertices;
 int vexnum,arcnum;
 int kind;
};

Status LocateVex(ALGraph G,VertexType u)
{
 int i;
 for(i=0;i<G.vexnum;i++)
  if(strcmp(u,G.vertices[i].data)==0)
   return i;
  return -1;
}

Status CreateGraph(ALGraph &G)
{
 int i,j,k;
 int w;
 ArcNode *p;
 VertexType va,vb;
 printf(“请输入图的顶点数、边数:”);
 scanf(“%d,%d”,&G.vexnum,&G.arcnum);
 printf(“请输入%d个顶点的值(<%d个字符):n”,G.vexnum,MAX_NAME);
 for(i=0;i<G.vexnum;i++)//构造顶点向量
 {
  scanf(“%s”,G.vertices[i].data);
  G.vertices[i].firstarc=NULL;
 }
 printf(“请输入每条弧的权值、弧尾和弧头(以空格作为间隔):n”);
 for(k=0;i<G.arcnum;k++)
 {
  scanf(“%d%s%s”,&w,va,vb);
  i=LocateVex(G,va);//弧尾
  j=LocateVex(G,vb);//弧头
  p=(ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex=j;
  p->info=(int*)malloc(sizeof(int));
  *(p->info)=w;
  p->nextarc=G.vertices[i].firstarc;//插在表头
  G.vertices[i].firstarc=p;
 }
 return OK;
}

void Display(ALGraph G)
{
 int i;
 ArcNode *p;
 printf(“有向网:n”);
 printf(“%个顶点:n”,G.vexnum);
 for(i=0;i<G.vexnum;i++)
      printf(“%s”,G.vertices[i].data);
 printf(“n%d条弧:n”,G.arcnum);
 for(i=0;i<G.vexnum;i++)
 {
  p=G.vertices[i].firstarc;
  while(p)
  {
   printf(“%s-%s”,G.vertices[i].data,G.vertices[p->adjvex].data);
   printf(“:%d”,*(p->info));
      p=p->nextarc;
  }
  printf(“n”);
 }
}

void FindInDegree(ALGraph G,int indegree[])
{
   int i;
   ArcNode *p;
   for(i=0;i<G.vexnum;i++)
    indegree[i]=0;
   for(i=0;i<G.vexnum;i++)
   {
    p=G.vertices[i].firstarc;
    while(p)
    {
     indegree[p->adjvex]++;
     p=p->nextarc;
    }
   }
}

 

Status TopologicalOrder(ALGraph G,SqStack &T)
{
 //有向网G采用邻接表存储结构,求各个顶点事件的最早发生时间ve(全局变量).T为拓扑序列顶点栈,
 //S为零入度顶点栈,若G回路,则用栈T返回G的一个拓扑序列,且函数值为OK,否则为ERROR
 int i,j,k,count,indegree[MAX_VERTEX_NUM];
 SqStack S;
 ArcNode *p;
 FindInDegree(G,indegree);
 InitStack(S);
 for(j=0;j<G.vexnum;j++)//建立零入度顶点栈S
  if(indegree[j]==0)
   Push(S,j);//入度为0者进栈
  InitStack(T);//初始化拓扑序列顶点栈
  count=0;//对输出顶点计数
  for(j=0;j<G.vexnum;j++)
   ve[j]=0;
  while(!StackEmpty(S))
  {
   //栈不空
   Pop(S,j);
   Push(T,j);
   ++count;
   for(p=G.vertices[j].firstarc;p;p=p->nextarc)
   {//对j号顶点的每个邻接点的入度减一
    k=p->adjvex;
    if((–indegree[k])==0)
     Push(S,k);
    if(ve[j]+*(p->info)>ve[k])
     ve[k]=ve[j]+*(p->info);
   }
  }
  if(count<G.vexnum)
  {
   printf(“此有向网有回路n”);
   return ERROR;
  }
  else
   return OK;
}

Status CriticalPath(ALGraph G)
{
 //G为有向网,输出G的各项关键活动
 int vl[MAX_VERTEX_NUM];
 SqStack T;
 int i,j,k,ee,el;
 ArcNode *p;
 char dut,tag;
 if(!TopologicalOrder(G,T))//产生有向环
  return ERROR;
 j=ve[0];
 for(i=1;i<G.vexnum;i++)
  if(ve[i]>j)
   j=ve[i];
  for(i=0;i<G.vexnum;i++)//初始化顶点事件的最尺发生时间(最大值)
   vl[i]=j;//完成点的最早发生时间}
       while(!StackEmpty(T))//按拓扑逆序求各顶点的vl值
     for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc)
     {
      k=p->adjvex;
      dut=*(p->info);
      if(vl[k]-dut<vl[j])
       vl[j]=vl[k]-dut;
     }
     printf(“j k dut ee el tagn”);
     for(j=0;j<G.vexnum;++j) //求ee el 和关键活动
      for(p=G.vertices[j].firstarc;p;p=p->nextarc)
      {
       k=p->adjvex;
       dut=*(p->info);
       ee=ve[j];
       el=vl[k]-dut;
       tag=(ee==el)?’*’:’ ‘;
       printf(“%2d%2d%3d%3d%3d
%cn”,j,k,dut,ee,el,tag);//输出关键活动
      }
      printf(“关键活动为:n”);
      for(j=0;j<G.vexnum;++j)
       for(p=G.vertices[j].firstarc;p;p->nextarc)
       {
        k=p->adjvex;
        dut=*(p->info);
        if(ve[j]==vl[k]-dut)
         printf(“%s-%sn”,G.vertices[j].data,G.vertices[k].data);
       }
       return OK;
}

 

 

// 主函数

#include <stdio.h>
#include <stdlib.h>
#include “007.h”

void main()
{
 ALGraph h;
 CreateGraph(h);
 Display(h);
 CriticalPath(h);
}

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图