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

《有向无环图的关键路径.doc》由会员分享，可在线阅读，更多相关《有向无环图的关键路径.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流有向无环图的关键路径.精品文档.有向无环图的关键路径.txt51自信是永不枯竭的源泉，自信是奔腾不息的波涛，自信是急流奋进的渠道，自信是真正的成功之母。#include#include#includeusing namespace std;#define MAX_VERTEX_NUM 20typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针int info; /弧上的信息/string info; /该弧相关信息ArcNode;typ

2、edef struct VNodeint data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; /存储图int venum,arcnum; /图的当前顶点数和弧数int kind; /图的种类标志ALGraph;int InDegreeMAX_VERTEX_NUM=0; /用于拓扑排序int CreateUG(ALGraph& G)coutG.venumG.arcnum;int i;for( i=0; iG.venum; i+)G.ver

3、ticesi.data=i+1;G.verticesi.firstarc=NULL;for( i=0; iG.arcnum; i+)coutv1v2;ArcNode* current=G.verticesv1-1.firstarc;ArcNode* p=G.verticesv1-1.firstarc;if(current=NULL)G.verticesv1-1.firstarc=new ArcNode;G.verticesv1-1.firstarc-adjvex=v2-1;G.verticesv1-1.firstarc-nextarc=NULL;elsewhile(current!=NULL)

4、p=current;current=current-nextarc;current=new ArcNode;current-adjvex=v2-1;current-nextarc=NULL;p-nextarc=current;current=G.verticesv2-1.firstarc;p=G.verticesv2-1.firstarc;if(current=NULL)G.verticesv2-1.firstarc=new ArcNode;G.verticesv2-1.firstarc-adjvex=v1-1;G.verticesv2-1.firstarc-nextarc=NULL;else

5、while(current!=NULL)p=current;current=current-nextarc;current=new ArcNode;current-adjvex=v1-1;current-nextarc=NULL;p-nextarc=current;return 1;int CreateDG(ALGraph& G)coutG.venumG.arcnum;int i;for( i=0; iG.venum; i+)G.verticesi.data=i+1;G.verticesi.firstarc=NULL;for( i=0; iG.arcnum; i+)coutv1v2info;A

6、rcNode* current=G.verticesv1-1.firstarc;ArcNode* p=G.verticesv1-1.firstarc;InDegreev2-1+;if(current=NULL)G.verticesv1-1.firstarc=new ArcNode;G.verticesv1-1.firstarc-adjvex=v2-1;G.verticesv1-1.firstarc-nextarc=NULL;G.verticesv1-1.firstarc-info=info;elsewhile(current!=NULL)p=current;current=current-ne

7、xtarc;current=new ArcNode;current-adjvex=v2-1;current-nextarc=NULL;current-info=info;p-nextarc=current;return 1;int CreateDG1(ALGraph& G)coutG.venumG.arcnum;int i;for( i=0; iG.venum; i+)G.verticesi.data=i+1;G.verticesi.firstarc=NULL;for( i=0; iG.arcnum; i+)coutv1v2;ArcNode* current=G.verticesv2-1.fi

8、rstarc;ArcNode* p=G.verticesv2-1.firstarc;if(current=NULL)G.verticesv2-1.firstarc=new ArcNode;G.verticesv2-1.firstarc-adjvex=v1-1;G.verticesv2-1.firstarc-nextarc=NULL;elsewhile(current!=NULL)p=current;current=current-nextarc;current=new ArcNode;current-adjvex=v1-1;current-nextarc=NULL;p-nextarc=curr

9、ent;return 1;int CreateGraph(ALGraph& G)coutG.kind;switch(G.kind)case 0:return CreateUG(G); /构造无向图case 1:return CreateDG(G); /构造有向图case 2:return CreateDG1(G); /构造逆邻接图default:return 0;int veMAX_VERTEX_NUM=0;bool TopologicalSort(ALGraph &G, stack &T)stack S;int i;for( i=0; inextarc)int w=p-adjvex;InDe

10、greew-;if(InDegreew=0)S.push(w);if(vei+p-info vew)vew=vei+p-info;if(countG.venum)cout有向图中有环存在endl;return false;return true;void CriticalPath(ALGraph &G)int k,dut;stack T;if(!TopologicalSort(G,T)return ;int v1MAX_VERTEX_NUM;for( k=0; knextarc)k=p-adjvex;dut=p-info;if(v1k-dutv1i)v1i=v1k-dut;for(int j=

11、0; jnextarc)k=q-adjvex; dut=q-info;if(vej=v1k-dut)cout关键路径:G.verticesj.data G.verticesk.dataendl;int main()ALGraph G;CreateGraph(G);ArcNode* current1;ArcNode* p;for(int k=0; kG.venum; k+)coutG.verticesk.data ;ArcNode* current1=G.verticesk.firstarc;while(current1!=NULL)coutadjvexnextarc;coutendl;system(pause);CriticalPath(G);system(pause);for(int i=0; inextarc;delete current1;current1=p;return 1;