#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 30 //圖的最大頂點(diǎn)數(shù)
#define MAX 30            //棧的最大容量
#define INFINITY 30000;   //定義最大的最遲發(fā)生時(shí)間
enum BOOL {False,True};
typedef struct ArcNode
{
	int adjvex;              //該弧所指向的頂點(diǎn)的位置
	int weight;              //該弧所代表的活動(dòng)的持續(xù)時(shí)間
	struct ArcNode *nextarc; //指向下一條弧的指針
} ArcNode;      //弧結(jié)點(diǎn)
typedef struct
{
	int indegree[MAX_VERTEX_NUM]; //存放各頂點(diǎn)的入度
	ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一條依附該頂點(diǎn)的弧的指針
	int vexnum,arcnum;                //圖的當(dāng)前頂點(diǎn)和弧數(shù)
} Graph;
typedef struct    //定義堆棧結(jié)構(gòu)
{
	int elem[MAX];   //棧區(qū)
	int top;         //棧頂指針
} Stack;
int ve[MAX_VERTEX_NUM];  //全局變量，存放各頂點(diǎn)的最早發(fā)生時(shí)間
void CreateGraph ( Graph & ); //生成圖的鄰接表
BOOL CriticalPath ( Graph );  //求圖的關(guān)鍵路徑
BOOL TopologicalSort ( Graph,Stack &T );  //進(jìn)行拓?fù)渑判?void FindInDegree ( Graph& ); //求圖各頂點(diǎn)的入度
void Initial ( Stack & );  //初始化一個(gè)堆棧
BOOL Push ( Stack &,int );  //將一個(gè)元素入棧
BOOL Pop ( Stack&,int & );  //將一個(gè)元素出棧
BOOL Gettop ( Stack,int& ); //得到棧頂元素
BOOL StackEmpty ( Stack );  //判斷堆棧是否為空
void main()
{
	Graph G;  //采用鄰接表結(jié)構(gòu)的圖
	char j='y';
	BOOL temp;
	textbackground ( 3 );  //設(shè)定屏幕顏色
	textcolor ( 15 );
	clrscr();
//------------------程序解說----------------------------
	printf ( "本程序?qū)⒀菔緲?gòu)造圖的關(guān)鍵路徑.\n" );
	printf ( "首先輸入圖的頂點(diǎn)數(shù)和弧數(shù).\n格式：頂點(diǎn)數(shù)，弧數(shù)；例如:6,8\n" );
	printf ( "接著輸入各弧(弧尾,弧頭)和權(quán)值.\n格式：弧尾，弧頭，權(quá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 ( "程序?qū)��?huì)構(gòu)造該圖并找出其關(guān)鍵路徑.\n" );
	printf ( "關(guān)鍵路徑:\n1->3  2\n3->4  4\n4->5  2\n" );
//------------------------------------------------------
	while ( j!='N'&&j!='n' )
	{
		CreateGraph ( G );       //生成鄰接表結(jié)構(gòu)的圖
		temp=CriticalPath ( G ); //尋找G的關(guān)鍵路徑
		if ( temp==False ) printf ( "該圖有回路!\n" );
		//若返回為False,表明該圖存在有環(huán)路
		else printf ( "該圖沒有回路!\n" );
		printf ( "關(guān)鍵路徑演示完畢，繼續(xù)進(jìn)行嗎?(Y/N)" );
		scanf ( " %c",&j );
	}
}

