graphfunc.cpp

数据结构中有关图的算法

void DepthOneTree(Graph G,int i,Graph CTree)
{
     int j=0,*Parent,pos;
     ArcNode *p,**Node,*q,*tNode,*pNode;
	 char *s,*t;
	 
	 //分配存储单元存储压入堆栈的下一个应该出栈的结点
	 Node=(ArcNode **)malloc(sizeof(ArcNode)*(j+1));
	 //分配存储单元存放堆栈中对应结点其双亲所在的相对位置
	 Parent=(int *)malloc(sizeof(int)*(j+1));
	  
   	 //访问第一个结点，该结点一定是没有被访问过
	 //printf("%s  ",G->vertices[i].data);
	 G->vertices[i].visited=1;
     
	 //保存树的结点信息
	 s=G->vertices[i].data;
	 t=CTree->vertices[i].data;
	 strcpy(t,s);
	 pos=i;

	 //指向其第一个邻接点
	 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];
				  pos=Parent[j];
			   }while(j>=0 && G->vertices[p->adjvex].visited!=0 );
	 		   
			   //如果栈中没有未被访问的元素，则遍历结束
			   if(j<0){
				   free(Node);
				   free(Parent);
				   return;
			   }

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

		//查找该结点所在的位置,并将当前结点插入到原孩子链表的最后
		pNode=CTree->vertices[pos].firstarc;
		if(pNode==NULL)
			CTree->vertices[pos].firstarc=tNode;
        else{     
		    while(pNode->nextarc!=NULL)
			   pNode=pNode->nextarc;
		    pNode->nextarc=tNode; 
		}
		
		//其双亲结点所在的位置
		pos=p->adjvex;
        //建立新的树的结点信息
		s=G->vertices[p->adjvex].data;
	    t=CTree->vertices[p->adjvex].data;
	    strcpy(t,s);	     

		//访问与其相邻的邻接点
		p=G->vertices[p->adjvex].firstarc;
			
	 }
  
   return;
}

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

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

    形式参数：
	      G:   指向图邻接表存储结构的指针，如果为有向图或网该,G为出表
		  
    函数输出：
	      指向广度优先生成树的孩子链表结构指针
*************************************************************************************/
Graph BreadthTrees(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)
		      BreadthOneTree(G,i,CTree);
	 }

  return CTree;
}

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

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

    形式参数：
	      G:     指向图邻接表存储结构的指针，如果为有向图或网该,G为出表
		  i:     未访问结点的在邻接表存储结构中的指针
		  CTree: 构造成的广度优先生成树
		  
    函数输出：
	      无
*************************************************************************************/
void BreadthOneTree(Graph G, int i, Graph CTree)
{
     int j=0,k=0,pos;
     ArcNode *p,**Node,*tNode,*pNode;
	 char *s,*t;
	 
     //分配临时存储单元
	 Node=(ArcNode **)malloc(sizeof(ArcNode)*(j+1));
	 
	 //访问第一个结点，该结点一定是没有被访问过
	 //printf("%s  ",G->vertices[i].data);
	 G->vertices[i].visited=1;
	 
	 //保存树的结点信息
	 s=G->vertices[i].data;
	 t=CTree->vertices[i].data;
	 strcpy(t,s);
	 pos=i;

	 //指向其第一个邻接点
	 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;
                 
				 //建立树的孩子表示法存储结构
                 //建立树的孩子结点
                 tNode=(ArcNode *)malloc(sizeof(ArcNode));
		         tNode->adjvex=p->adjvex;
		         tNode->nextarc=NULL;
		         tNode->weight=tNode->weight;

	           	 //查找该结点所在的位置,并将当前结点插入到原孩子链表的最后
		         pNode=CTree->vertices[pos].firstarc;
		         if(pNode==NULL)
			          CTree->vertices[pos].firstarc=tNode;
                 else{     
		              while(pNode->nextarc!=NULL)
			              pNode=pNode->nextarc;
		              pNode->nextarc=tNode; 
				 }
			 }
			 //查找下一个邻接点
		     p=p->nextarc;
		}
	    
		//如果队列中还有未访问的邻接点，则出队列，访问下一个未曾访问的邻接点
		if(j>k){		  
		     p=Node[k];
		     k++;			
		 }
		  //如果队列为空，并且该结点的所有邻接点都访问过，则退出，并释放空间
		 else{		 
			 free(Node);
		     return;
		 }


		 //其双亲结点所在的位置
		 pos=p->adjvex;
         //建立新的树的结点信息
		 s=G->vertices[p->adjvex].data;
	     t=CTree->vertices[p->adjvex].data;
	     strcpy(t,s);	 
	 	 //访问与其相邻的邻接点
	     p=G->vertices[p->adjvex].firstarc;
	 }

   return;
}

