graphfunc.cpp

数据结构中有关图的算法

/*************************************************************************************
    以下函数建立图的邻接表结构，并实现图的深度和广度优先搜索,深度优先生成树，广度优先
生成树，结点之间连通性判断，最小生成树（普尼姆算法和克鲁斯卡尔算法），拓扑排序，最短
路径和关键路径等算法。
	图的存储结构定义在WORK18.H中

                                                            编写者：黄海于
										                    2002、12、6
*************************************************************************************/
#include "work18.h"

/*************************************************************************************
    函数：Graph CreateGraph(int Choice)；

    功能：根据用户要求建立有向图、网和无向图、网的邻接表存储结构

    形式参数：
	      Choice: 对于无向图而言，输入大于1的值，对于有向图的入表，则输入0，
		          对于有向图的出表，则输入1。
    函数输出：
	      指向邻接表存储结构第一个存储单元的指针
*************************************************************************************/
Graph CreateGraph(int Choice)
{
    Graph G;
	int   i;
	char  Head[20],Tail[20],*stemp,*htemp;
	float weight;
	
	//分配内存
	G=(Graph)malloc(sizeof(ALGraph));
	
	//输入图的类型
	printf("Please input the type of Graph:\n");
	if(Choice<=1){
       printf("0: diGraph\n");
	   printf("1: diNetwork\n");
	}
	else{
	  printf("2: UndiGraph\n");
	  printf("3: UndiNetwork\n");
	}

	printf("Choice:");
	scanf("%d",&G->kind);
	
	//输入顶点数目和弧的数目
	printf("Please input number Arc:");
	scanf("%d",&G->arcnum);

	//输入所有的弧或线段
	printf("please input each Arc in the Graph\n");
    //输入所有的弧或线段，若为有向图，则按起点和终点输入方式，
	//结点名为字符串，不超过20个字节
	G->vexnum=0;
	G->vertices=(AdjList)malloc(sizeof(VNode)*(G->vexnum+1));
	for(i=0;i<G->arcnum;i++){
	   //每条弧的起点和终点,对于图而言，不需要输入权值
	   printf("Input Arc %d ==> Tail Head",i+1);
	   if(G->kind==1 || G->kind==3)
		   printf(" weight");       
	   printf(":");

	   scanf("%s%s",Tail,Head);
	   if(G->kind==1 || G->kind==3)
		   scanf("%f",&weight);
	   else 
		   weight=0;
     
	   stemp=Tail;
	   htemp=Head;
	   //如果是有向图且为出表或者为无向图
	   if(Choice<=0)
	       InsertNode(htemp,stemp,G,weight);				 				 
	   //如果是有向图且为入表
	   else
           InsertNode(stemp,htemp,G,weight);
	}		 
	
	return G;
}

/*************************************************************************************
    函数：void InsertNode(char *stemp,char *htemp,Graph G,float weight);

    功能：根据输入的信息，在邻接表中插入一个结点。

    形式参数：
	      stemp:  弧的一个顶点名，对有向图而言为起点。
		  htemp:  弧的一个顶点名，对有向图而言为终点。
		  G:      指向图邻接表存储结构的指针
		  weight: 弧上的权值，如果为图，则输入0，否则输入实际的权值

    函数输出：
	      无
*************************************************************************************/
void InsertNode(char *stemp,char *htemp,Graph G,float weight)
{
    int  pos,prepos;
   	
	//确定是否需要将输入的弧插入到邻接表连续存储空间中，并得到插入位置
	prepos=InsertStr(stemp,G);
	pos=InsertStr(htemp,G);
	//插入结点
	InsNode(prepos,pos,G,weight);
		 
	//如果为无向图，则需要在链表中插入两次
	switch(G->kind){
	case AG:
	case AN:
		 InsNode(pos,prepos,G,weight);
		 break;
	}

  return;
}

/*************************************************************************************
    函数：int InsertStr(char *stemp,Graph G);

    功能：在图的邻接表存储结构中查找是否有值为stemp的结点，如果无，则插入，如果有，则
	      只返回该结点的相对位置。

    形式参数：
	      stemp:  弧的一个顶点名
		  G:      指向图邻接表存储结构的指针
		 
    函数输出：
	      该结点名在邻接表中的相对位置
*************************************************************************************/
int InsertStr(char *stemp,Graph G)
{
    int i;
	char *ctemp;
    

	//指向0号存储单元
	ctemp=G->vertices[0].data;
    
	//查找此前的所有存储单元，如果该结点名已经存在，则不再保留
	for(i=0;i<G->vexnum;i++){
		ctemp=G->vertices[i].data;
		if(strcmp(stemp,ctemp)==0)
			 break;
	 }

	//若不存在，则保存该结点，并增加结点数目
	if(i==G->vexnum){
       ctemp=G->vertices[i].data;
	   strcpy(ctemp,stemp);
	   G->vertices[i].firstarc=NULL;
	   G->vertices[i].visited=0;
	   G->vertices[i].Indegree=0;
	   G->vertices[i].Outdegree=0;
	   G->vexnum++;
	   G->vertices=(AdjList)realloc(G->vertices,sizeof(VNode)*(G->vexnum+1));
	 }

  return i;
}

