有向无环图关键路径

《有向无环图关键路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、有向无环图的关键路径.txt51自信是永不枯竭的源泉，自信是奔腾不息的波涛，自信是急流奋进的渠道，自信是真正的成功之母。#include#include#includeusingnamespacestd;#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针intinfo;//弧上的信息//stringinfo;//该弧相关信息}Ar

2、cNode;typedefstructVNode{intdata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;//存储图intvenum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;intInDegree[MAX_VERTEX_NUM]={0};//用于拓扑排序intCreateUG(ALGraph&G){cout<<"请输入图

3、中顶点个数和边数:";cin>>G.venum>>G.arcnum;inti;for(i=0;i>v1>>v2;ArcNode*current=G.vertices[v1-1].firstarc;ArcNode*p=G.vertices[v1-1].firstarc;if(curr

4、ent==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=cur

5、rent;}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;}c

6、urrent=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

7、t<<"请输入你要加入的边的信息:";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){G.vertices[v1-1].firstarc=newArcNode;G.vertices[v1-1].firstarc->adjvex=v2-1;G.vertices[v1-1].firstarc-

8、>nextarc=NULL;G.vertices[v1-1].firstarc->info=info;}else{while(current!=NULL){p=current;current=current->nextarc;}current=newArcNode;curre