BOOL CriticalPath ( Graph G )
{//G為有向網(wǎng)，輸出G的各項(xiàng)關(guān)鍵活動(dòng)
	int j,dut,k,ee,el;
	int vl[MAX_VERTEX_NUM]; //存放各頂點(diǎn)的最遲發(fā)生時(shí)間
	Stack T;     //堆棧T存放拓?fù)渑判虻捻旤c(diǎn)序列
	ArcNode*p;
	Initial ( T );  //初始化堆棧T
	if ( !TopologicalSort ( G,T ) ) return False;
	//利用拓?fù)渑判蚯蟪龈黜旤c(diǎn)的最早發(fā)生時(shí)間，并用T返回拓?fù)湫蛄校?	//若返回False，表明該網(wǎng)有回路
	printf ( "Critical Path:\n" );
	Gettop ( T,k ); //k取得拓?fù)湫蛄械淖詈笠粋�(gè)頂點(diǎn)，即該網(wǎng)的匯點(diǎn)
	vl[k]=ve[k]; //匯點(diǎn)的vl=ve
	for ( j=1; j<=G.vexnum; j++ ) if ( j!=k ) vl[j]=INFINITY; //將其他的頂點(diǎn)的vl置為IFINITY
	while ( !StackEmpty ( T ) ) //按拓?fù)淠嫘蚯蟾黜旤c(diǎn)的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++ )  //求每條弧的最早開始時(shí)間ee和最遲開始時(shí)間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，則該弧為關(guān)鍵活動(dòng)
		}
	return True;
}
void CreateGraph ( Graph &G )
{//構(gòu)造鄰接表結(jié)構(gòu)的圖G
	int i;
	int start,end,arcweight;
	ArcNode *s;
	printf ( "請輸入頂點(diǎn)數(shù)和弧數(shù)(頂點(diǎn)數(shù)，弧數(shù)):" );
	scanf ( "%d,%d",&G.vexnum,&G.arcnum ); //輸入圖的頂點(diǎn)數(shù)和弧數(shù)
	for ( i=1; i<=G.vexnum; i++ ) G.AdjList[i]=NULL; //初始化指針數(shù)組
	printf ( "請輸入各弧和權(quán)值，格式:弧尾,弧頭,權(quán)值\n" );
	for ( i=1; i<=G.arcnum; i++ )
	{
		scanf ( "%d,%d,%d",&start,&end,&arcweight );
		//輸入弧的起點(diǎn)和終點(diǎn)即該弧所代表的活動(dòng)的持續(xù)時(shí)間
		s= ( ArcNode * ) malloc ( sizeof ( ArcNode ) ); //生成一個(gè)弧結(jié)點(diǎn)
		s->nextarc=G.AdjList[start]; //插入到鄰接表中
		s->adjvex=end;
		s->weight=arcweight;
		G.AdjList[start]=s;
	}
}

BOOL TopologicalSort ( Graph G,Stack &T )
{//有向網(wǎng)G采用鄰接表存儲(chǔ)結(jié)構(gòu)，求各頂點(diǎn)事件的最早發(fā)生時(shí)間ve，
//T為拓?fù)湫蛄许旤c(diǎn)棧，S為零入度頂點(diǎn)棧。
//若G無回路，則用棧返回G的一個(gè)拓?fù)湫蛄校�且函�?shù)返回True,否則返回False
	int i,k;
	int count; //計(jì)數(shù)器
	ArcNode* p;
	Stack S;
	FindInDegree ( G ); //求出圖中各頂點(diǎn)的入度
	Initial ( S );   //堆棧初始化，存放入度為零的頂點(diǎn)
	for ( i=1; i<=G.vexnum; i++ )
		if ( !G.indegree[i] ) Push ( S,i ); //入度為零的頂點(diǎn)入棧
	count=0;     //對輸出頂點(diǎn)記數(shù)
	for ( i=1; i<=G.vexnum; i++ )
		ve[i]=0;   //ve初始化
	while ( !StackEmpty ( S ) )
	{
		Pop ( S,i );  //i號頂點(diǎn)出S棧并入T棧，count記數(shù)
		Push ( T,i );
		count++;
		for ( p=G.AdjList[i]; p; p=p->nextarc )
		{
			k=p->adjvex;       //對i號頂點(diǎn)的每個(gè)鄰接頂點(diǎn)的入度減一
			if ( ! ( --G.indegree[k] ) ) Push ( S,k ); //若入度為零，入棧
			if ( ( ve[i]+p->weight ) >ve[k] ) ve[k]=ve[i]+p->weight;
			//修改k號頂點(diǎn)的最遲發(fā)生時(shí)間
			//ve的求法：ve(j)=Max{ve(i)+dut(<i,j>)} <i,j>∈S,j=1,2,…,n-1
		}
	}
	if ( count<G.vexnum ) return False; //如輸出頂點(diǎn)數(shù)少于圖中頂點(diǎn)數(shù)，則該圖有回路
	else return True;
}
void FindInDegree ( Graph &G )
{//求出圖G的各頂點(diǎn)的入度，存放在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]++;  //弧頭頂點(diǎn)的入度加一
	}
}
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;
}

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。