无向图的生成树和生成森林算法

时间:2023-02-05 12:35:20
 

对图的深度优先搜索遍历DFS(或BFS)算法稍作修改,就可得到构造图的DFS生成树算法。

在算法中,树的存储结构采用孩子—兄弟表示法。首先建立从某个顶点V出发,建立一个树结点,然后再分别以V的邻接点为起始点,建立相应的子生成树,并将其作为V 结点的子树链接到V结点上。显然,算法是一个递归算法。

(1) DFStree算法

typedef  struct  CSNode

         ElemType  data ;

         struct  CSNode *firstchild , *nextsibling ;

}CSNode ;

 

CSNode  *DFStree(ALGraph *G , int v)

         CSNode  *T , *ptr , *q ;

         LinkNode  *p ; 

         int w ;

         Visited[v]=TRUE ;

         T=(CSNode *)malloc(sizeof(CSNode)) ;

         T->data=G->AdjList[v].data ;

         T->firstchild=T->nextsibling=NULL ; //   建立根结点

         q=NULL ;

         p=G->AdjList[v].firstarc ;

         while (p!=NULL)

         {

                   w=p->adjvex ;

                   if  (!Visited[w])

               { 

                            ptr=DFStree(G,w) ;       /*  子树根结点  */

                    if  (q==NULL)  T->firstchild=ptr ;

                    else  q->nextsibling=ptr ;

                     q=ptr ;

                }

                p=p->nextarc ;

         }

         return(T) ;

}

 

(2)  BFStree算法

typedef struct Queue

         int  elem[MAX_VEX] ;

         int front , rear ;

}Queue ;     /*   定义一个队列保存将要访问顶点  */

 

CSNode  *BFStree(ALGraph *G ,int v)

         CSNode  *T , *ptr , *q ;

         LinkNode  *p ;

         Queue  *Q ;

         int w , k ;

         Q=(Queue *)malloc(sizeof(Queue)) ;

         Q->front=Q->rear=0 ;   /*建立空队列并初始化*/

         Visited[v]=TRUE ;

         T=(CSNode *)malloc(sizeof(CSNode)) ;

         T->data=G->AdjList[v].data ;

         T->firstchild=T->nextsibling=NULL ; //  建立根结点

         Q->elem[++Q->rear]=v ;   /*   v入队   */

         while (Q->front!=Q->rear)

         { 

                   w=Q->elem[++Q->front] ;  

                   q=NULL ;

                   p=G->AdjList[w].firstarc ;

                   while (p!=NULL)

               {  

                            k=p->adjvex ;

                    if  (!Visited[k])

                 { 

                                     Visited[k]=TRUE ;

                                     ptr=(CSNode *)malloc(sizeof(CSNode)) ;

                         ptr->data=G->AdjList[k].data ;

                         ptr->firstchild=T->nextsibling=NULL ;

                         if  (q==NULL)  T->firstchild=ptr ;

                         else  q->nextsibling=ptr ;

                         q=ptr ;

                         Q->elem[++Q->rear]=k ;  /*   k入对   */

                     }    /*   end  if   */

                         p=p->nextarc ;

                   }     /*  end  while  p  */

         }    /*  end whil  Q  */

         return(T) ;

}  /*求图G广度优先生成树算法BFStree*/

 

(3)  图的生成森林算法

CSNode  *DFSForest(ALGraph *G)

         CSNode  *T , *ptr , *q ; 

         int w ;

         for (w=0; w<G->vexnum; w++)

                   Visited[w]=FALSE;

         T=NULL ;

         for (w=0 ; w<G->vexnum ; w++)

                   if (!Visited[w])

                   { 

                            ptr=DFStree(G, w) ;

                        if  (T==NULL)  T=ptr ;

                        else  q->nextsibling=ptr ;

                        q=ptr ;  

                   }

         return(T) ;

}