graphfunc.cpp

数据结构中有关图的算法

     //上面得到的是图的存储结构，可通过生成树的方式，将其变成树的存储
	 //结构
     KTree=BreadthTrees(CTree);
       
	return KTree;
}

/*************************************************************************************
    函数：int FindKruskalWeight(Graph G,Graph CTree)；

    功能： 查找权值最小且落在不同的连通分量上的弧，并将其构成新的图的结构

    形式参数：
	      G:     指向图邻接表存储结构的指针，如果为有向图或网该,G为出表
		  CTree: 指向用图表示的最小生成树的指针，该树采用图的存储结构
		  
    函数输出：
	      0：    图中所有顶点还未处在同一个连通分量上
		  1：    图中所有顶点处在同一个连通分量上
*************************************************************************************/
int FindKruskalWeight(Graph G, Graph CTree)
{
      
     float Minw;
	 ArcNode *p,*q=NULL;
	 int i,cpos;
	 char *s,*t;
	 
	 //设置最小权值为最大值
     Minw=(float)3.4E38;

	 //从G中的第一结点开始，查找这些结点与其它结点相连的弧中权值最小者
	 for(i=0;i<G->vexnum;i++){
		 //得到G中第i个结点的起始地址	     
		 p=G->vertices[i].firstarc;
		 //如果不为空，则查找权值最小的结点     
		 if(p!=NULL){
             //比较与第i结点相连的所有结点中权值最小者，并保留其结点地址以便在
			 //CTree中插入该结点的信息
             while(p!=NULL){
			      //如果当前权值更小，且两个顶点不在同一个连通图上，则认为新的
				  //最小权值
				  s=G->vertices[i].data;
				  t=G->vertices[p->adjvex].data;
			      if( NodeConnect(CTree,s,t)==0 && Minw>p->weight){
                      Minw=p->weight;
				      q=p;
					  cpos=i;
				  }	
				  p=p->nextarc;
			 }
		 }	
	 }
     
	 //如果该结点不为空，则需要构造新的图	 
	 if(q!=NULL ){
         InsNode(cpos,q->adjvex,CTree,q->weight);
		 InsNode(q->adjvex,cpos,CTree,q->weight);
		 CTree->arcnum++;
	 }
	
	 //如果所有结点都已连通，则结束构造最小生成树	 
     if(ConnectGraph(CTree)==1)
		 return 1;
	
   return 0;
}

/*************************************************************************************
    函数：int ConnectGraph(Graph G)；

    功能： 判断该图中的所有顶点是否在同一个连通分量上，也可用于判断该图是否是一个连通图

    形式参数：
	      G:  指向图邻接表存储结构的指针，如果为有向图或网该G为出表
		 		  
    函数输出：
	      1： 该图为一个连通图
		  0： 该图不是一个连通图
*************************************************************************************/
int ConnectGraph(Graph G)
{
    
     int j=0,k=0,visited=0,i=0;
     ArcNode *p,**Node;
	 
     //分配临时存储单元
	 Node=(ArcNode **)malloc(sizeof(ArcNode)*(j+1));
	 
	 //设置未访问标志
	 for(j=0;j<G->vexnum;j++)
		 G->vertices[j].visited=0;

	 j=0;
	 //访问第一个结点，该结点一定是没有被访问过
	 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));
                 //访问该结点，并设置已访问标志
		         G->vertices[p->adjvex].visited=1;
				 visited++;
			 }
			 //查找下一个邻接点
		     p=p->nextarc;
		}
	    
		//如果队列中还有未访问的邻接点，则出队列，访问下一个未曾访问的邻接点
		if(j>k){		  
		     p=Node[k];
		     k++;			
		 }
		  //如果队列为空，并且该结点的所有邻接点都访问过，则退出，并释放空间
		 else{		 
			 free(Node);
			 if(visited==G->vexnum)
		         return 1;
			 else
				 return 0;
		 }
	 	 //访问与其相邻的邻接点
	     p=G->vertices[p->adjvex].firstarc;
	 }

    return 0;
}

/*************************************************************************************
    函数：int TopOrder(Graph G,int Choice)；

    功能： 判断某图是否是AOV网，即图中不存在环。

    形式参数：
	      G:      指有向图邻接表存储结构的指针，该G为出表
		  Choice: 是否显示拓扑排序结果。0：不显示，1：显示
		 		  
    函数输出：
	      1： 该有向图为AOV网
		  0： 该有向图不存在环
*************************************************************************************/
int TopoOrder(Graph G,int Choice)
{

	int i,j,*Node;
	ArcNode *p;

	//为了不破坏原来图的存储信息，故分配额外的存储空间存放结点的入度
	Node=(int *)malloc(sizeof(int)*(G->vexnum+1));
	for(i=0;i<G->vexnum;i++)
		Node[i]=G->vertices[i].Indegree;

	//如果希望显示排序结果则choice==1
	if(Choice==1)
	   printf("Order of Topological:");
	
	//设置未访问标志
	for(i=0;i<G->vexnum;i++)
		G->vertices[i].visited=0;
	
	//循环直到排序结束或者找不到入度为0的顶点
	while(1){
	   //查找入度为0且没有排序的顶点
       for(i=0;i<G->vexnum;i++){
	 	  if(Node[i]==0 && G->vertices[i].visited==0)
			  break;
	   }
       //如果没有这样的顶点，则可能是完全访问完所有的顶点，也可能是没有
	   //入度为0的顶点
	   if(i==G->vexnum){
		   //如果是未访问完所有的顶点，则返回0
		   for(j=0;j<G->vexnum;j++){
			   if(G->vertices[j].visited==0){
				   free(Node);
				   return 0;
			   }
		   }
		   //否则返回1
		   free(Node);
	 	   return 1;
	   }
    
	   //设置已访问标志，并将与其相连的所有邻接点的入度减1
       p=G->vertices[i].firstarc;
	   if(Choice==1)
	      printf("%s ",G->vertices[i].data);
	   G->vertices[i].visited=1;
	   while(p!=NULL){
          Node[p->adjvex]--;
		  p=p->nextarc;
	   }
	}	
}