/*************************************************************************************
    函数：void InsNode(int pos1,int pos2,Graph G,float weight);

    功能：根据弧或线段的信息，在邻接表中插入一个结点

    形式参数：
	      pos1:   弧或线段的一个顶点在邻接表中的相对位置
		  pos2:   弧或线段的另一个顶点在邻接表中的相对位置
		  G:      指向图邻接表存储结构的指针
		  weight: 弧上的权值，如果为图，则输入0，否则输入实际的权值

    函数输出：
	      无
*************************************************************************************/
void  InsNode(int pos1,int pos2, Graph G,float weight)
{
     ArcNode  *p,*q;

	 //分配存储空间，并设置结点的信息
     p=(ArcNode*)malloc(sizeof(ArcNode));
	 p->weight=weight;
	 p->adjvex=pos2;
	 p->nextarc=NULL;
	 //如果是第一个邻接点
	 if(G->vertices[pos1].firstarc==NULL)
		 G->vertices[pos1].firstarc=p;
	 //如果不是第一个邻接点，则成为链表中最后一个结点
	 else{
	     q=G->vertices[pos1].firstarc;
		 while(q->nextarc!=NULL)
		    q=q->nextarc;
	     q->nextarc=p;
	 }
	 G->vertices[pos1].Outdegree++;
	 G->vertices[pos2].Indegree++;

  return;
}

/*************************************************************************************
    函数：void DepthSearch(Graph G);

    功能： 采用深度优先搜索方法遍历图中的所有结点

    形式参数：
	      G:   指向图邻接表存储结构的指针，如果为有向图或网该,G为出表
		  
    函数输出：
	      无
*************************************************************************************/
void DepthSearch(Graph G)
{
     int i;

	  //设置未访问标志
	 for(i=0;i<G->vexnum;i++)
		 G->vertices[i].visited=0;

	 for(i=0;i<G->vexnum;i++){
		 if(G->vertices[i].visited==0)
			 DepthOneSearch(G,i);
	 }  
  return;
}

/*************************************************************************************
    函数：void DepthOneSearch(Graph G,int i);

    功能：从某个结点出发，一次深度优先搜索图的邻接表结构

    形式参数：
	      G:  指向图邻接表存储结构的指针
		  i:  该结点在邻接表中的相对位置

    函数输出：
	      无
*************************************************************************************/
int DepthOneSearch(Graph G,int i)
{
     int j=0,visited=0;
     ArcNode *p,**Node,*q;
	 
	 Node=(ArcNode **)malloc(sizeof(ArcNode)*(j+1));
	 
	 //访问第一个结点，该结点一定是没有被访问过
	 printf("%s  ",G->vertices[i].data);
	 G->vertices[i].visited=1;
	 visited++;

	 //指向其第一个邻接点
	 p=G->vertices[i].firstarc;  
	 //循环直到条件满足后自动返回
	 while(1){
		
		//如果当前顶点的邻接点不为空并且该邻接点已经访问过，则找其下一个邻接点
		while( p!=NULL && G->vertices[p->adjvex].visited==1)
	       p=p->nextarc;
	    
		//q指向当前未访问结点
		q=p;
		//如果当前已经访问完该结点的所有邻接点，则从堆栈中弹出下一个要访问的邻接点
	    if(p==NULL){
		   //如果堆栈中还有未访问的邻接点，则弹出一个未曾访问的邻接点
		   if(j>0){
			   //在堆栈中查找未访问过的邻接点
			   do{
			      j--;
		          p=Node[j];
			   }while(j>=0 && G->vertices[p->adjvex].visited!=0);
	 		   
			   //如果栈中没有未被访问的元素，则遍历结束,并释放空间
			   if(j<0){
				   free(Node);
				   return visited;
			   }

			   //查找该结点后面未曾访问过的结点
			   q=p;
	           while(q->nextarc!=NULL && 
				    G->vertices[q->nextarc->adjvex].visited==1)
	              q=q->nextarc;	  		  
		   }
		   //如果堆栈为空，并且该结点的所有邻接点都访问过，则退出，并释放空间
		   else{
			  free(Node);
		      return visited;
		   }
		}
		
		//如果该邻接点的下一个邻接点不为空，并且由于该邻接点未曾访问过，
		//因此应该压入堆栈
	    if(q->nextarc!=NULL){
	        Node[j]=q->nextarc;
	        j++;
            Node=(ArcNode **)realloc(Node,sizeof(ArcNode)*(j+1));
		}
		
		//访问该结点，并设置已访问标志
		printf("%s  ",G->vertices[p->adjvex].data);
	    G->vertices[p->adjvex].visited=1;
		visited++;
		
		//访问与其相邻的邻接点
		p=G->vertices[p->adjvex].firstarc;
	 }
  return visited;
}

