图的算法之关键路径
#include #include #include
#define max 100
#define maxsize 100000
typedef struct arc {
int adjvex;
int weight;
struct arc *nextarc; }arcnode;
typedef struct
{
char vertices[10];
int id;
struct arc *firstarc; }vex;
typedef struct
{
vex vexs[max];
int vexnum,arcnum; }net;
typedef struct
{
int *data;
int top;
int stacksize;
}seqstack1;
typedef struct
{
int *data;
int top;
int stacksize;
}seqstack2;
int initstack1(seqstack1 &s)
{
s.data=(int *)malloc(max * sizeof(int));
s.top=-1;
s.stacksize=max;
return 1;
}
int pushstack1(seqstack1 &s,int x)
{
if(s.top==s.stacksize-1)
return 0;
s.top++;
s.data[s.top]=x;
return 1;
}
int popstack1(seqstack1 &s,int &x)
{
if(s.top==-1)
return 0;
x=s.data[s.top];
s.top--;
return 1;
}
int initstack2(seqstack2 &s) {
s.data=(int *)malloc(max * sizeof(int));
s.top=-1;
s.stacksize=max;
return 1;
}
int pushstack2(seqstack2 &s,int x)
{
if(s.top==s.stacksize-1)
return 0;
s.top++;
s.data[s.top]=x;
return 1;
}
int popstack2(seqstack2 &s,int &x)
{
if(s.top==-1)
return 0;
x=s.data[s.top];
s.top--;
return 1;
}
int locate(net n,char *ch) {
for(int i=0;iadjvex=j;
p->weight=distance;
p->nextarc=n.vexs[i].firstarc;
n.vexs[i].firstarc=p;
}
}
void output(net n)
{
arcnode *p;
int i,w;
for(i=0;iadjvex;
printf("--->%s(%d)",n.vexs[w].vertices,p->weight);
p=p->nextarc;
}
printf("\n");
}
}
void findID(net &n)
{
arcnode *p;
int i,w;
for(i=0;iadjvex;
n.vexs[w].id++;
p=p->nextarc;
}
}
}
void critical_path(net n) {
int ve[max]={0},vl[max]={0};
arcnode *p;
int i,k,j,e,l;
seqstack1 s1; seqstack2 s2;
initstack1(s1); initstack2(s2);
for(i=0;iadjvex; n.vexs[k].id--;
if(n.vexs[k].id==0) pushstack1(s1,k);
if(ve[j]+p->weight>ve[k])
ve[k]=ve[j]+p->weight;
p=p->nextarc;
}
}
i=0;
printf("拓扑序列:\n");
while(i<=s2.top)
{
printf("%s ",n.vexs[s2.data[i]].vertices);
i++;
}
printf("\n");
for(i=0;iadjvex;
if(vl[k]-p->weightweight;
p=p->nextarc;
}
}
printf("关键路径 距离:\n");
for(i=0;iadjvex;
e=ve[i]; l=vl[k]-p->weight;
if(e==l)
printf("<%s %s>: %d\n",n.vexs[i].vertices,n.vexs[k].vertices,p->weight);
p=p->nextarc;
}
}
}
void main()
{
net n;
create(n);
output(n);
findID(n);
critical_path(n); }
本文档为【图的算法之关键路径】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483