/*************************************************************************************
    函数：Path *ShortPath(Graph G, char *stemp)；

    功能：求从某个顶点出发到其它顶点的最短路径

    形式参数：
	      G:      指向网的邻接表存储结构的指针，若为有向网，则为出表
		  stemp:  起始点
		 		  
    函数输出：
          指向Path结构的指针。该结构包含所有的最短路径及其长度。
*************************************************************************************/
Path *ShortPath(Graph G, char *stemp)
{

     float Min,Minw=0;
     int   i,pos,visited=0;
	 ArcNode *p;
	 Path  *sp;
	 
	 //给结果分配内存空间
	 sp=(Path *)malloc(sizeof(Path)*(G->vexnum+1));
	 //分配空间存放每条路径
     sp->Spath=(char *)malloc(sizeof(char));
	 
	 //起点在网G中的位置
     pos=InsertStr(stemp,G);

	 //初始化信息
     for(i=0;i<G->vexnum;i++){
		 G->vertices[i].visited=0;
	     //每条路径的起始距离均为无穷大
		 sp[i].Dist=(float)3.4E38;
		 sp[i].Spath=(char *)malloc(sizeof(char)*20);
		 strcpy(sp[i].Spath,"");
	 }
     
	 //保存起点
	 sp[pos].Spath=(char *)realloc(sp[pos].Spath,sizeof(char)*(strlen(stemp)+2));
	 strcpy(sp[pos].Spath,stemp);
	 strcat(sp[pos].Spath," ");

	 p=G->vertices[pos].firstarc;
	 G->vertices[pos].visited=1;

     while(1){
		 //如果从起点到当前点的距离大于此前得到的最短距离和起点到最短距离的
		 //点到当前点的距离之和，则将当前点的距离设置成新的距离值，同时保存
		 //已得到的从起点到当前点的路径，当前的p指向与当前所得到的最短路径上
		 //的点相邻的其它点
		 while(p!=NULL){
		     if(sp[p->adjvex].Dist>Minw+p->weight && 
				         G->vertices[p->adjvex].visited==0){
				 //修改路径长度
			     sp[p->adjvex].Dist=Minw+p->weight;
                 //修改路径为此前一点所经历的路径加上当前点的路径
			     sp[p->adjvex].Spath=(char *)realloc(sp[p->adjvex].Spath,
					           sizeof(char)*(strlen(sp[pos].Spath)+2));
			     strcpy(sp[p->adjvex].Spath,sp[pos].Spath);
			     strcat(sp[p->adjvex].Spath," ");
			 }
			 //查找下一个与之相连的点
			 p=p->nextarc;
		 }
     
		 //查找当前得到的所有路径中最短值，当然应该去除掉已经得到的最短路径的
		 //终点
	     Min=(float)3.4E38;
	     for(i=0;i<G->vexnum;i++){
            if(sp[i].Dist<Min && G->vertices[i].visited==0){
			    Min=sp[i].Dist;
			    pos=i;
				//如果每次循环都能到达这儿，说明路径值不为无穷大并且还有没有得
				//到最短路径的点
				visited=1;
			}
		 }
         
		 //如果所有的点都得到了最短路径或者有一些点根本无法到达，则返回
		 if(i>=G->vexnum && visited==0)
             return sp;

		 //得到从起点到当前的的最短路径
	     visited=0;
		 Minw=Min;
		 G->vertices[pos].visited=1;
	     sp[pos].Spath=(char *)realloc(sp[pos].Spath,
			     sizeof(char)*(strlen(G->vertices[pos].data)+strlen(sp[pos].Spath)+2));
	     strcat(sp[pos].Spath,G->vertices[pos].data);
		 strcat(sp[pos].Spath," ");
	     p=G->vertices[pos].firstarc;		
	 }  
}

