有向无环图的关键路径.doc

有向无环图的关键路径.txt51自信是永不枯竭的源泉，自信是奔腾不息的波涛，自信是急流奋进的渠道，自信是真正的成功之母。#include<iostream>
#include<string>
#include<stack>
usingnamespacestd;

#defineMAX_VERTEX_NUM20
typedefstructArcNode{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;//指向下一条弧的指针
intinfo;//弧上的信息
// stringinfo;//该弧相关信息
}ArcNode;
typedefstructVNode{
intdata;//顶点信息
ArcNode*firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct{
AdjListvertices;//存储图
intvenum,arcnum;//图的当前顶点数和弧数
intkind;//图的种类标志
}ALGraph;

intInDegree[MAX_VERTEX_NUM]={0};//用于拓扑排序

intCreateUG(ALGraph&G){
cout<<"请输入图中顶点个数和边数:";
cin>>G.venum>>G.arcnum;
inti;
for(i=0;i<G.venum;i++){
G.vertices[i].data=i+1;
G.vertices[i].firstarc=NULL;
}
for(i=0;i<G.arcnum;i++){
cout<<"请输入你要加入的边的信息:";
intv1,v2;
cin>>v1>>v2;
ArcNode*current=G.vertices[v1-1].firstarc;
ArcNode*p=G.vertices[v1-1].firstarc;
if(current==NULL){
G.vertices[v1-1].firstarc=newArcNode;
G.vertices[v1-1].firstarc->adjvex=v2-1;
G.vertices[v1-1].firstarc->nextarc=NULL;
}
else{
while(current!=NULL){
p=current;
current=current->nextarc;
}
current=newArcNode;
current->adjvex=v2-1;
current->nextarc=NULL;
p->nextarc=current;
}

current=G.vertices[v2-1].firstarc;
p=G.vertices[v2-1].firstarc;
if(current==NULL){
G.vertices[v2-1].firstarc=newArcNode;
G.vertices[v2-1].firstarc->adjvex=v1-1;
G.vertices[v2-1].firstarc->nextarc=NULL;
}
else{
while(current!=NULL){
p=current;
current=current->nextarc;
}
current=newArcNode;
current->adjvex=v1-1;
current->nextarc=NULL;
p->nextarc=current;
}
}
return1;
}

intCreateDG(ALGraph&G){
cout<<"请输入图中顶点个数和边数:";
cin>>G.venum>>G.arcnum;
inti;
for(i=0;i<G.venum;i++){
G.vertices[i].data=i+1;
G.vertices[i].firstarc=NULL;
}
for(i=0;i<G.arcnum;i++){
cout<<"请输入你要加入的边的信息:";
intv1,v2,info;
cin>>v1>>v2>>info;
ArcNode*current=G.vertices[v1-1].firstarc;
ArcNode*p=G.vertices[v1-1].firstarc;
InDegree[v2-1]++;
if(current==NULL){