/*************************************************************************************
    函数：void NodeConnect(Graph G,char *stemp,char *htemp);

    功能： 判断两结点是否连通

    形式参数：
	      G:     指向图邻接表存储结构的指针，如果为有向图或网该,G为出表
		  stemp: 结点名称
		  htemp: 结点名称
		  
    函数输出：
	      0: 两结点不连通
		  1: 两结点连通
*************************************************************************************/
int NodeConnect(Graph G, char *stemp, char *htemp)
{
     	 
     int j=0,k=0,i;
     ArcNode *p,**Node;
	 char *s;
	 
	 //设置未访问标志
	 for(j=0;j<G->vexnum;j++)
		 G->vertices[j].visited=0;

	 j=0;
	 //找到起始结点的相对位置，如果一次遍历能够找到另外一个结点，则说明
	 //两结点处在同一个连通图上
	 i=InsertStr(stemp,G);

     //分配临时存储单元
	 Node=(ArcNode **)malloc(sizeof(ArcNode)*(j+1));
	 
	 //访问第一个结点，该结点一定是没有被访问过
	 //printf("%s  ",G->vertices[i].data);
	 G->vertices[i].visited=1;
	 
	 //指向其第一个邻接点
	 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));
                 //访问该结点，并设置已访问标志
		         s=G->vertices[p->adjvex].data;
				 //printf("%s  ",s);
	             G->vertices[p->adjvex].visited=1;
				 
				 //如果该结点与要查找的结点相同，则说明两者连通
                 if(strcmp(s,htemp)==0)
					 return 1;

			 }
			 //查找下一个邻接点
		     p=p->nextarc;
		}
	    
		//如果队列中还有未访问的邻接点，则出队列，访问下一个未曾访问的邻接点
		if(j>k){		  
		     p=Node[k];
		     k++;			
		 }
		  //如果队列为空，并且该结点的所有邻接点都访问过，则退出，并释放空间
		 else{		 
			 free(Node);
		     return 0;
		 }
	 	 //访问与其相邻的邻接点
	     p=G->vertices[p->adjvex].firstarc;
	 }

   return 0;
}

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

    功能： 采用Prim算法求最小生成树

    形式参数：
	      G:     指向图邻接表存储结构的指针，如果为有向图或网该,G为出表
		  
    函数输出：
	      指向最小生成树的指针,最小生成树采用图的邻接表结构，也是树的孩子表示法
