有向无环图的关键路径

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

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

2、;//该弧相关信息}ArcNode;typedefstructVNode{intdata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;//存储图intvenum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;intInDegree[MAX_VERTEX_NUM]={0};//用于拓扑排序intCreateU

3、G(ALGraph&G){cout<<"请输入图中顶点个数和边数:";cin>>G.venum>>G.arcnum;inti;for(i=0;i>v1>>v2;ArcNode*current=G.vertices[v1-1].firstarc;ArcNode

4、*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->

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

6、e{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

7、ces[i].data=i+1;G.vertices[i].firstarc=NULL;}for(i=0;i>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].f

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