求关键路径（包含邻接表的建立、拓扑排序）

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int adjvex; //邻接点域
int info; //边上的信息
struct node *next;//指向下一个邻接点（或边）的指针域
}edgenode;

typedef struct vnode //顶点的表结点
{
int indegree; //存放顶点的入度
int vertex; // 顶点域
edgenode *firstedge;//边表头的指针
}vertexnode;

vertexnode adjlist[100];//顶点节点向量

void creatalgraph(int n,int e)//建立有向图的邻接表存储
{
int i,j,k,info;

edgenode *s;

for(i=0;i<n;i++)//建立n个顶点的定点表
{
// scanf("%c",&(adjlist[i].vertex));//录入顶点信息
adjlist[i].firstedge=NULL;//顶点的边表头指针设为空
adjlist[i].indegree=0;
}

for(k=0;k<e;k++) //建立边表
{
scanf("%d%d%d",&i,&j,&info);//录入有序偶对《vi,vj>及信息info
adjlist[j].indegree++;
s=(edgenode* )malloc(sizeof(edgenode));

s->adjvex=j;
s->info=info;
s->next=adjlist[i].firstedge;

adjlist[i].firstedge=s;

}

for(i=0;i<n;i++)
{
printf("adjlist[%d].indegree==%d ",i,adjlist[i].indegree);
s=adjlist[i].firstedge;
while(s)
{
printf("%d ",s->adjvex);
s=s->next;
}
printf("\n");
}
for(i=0;i<n;i++)
{
printf("%d ",i);
s=adjlist[i].firstedge;
while(s!=NULL)
{
printf("j==%d info==%d ",s->adjvex,s->info);
s=s->next;
}
printf("\n\n");
}
printf("\n");
}

int topsort(int tsort[],int n)
{//图用邻接表存储，顶点节点带入度域，求其拓扑序列，并存入tsort向量
edgenode *p;
int q[100],head,tail;
int m=0,i,j,k; //m为计数器，记录已输出得顶点数目

head=0;//初始化队列
tail=-1;

for(i=0;i<n;i++)//依次将入度为0的顶点入队
if(adjlist[i].indegree==0)
{
tail++;
q[tail]=i;
}

while(head<=tail)
{
j=q[head];//出队
head++;
tsort[m]=j; //点j进入拓扑序列中
m++;

p=adjlist[j].firstedge;
while(p)
{
k=p->adjvex;
adjlist[k].indegree--;
if(adjlist[k].indegree==0)//进队
{
tail++;
q[tail]=k;
}
p=p->next;
}
}
if(m<n)
{
printf("网络中有回路");
return 0;
}
else
{ for(i=0;i<n;i++)
printf("%d ",tsort[i]);
printf("\n");

return 1;
}
}

typedef struct
{
int data[100];
int top;
}stack;

int ve[100]={0},vl[100],e[100],l[100];
stack t;

int vertexelytinme(int n)
{
//t为拓扑序列顶点，s为入度顶点栈
//若图无回路，则用栈t返回图的拓扑序列，否则返回0；
int i,j,k,count;
edgenode *p;
stack s;
s.top=-1;
count=0;

for(i=0;i<n;i++)
if(adjlist[i].indegree==0)//将入度为0 的顶点入栈，
{
s.top++;
s.data[s.top]=i;
}
t.top=-1;

while(s.top!=-1)
{
j=s.data[s.top];
s.top--;
t.top++;
t.data[t.top]=j; //进入拓扑序列
count++; //计数进入拓扑序列的点

for(p=adjlist[j].firstedge;p;p=p->next)
{
k=p->adjvex;
adjlist[k].indegree --;
if(adjlist[k].indegree==0)
{
s.top++;
s.data[s.top]=k;
}

if((ve[j]+(p->info))>ve[k])//求得最大的ve[k]
{
ve[k]=ve[j]+(p->info);
}
}
}
if(count<n)
return 0;
else
{
for(i=0;i<n;i++)
printf("ve[%d]==%d ",i,ve[i]);
printf("\n");

return 1;
}
}

int pivotalpath(int n)//求AOE网的关键活动
{//图为AOE网，用邻接矩阵存储，求出图的各项关键活动

char tag;
int i,j,k,dut,e,l;
edgenode *p;
for(i=0;i<n;i++)
vl[i]=ve[n-1];
while(t.top!=-1)
{
j=t.data[t.top];
t.top--;

for(p=adjlist[j].firstedge;p;p=p->next)
{
k=p->adjvex;
if((vl[k]-(p->info)<vl[j]))//vl[j]取最小的
vl[j]=vl[k]-(p->info);
}
}

for(i=n-1;i>=0;i--)
printf("vl[%d]==%d ",i,vl[i]);
printf("\n\n");

printf("顶点1 顶点2 权值 最早 最迟 是否为关键活动\n");

for(j=0;j<n;j++)//求每个活动的最早和最迟开始时间，同时求出关键活动
{

for(p=adjlist[j].firstedge;p;p=p->next)
{
k=p->adjvex;
dut=p->info;
e=ve[j];
// printf("%d %d ",vl[k],dut);
l=vl[k]-dut;
// printf("e==%d l==%d\n",e,l);

if(e==l)
{
tag='*';//带“*”为关键活动
printf("%d->%d: %d %d %d %c\n",j,k,dut,e,l,tag);
}
}
}
return 1;
}

int main()
{ freopen("1.txt","r",stdin);
int n,e,i;
edgenode *s;
scanf("%d%d",&n,&e);
creatalgraph(n,e);
// topsort(tsort,n);
printf("\n");

vertexelytinme(n);
pivotalpath(n);

return 0;
}