關鍵路徑算法C++實現代碼
#include <dos.h>include <conio.h>
include <stdio.h>
include <stdlib.h>
include <string.h>
define MAX_VERTEX_NUM 30 //圖的最大頂點數
define MAX 30 //棧的最大容量
define INFINITY 30000; //定義最大的最遲發生時間
enum BOOL {False,True}; typedef struct ArcNode { int adjvex; //該弧所指向的頂點的位置 int weight; //該弧所代表的活動的持續時間 struct ArcNode nextarc; //指向下一條弧的指針 } ArcNode; //弧結點 typedef struct { int indegree[MAX_VERTEX_NUM]; //存放各頂點的入度 ArcNode AdjList[MAX_VERTEX_NUM]; //指向第一條依附該頂點的弧的指針 int vexnum,arcnum; //圖的當前頂點和弧數 } Graph; typedef struct //定義堆棧結構 { int elem[MAX]; //棧區 int top; //棧頂指針 } Stack; int ve[MAX_VERTEX_NUM]; //全局變量，存放各頂點的最早發生時間 void CreateGraph ( Graph & ); //生成圖的鄰接表 BOOL CriticalPath ( Graph ); //求圖的關鍵路徑 BOOL TopologicalSort ( Graph,Stack &T ); //進行拓撲排序 void FindInDegree ( Graph& ); //求圖各頂點的入度 void Initial ( Stack & ); //初始化一個堆棧 BOOL Push ( Stack &,int ); //將一個元素入棧 BOOL Pop ( Stack&,int & ); //將一個元素出棧 BOOL Gettop ( Stack,int& ); //得到棧頂元素 BOOL StackEmpty ( Stack ); //判斷堆棧是否為空 void main() { Graph G; //采用鄰接表結構的圖 char j='y'; BOOL temp; textbackground ( 3 ); //設定屏幕顏色 textcolor ( 15 ); clrscr(); //------------------程序解說---------------------------- printf ( "本程序將演示構造圖的關鍵路徑.\n" ); printf ( "首先輸入圖的頂點數和弧數.\n格式：頂點數，弧數；例如:6,8\n" ); printf ( "接著輸入各弧(弧尾,弧頭)和權值.\n格式：弧尾，弧頭，權值；例如:\n1,2,3\n1,3,2\n" ); printf ( "2,5,3\n5,6,1\n2,4,2\n4,6,2\n3,4,4\n3,6,3\n" ); printf ( "程序將會構造該圖并找出其關鍵路徑.\n" ); printf ( "關鍵路徑:\n1->3 2\n3->4 4\n4->5 2\n" ); //------------------------------------------------------ while ( j!='N'&&j!='n' ) { CreateGraph ( G ); //生成鄰接表結構的圖 temp=CriticalPath ( G ); //尋找G的關鍵路徑 if ( temp==False ) printf ( "該圖有回路!\n" ); //若返回為False,表明該圖存在有環路 else printf ( "該圖沒有回路!\n" ); printf ( "關鍵路徑演示完畢，繼續進行嗎?(Y/N)" ); scanf ( " %c",&j ); } }
BOOL CriticalPath ( Graph G ) {//G為有向網，輸出G的各項關鍵活動 int j,dut,k,ee,el; int vl[MAX_VERTEX_NUM]; //存放各頂點的最遲發生時間 Stack T; //堆棧T存放拓撲排序的頂點序列 ArcNodep; Initial ( T ); //初始化堆棧T if ( !TopologicalSort ( G,T ) ) return False; //利用拓撲排序求出各頂點的最早發生時間，并用T返回拓撲序列， //若返回False，表明該網有回路 printf ( "Critical Path:\n" ); Gettop ( T,k ); //k取得拓撲序列的最后一個頂點，即該網的匯點 vl[k]=ve[k]; //匯點的vl=ve for ( j=1; j<=G.vexnum; j++ ) if ( j!=k ) vl[j]=INFINITY; //將其他的頂點的vl置為IFINITY while ( !StackEmpty ( T ) ) //按拓撲逆序求各頂點的vl值 { Pop ( T,j ); for ( p=G.AdjList[j]; p; p=p->nextarc ) { k=p->adjvex; dut=p->weight; if ( vl[k]-dut<vl[j] ) vl[j]=vl[k]-dut; //vl的求法：vl(i)=Min{vl(j)-dut(<i,j>)} <i,j>∈S,i=n-2,...0 } } for ( j=1; j<=G.vexnum; j++ ) //求每條弧的最早開始時間ee和最遲開始時間el for ( p=G.AdjList[j]; p; p=p->nextarc ) { k=p->adjvex; dut=p->weight; ee=ve[j]; el=vl[k]-dut; if ( ee==el ) printf ( "%d->%d%5d\n",j,k,dut ); //若ee=el，則該弧為關鍵活動 } return True; } void CreateGraph ( Graph &G ) {//構造鄰接表結構的圖G int i; int start,end,arcweight; ArcNode s; printf ( "請輸入頂點數和弧數(頂點數，弧數):" ); scanf ( "%d,%d",&G.vexnum,&G.arcnum ); //輸入圖的頂點數和弧數 for ( i=1; i<=G.vexnum; i++ ) G.AdjList[i]=NULL; //初始化指針數組 printf ( "請輸入各弧和權值，格式:弧尾,弧頭,權值\n" ); for ( i=1; i<=G.arcnum; i++ ) { scanf ( "%d,%d,%d",&start,&end,&arcweight ); //輸入弧的起點和終點即該弧所代表的活動的持續時間 s= ( ArcNode * ) malloc ( sizeof ( ArcNode ) ); //生成一個弧結點 s->nextarc=G.AdjList[start]; //插入到鄰接表中 s->adjvex=end; s->weight=arcweight; G.AdjList[start]=s; } }
BOOL TopologicalSort ( Graph G,Stack &T ) {//有向網G采用鄰接表存儲結構，求各頂點事件的最早發生時間ve， //T為拓撲序列頂點棧，S為零入度頂點棧。 //若G無回路，則用棧返回G的一個拓撲序列，且函數返回True,否則返回False int i,k; int count; //計數器 ArcNode p; Stack S; FindInDegree ( G ); //求出圖中各頂點的入度 Initial ( S ); //堆棧初始化，存放入度為零的頂點 for ( i=1; i<=G.vexnum; i++ ) if ( !G.indegree[i] ) Push ( S,i ); //入度為零的頂點入棧 count=0; //對輸出頂點記數 for ( i=1; i<=G.vexnum; i++ ) ve[i]=0; //ve初始化 while ( !StackEmpty ( S ) ) { Pop ( S,i ); //i號頂點出S棧并入T棧，count記數 Push ( T,i ); count++; for ( p=G.AdjList[i]; p; p=p->nextarc ) { k=p->adjvex; //對i號頂點的每個鄰接頂點的入度減一 if ( ! ( --G.indegree[k] ) ) Push ( S,k ); //若入度為零，入棧 if ( ( ve[i]+p->weight ) >ve[k] ) ve[k]=ve[i]+p->weight; //修改k號頂點的最遲發生時間 //ve的求法：ve(j)=Max{ve(i)+dut(<i,j>)} <i,j>∈S,j=1,2,…,n-1 } } if ( count<G.vexnum ) return False; //如輸出頂點數少于圖中頂點數，則該圖有回路 else return True; } void FindInDegree ( Graph &G ) {//求出圖G的各頂點的入度，存放在G.indegree[1..G.vexnum]中 int i; ArcNode p; for ( i=1; i<=G.vexnum; i++ ) G.indegree[i]=0; for ( i=1; i<=G.vexnum; i++ ) { for ( p=G.AdjList[i]; p; p=p->nextarc ) G.indegree[p->adjvex]++; //弧頭頂點的入度加一 } } void Initial ( Stack &S ) { S.top=-1; //棧頂指針初始化為-1 }
BOOL Push ( Stack &S,int ch ) {//將元素ch入棧，成功返回True,失敗返回False if ( S.top>=MAX-1 ) return False;//判斷是否棧滿 else { S.top++; //棧頂指針top加一 S.elem[S.top]=ch; //入棧 return True; } }
BOOL Pop ( Stack &S,int &ch ) {//將棧頂元素出棧,成功返回True，并用ch返回該元素值，失敗返回False if ( S.top<=-1 ) return False;//判斷是否棧空 else { S.top--; //棧頂指針減一 ch=S.elem[S.top+1]; return True; } } BOOL Gettop ( Stack S,int &ch ) {//取得棧頂元素，成功返回True，并用ch返回該元素值，失敗返回False if ( S.top<=-1 ) return False; else { ch=S.elem[S.top];//顯示棧頂元素 return True; } } BOOL StackEmpty ( Stack S ) {//判斷堆棧是否已空，若空返回True,不空返回False if ( S.top<=-1 ) return True; else return False; } </pre>