/*************************************************************************************
    函数：Path *CriticalPath(Graph G,char *stemp,char *htemp);

    功能：求从stemp出发到htemp的关键路径

    形式参数：
	      G:      有向网的邻接表存储结构，G为出表
		  stemp:  源点
		  htemp:  汇点

    函数输出：
	      存储关键路径上的每条弧以及源点到该弧的路径。每条弧以三元组的形式表示，即
    起点，终点以及源点到该点的路径长度。
*************************************************************************************/
Path *CriticalPath(Graph G,char *stemp,char *htemp)
{
     Path *cp;
     float *ve,*vl,ee,el;
     int i,spos,hpos,j,*Node,*T,k=0;
	 ArcNode *p;	 

	 //为了不破坏原来图的存储信息，故分配额外的存储空间存放结点的入度
	 Node=(int *)malloc(sizeof(int)*(G->vexnum+1));
	 //存储拓扑排序时已访问结点
	 T=(int *)malloc(sizeof(int)*(G->vexnum+1));
	 //存储某结点的最早发生时间
	 ve=(float*)malloc(sizeof(float)*(G->vexnum+1));
	 //存储某结点的最迟发生时间
	 vl=(float*)malloc(sizeof(float)*(G->vexnum+1));
	 //存储最后结果
	 cp=(Path*)malloc(sizeof(Path)*(G->vexnum+1));

	 //将原图中的度存储在临时分配的存储空间中
	 for(i=0;i<G->vexnum;i++)
		Node[i]=G->vertices[i].Indegree;

     //设置未访问标志
	 for(i=0;i<G->vexnum;i++){
		G->vertices[i].visited=0;
		ve[i]=0;
		vl[i]=(float)3.4E38;
	 }
	
	 //查找起点和终点
     spos=InsertStr(stemp,G);
	 hpos=InsertStr(htemp,G);
	 
	 //循环直到排序结束或者找不到入度为0的顶点
	 while(1){
	    //查找入度为0且没有排序的顶点
        for(i=0;i<G->vexnum;i++){
	 	   if(Node[i]==0 && G->vertices[i].visited==0)
			   break;
		}
        //如果没有这样的顶点，则可能是完全访问完所有的顶点，也可能是没有
	    //入度为0的顶点
	    if(i==G->vexnum){
		   //如果是未访问完所有的顶点，则返回0
		   for(j=0;j<G->vexnum;j++){
			   if(G->vertices[j].visited==0){
				   free(Node);
				   free(T);
				   free(ve);
				   free(vl);
				   for(k=0;k<G->vexnum;k++)
				       free(cp[k].Spath);
				   free(cp);
				   return NULL;
			   }
		   }
		   //否则跳出循环，继续计算vl的值
		   break;
		}    
		
	    //设置已访问标志，并将与其相连的所有邻接点的入度减1，同时将访问点
		//压入堆栈
		T[k++]=i;		
        p=G->vertices[i].firstarc;
	    G->vertices[i].visited=1;
		// 查找与其相邻的顶点，并将度减1
		while(p!=NULL){
			//计算其邻接点的最早发生时间＝该点的最早发生时间＋其权值
			if(ve[p->adjvex]<ve[i]+p->weight)
		        ve[p->adjvex]=ve[i]+p->weight;
            Node[p->adjvex]--;
		    p=p->nextarc;
		}
	 }

	 //如果起点和终点不是我们的源点和汇点，则没有任何意义，返回错误信息
     k=k-1;
	 if(T[0]!=spos && T[k]!=hpos){
         free(Node);
	     free(T);
		 free(ve);
		 free(vl);
		 for(k=0;k<G->vexnum;k++)
		     free(cp[k].Spath);
		 free(cp);
		 return NULL;
	 }

	 //汇点的最早发生时间和最迟发生时间相同
     vl[k]=ve[k];
	 k--;	 
	 //取倒数第二个点开始查找与其相邻的邻接点，从而计算其邻接点的最迟发生
	 //时间，k为堆栈当前栈顶指针
	 while(k>=0){
		 p=G->vertices[T[k]].firstarc;
		 while(p!=NULL){
			 //计算最迟发生时间
			 if(vl[k]>vl[p->adjvex]-p->weight)
				 vl[k]=vl[p->adjvex]-p->weight;
			 p=p->nextarc;
		 }
		 k--;
	 }
     
	 //计算某条弧的最早发生时间和最迟发生时间，如果二者相同，则该弧为关键
	 //路径上的点，并将其每条弧保存在cp结构体的每个存储单元中
     k=0;	 
     for(i=0;i<G->vexnum;i++){
		 p=G->vertices[i].firstarc;
		 while(p!=NULL){
			 ee=ve[i];
			 el=vl[p->adjvex]-p->weight;
			 if(ee==el){
				 //分配存储单元
				 cp[k].Spath=(char *)malloc(sizeof(char)*
					          (strlen(G->vertices[i].data)+strlen(G->vertices[p->adjvex].data)
							  +2));
				 //起点
                 strcpy(cp[k].Spath,G->vertices[i].data);
				 strcat(cp[k].Spath," ");
				 //终点
				 strcat(cp[k].Spath,G->vertices[p->adjvex].data);
				 //从源点开始到该点的关键路径的大小
				 cp[k].Dist=vl[p->adjvex];
				 k++;
			 }
			 p=p->nextarc;			 
		 }
	 }
	 free(Node);
     free(T);
     free(ve);
     free(vl);

   return cp;
}