/*************************************************************************************
    函数：void DepthSearch(Graph G);

    功能： 采用广度优先搜索方法遍历图中的所有结点

    形式参数：
	      G:  指向图邻接表存储结构的指针，如果为有向图或网该,G为出表
		  
    函数输出：
	      无
*************************************************************************************/
void BreadthSearch(Graph G)
{
     int i;

	   //设置未访问标志
	 for(i=0;i<G->vexnum;i++)
		 G->vertices[i].visited=0;

	 for(i=0;i<G->vexnum;i++){
		 if(G->vertices[i].visited==0)
			 BreadthOneSearch(G,i);
	 }
	 
   return;

}

/*************************************************************************************
    函数：void BreadthOneSearch(Graph G,int i);

    功能：从某个结点出发，一次广度优先搜索图的邻接表结构

    形式参数：
	      G:      指向图邻接表存储结构的指针
		  i:      该结点在邻接表中的相对位置

    函数输出：
	      无
*************************************************************************************/
int BreadthOneSearch(Graph G, int i)
{
     int j=0,k=0,visited=0;
     ArcNode *p,**Node;
	 
     //分配临时存储单元
	 Node=(ArcNode **)malloc(sizeof(ArcNode)*(j+1));
	 
	 //访问第一个结点，该结点一定是没有被访问过
	 printf("%s  ",G->vertices[i].data);
	 G->vertices[i].visited=1;
	 visited++;
	 
	 //指向其第一个邻接点
	 p=G->vertices[i].firstarc;  
     while(1){
		
		//如果当前顶点的邻接点不为空并且该邻接点已经访问过，则找其下一个邻接点
		while( p!=NULL){
			 //如果该邻接点未被访问过，则入栈，并且访问该结点
			 if(G->vertices[p->adjvex].visited==0){
                 Node[j]=p;
	             j++;
                 Node=(ArcNode **)realloc(Node,sizeof(ArcNode)*(j+1));
                 //访问该结点，并设置已访问标志
		         printf("%s  ",G->vertices[p->adjvex].data);
	             G->vertices[p->adjvex].visited=1;
				 visited++;
			 }
			 //查找下一个邻接点
		     p=p->nextarc;
		}
	    
		//如果队列中还有未访问的邻接点，则出队列，访问下一个未曾访问的邻接点
		if(j>k){		  
		     p=Node[k];
		     k++;			
		 }
		  //如果队列为空，并且该结点的所有邻接点都访问过，则退出，并释放空间
		 else{		 
			 free(Node);			 
		     return visited;
		 }
	 	 //访问与其相邻的邻接点
	     p=G->vertices[p->adjvex].firstarc;
	 }

   return visited;
}

/*************************************************************************************
    函数：Graph DepthTrees(Graph G);

    功能：深度优先搜索得到用孩子链表结构表示的深度优先生成树或森林。

    形式参数：
	      G:   指向图邻接表存储结构的指针，如果为有向图或网该,G为出表
		  
    函数输出：
	      指向深度优先生成树的孩子链表结构指针
*************************************************************************************/
Graph DepthTrees(Graph G)
{
     Graph CTree;
	 int   i;
     
     //给树存储结构分配存储单元，由于采用树的孩子表示法，因此结构与
	 //图的连接表结构基本相同,故在此采用图的存储结构存储该生成树，但
	 //有些信息没有使用
     CTree=(Graph)malloc(sizeof(ALGraph));

	 //给其孩子结点分配存储空间
	 CTree->vertices=(AdjList)malloc(sizeof(VNode)*G->vexnum);
	 for(i=0;i<G->vexnum;i++){
		 CTree->vertices[i].firstarc=NULL;
		 G->vertices[i].visited=0;
	 }
	
     for(i=0;i<G->vexnum;i++){
		if(G->vertices[i].visited==0)
		      DepthOneTree(G,i,CTree);
	 }


   return CTree;

}

/*************************************************************************************
    函数：void DepthOneTree(Graph G,int i,Graph CTree);

    功能： 采用深度优先搜索方法得到一棵深度优先生成树

    形式参数：
	      G:     指向图邻接表存储结构的指针，如果为有向图或网该,G为出表
		  i:     未访问结点的在邻接表存储结构中的指针
		  CTree: 构造成的深度优先生成树
		  
    函数输出：
	      无
*************************************************************************************/