7_41.cpp

数据结构与算法利用深度优先遍历有向图求关键路径

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#define VertexType char //数据元素类型
#define vexnum 6 //最大顶点数
int Vn=6,En=8; //实际顶点数，边或弧数
typedef enum{FALSE,TRUE}Boolean;
Boolean visited[vexnum];
int ve[vexnum]={0};
int vl[vexnum]={0};
int indegree[6];
char Ve[vexnum+1]="abcdef";
int act[8]={3,2,2,3,4,3,2,1};
// 邻接表存储结构
typedef struct ArcNode
{
	int adjvex; //邻接点在顺序表中的位置
	int info;
	struct ArcNode *nextarc; //指向下一个邻接点
}ArcNode,*AdjLink;

// 表头指针结构
typedef struct VNode
{
	VertexType data;
	//AdjLink HAdjV; //邻接点链表头指针
	ArcNode *firstarc;
} VNode;

// 图的邻接表存储结构
VNode AdjList[vexnum];
// 图的初始化

void GraphAdjLInit(VertexType *vs)
{
	if (Vn>vexnum) Vn=vexnum;
	for (int k=0; k<vexnum; ++k)
	{
		if (k<Vn) AdjList[k].data=vs[k];
		else AdjList[k].data=NULL;
		AdjList[k].firstarc=NULL;
	}
} //GraphAdjLInit

// 求顶点v在图G中的位置(下标)
int LocationV(VertexType v)
{
	for (int k=0; k<Vn; ++k)
		if (AdjList[k].data==v) return k;
	if (k>=vexnum) return -1;
	AdjList[k].data=v;
	Vn=k+1;
	AdjList[Vn].data=NULL;
	return k;
} //LocationV

// 通过输入“边”建立图的邻接表存储结构
void GraphAdjCreate(char v,char w,int weight)
{//char ch;
	//VertexType v1,v2;
	//int weight=0;
	int j1=0,j2=0;
	AdjLink p,q;
	/*printf("\n输入各条弧的信息：(中间不要有空格)\n");
	//while (Vn<VertexNum)
	for(int i=0;i<En;i++)
	{printf("请输入第%d条弧<v,w,weight>的信息",i+1);
	scanf("%c%c%d%c",&v1,&v2,&weight,&ch);*/
        j1=LocationV(v);
       j2=LocationV(w); 

		//if (j1==j2 || j1<0 || j2<0) break;
	 if (j1==-1) return;
	if (j2==-1) return;
	//	++En;
		p=(AdjLink) malloc(sizeof(VNode));
		p->adjvex=j2;
		p->info=weight;
		p->nextarc=NULL;
		if (!AdjList[j1].firstarc) {AdjList[j1].firstarc=p;}
		else
		{
			q=AdjList[j1].firstarc;
			while (q->nextarc) q=q->nextarc;
			q->nextarc=p;
		}
	
} //GraphAdjCreate

// 显示图的邻接表存储结构
void GraphAdjLPrint()
{
	for(int k=0; k<Vn; ++k)
	{
		printf("%d [%c",k,AdjList[k].data);
		AdjLink p=AdjList[k].firstarc;
		if(p)printf(",*]->[");	
		while(p)
		{ if(p->nextarc)
		  printf("%d,%d,%d,*]->[",k,p->adjvex,p->info);
		else printf("%d,%d,%d",k,p->adjvex,p->info);
			p=p->nextarc;
		}
		printf(",^]\n");
	}
}//GraphAdjLPrint

void FindInDegree()
 { 
   int i;
   AdjLink p;
   for(i=0;i<Vn;i++)  indegree[i]=0; 
   for(i=0;i<Vn;i++)
   {
     p=AdjList[i].firstarc;
     while(p)
     { indegree[p->adjvex]++;
       p=p->nextarc;
	 }
   }
}

void DFS1(int i)
{int dut;
  if(!indegree[i]) ve[i]=0;
  for(AdjLink p=AdjList[i].firstarc;p;p=p->nextarc)
  {
    dut=p->info;
    if(ve[i]+dut>ve[p->adjvex])
      ve[p->adjvex]=ve[i]+dut;
    DFS1(p->adjvex);
  }
}//DFS1 

void DFS2(int i)
{int dut;

if(!AdjList[i].firstarc) vl[i]=ve[i];
  else
  {
    for(AdjLink p=AdjList[i].firstarc;p;p=p->nextarc)
    {
      DFS2(p->adjvex);
      dut=p->info;
      if(vl[p->adjvex]-dut<vl[i])
	  vl[i]=vl[p->adjvex]-dut;
    }
  }//else
}//DFS2 
void Critical_Path()//利用深度优先遍历求网的关键路径
{int i;
  FindInDegree();
  for(i=0;i<Vn;i++)
    if(!indegree[i]) DFS1(i); //第一次深度优先遍历:建立ve
for(i=0;i<Vn;i++)vl[i]=ve[Vn-1];
  for(i=0;i<Vn;i++)
    if(!indegree[i]) DFS2(i); //第二次深度优先遍历:建立vl
	printf("顶点     ve        vl\n");
 for(i=0;i<Vn;i++)	printf("%c        %d         %d\n",Ve[i],ve[i],vl[i]);
	printf("关键路径为");
  for(i=0;i<Vn;i++)
    if(vl[i]==ve[i]) printf("->%c",AdjList[i]); //打印输出关键路径
}//Critical_Path 

void main()
{ 
printf("利用深度优先遍历有向图求关键路径\n课本186页的例题\n");
GraphAdjLInit(Ve);
GraphAdjLPrint(); 
/***********弧的信息***************/
GraphAdjCreate(Ve[0],Ve[1],act[0]);
GraphAdjCreate(Ve[0],Ve[2],act[1]);
GraphAdjCreate(Ve[1],Ve[3],act[2]);
GraphAdjCreate(Ve[1],Ve[4],act[3]);
GraphAdjCreate(Ve[2],Ve[3],act[4]);
GraphAdjCreate(Ve[2],Ve[5],act[5]);
GraphAdjCreate(Ve[3],Ve[5],act[6]);
GraphAdjCreate(Ve[4],Ve[5],act[7]);

printf("\n初始有向图为:(v,w,weight) \n");
GraphAdjLPrint();

Critical_Path();
printf("\n");
}