*************************************************************************************/
Graph PrimTree(Graph G)
{
     Graph CTree;
     int i,Maxpos,pos=0;
	
	 //分配存储空间给最小生成树
	 CTree=(Graph)malloc(sizeof(ALGraph));
	 CTree->vexnum=0;
     CTree->vertices=(AdjList)malloc(sizeof(VNode)*(G->vexnum+1));     

	 //将原图中的每个结点设置没有访问标志
	 for(i=0;i<G->vexnum;i++)
		 G->vertices[i].visited=0;	
     
	 //得到最小生成树中当前结点个数
	 Maxpos=InsertStr(G->vertices[pos].data,CTree);
	 //查找与当前结点相连的其它结点的最小值，然后将该结点插入到最小
	 //生成树中，并将该结点设置成已访问标志
	 for(i=0;i<=Maxpos;i++){
		Maxpos=FindPrimWeight(G,CTree,i);   
		//如果两个集合的结点数相同，则结束
		if(Maxpos>G->vexnum)
			break;
	 }

   return CTree;
}

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

    功能： 查找从已找到最小值的结点集合到其它点集合的最小值，并构建相应的最小生成树

    形式参数：
	      G:     指向图邻接表存储结构的指针，如果为有向图或网该,G为出表
		  CTree: 指向最小生成树的指针
		  Maxpos:当前已构建的最小生成树中结点的数目
		  
    函数输出：
	      当前已构建的最小生成树中的结点数目
*************************************************************************************/
int FindPrimWeight(Graph G,Graph CTree,int Maxpos)
{

     float Minw;
	 ArcNode *p,*q=NULL;
	 int rpos,pos,curpos,i,cpos;
	 char *s;	 
	 
	 //得到当前最小生成树中的结点数
     curpos=Maxpos;
	 Minw=(float)3.4E38;

	 //从CTree的第一结点开始，查找CTree中所有结点与剩余结点相连的弧中权值最小者
	 for(i=0;i<=Maxpos;i++){
		 //得到待查找的起始结点在原图中的位置
	     pos=InsertStr(CTree->vertices[i].data,G);
         p=G->vertices[pos].firstarc;
         G->vertices[pos].visited=1;		 
		 if(p!=NULL){
			 //比较与第i结点相连的所有结点中权值最小者，并保留其结点地址以便在
			 //CTree中插入该结点的信息
             while(p!=NULL){
			      if(G->vertices[p->adjvex].visited==0 && Minw>p->weight){
                      Minw=p->weight;
				      q=p;
					  cpos=i;
				  }	
				  p=p->nextarc;
			 }
		 }	
	 }
     
	 //如果该结点不为空，者需要建立最小生成树
	 if(q!=NULL){
	    G->vertices[q->adjvex].visited=1;   
	    s=G->vertices[q->adjvex].data;
	    rpos=InsertStr(s,CTree);
	    InsNode(cpos,rpos,CTree,q->weight);
	    curpos=curpos>rpos?curpos:rpos;
	 }
  return curpos;
}

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

    功能： 采用Kruskal算法求最小生成树

    形式参数：
	      G:     指向图邻接表存储结构的指针，如果为有向图或网该,G为出表
		  
    函数输出：
	      指向最小生成树的指针,最小生成树采用图的邻接表结构，也是树的孩子表示法
*************************************************************************************/
Graph KruskalTree(Graph G)
{
     
	 Graph CTree,KTree;
     int i,pos=0;
	
	 //分配存储空间给最小生成树,同时初始化
	 CTree=(Graph)malloc(sizeof(ALGraph));
	 CTree->vexnum=0;
     CTree->vertices=(AdjList)malloc(sizeof(VNode)*(G->vexnum+1));    
	 CTree->kind=G->kind;
	 CTree->arcnum=0;

	 //将原图中的每个结点设置没有访问标志,在CTree中插入空的结点名
	 for(i=0;i<G->vexnum;i++){
		 G->vertices[i].visited=0;
		 InsertStr(G->vertices[i].data,CTree);
	 }
     
	 //查找所有弧中权值最小的弧，如果该弧上两个顶点在CTree中是不连通
	 //的，则认为处在不同的连通分量上。只有权值最小，且出在不同的的连
	 //通分量上，才认为是合适的。如果所有的顶点都是连通的，则认为已得
	 //到最小生成树
	 while(1){
	    if(FindKruskalWeight(G,CTree)==1)
	  	   break;
	 }