生成树

生成树：如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。
生成树是连通图的包含图中的所有顶点的极小连通子图,图的生成树不惟一(极小子图是指边数最少的子图，任意一个具有n个顶点的连通图至少含有n-1条边，具有n-1条边的连通图必是一棵树，因此n个顶点的生成树包含n-1条边)，从不同的顶点出发进行遍历，可以得到不同的生成树,当采用深度搜索构造生成树时，则该生成树称为深度优先生成树，若采用广度搜索构造生成树时，则该生成树称为广度优先生成树。
关节点：图G中当地一个顶点v，如果删除v以及v上所有边后，得到的新图G‘至少包含两个联通分支。
双联通图：没有关节点的连通图，连通无向图G的双连通分支是图G中的一个最大双连通子图。
在深度优先搜索中，顶点的访问顺序为每个顶点的深度优先编号，在一个深度优先生成树中，如果顶点u是顶点v的祖先顶点,$dfn(v)<dfn(u)$，在图中，非树边为（u,v）为回退边。
当且仅当，深度优先搜索生成树根结点至少有两个儿子，他就是一个关节点，而任何顶点u非关节点，当且仅当u至少有一个儿子w，从w出发，不能通过w的后代顶点个一条回退边到达u的祖先顶点，low(u)等于从u出发，经过一条后代顶点路径和一条回退边，所能到达的具有最小深度优先编号的即：
low（u）=min{dfn(u)，min{low(w),w是u的儿子}，min{dfn(w)|(u,w)是一条回退边}}。
因此，判断顶点u是否为关节点的方法是:如果顶点u是生成树的根顶点，切u至少有两个儿子，则u是关节点，如果u不是根顶点，那么当且仅当u有一个儿子w，使得low(w)>=dfn(u),则u是关节点。
如图所示：




寻找图G的双连通分支的伪代码实现：

#define MIN2(x,y) ((x)<(y)? (x):(y))//返回较小的数
#define MAX_VERTCES 50
short int dfn[MAX_VERTCES];//对应顶点访问顺序，即深度优先编号
short int low[MAX_VERTCES];// 从对应顶点出发所能到达的具有最小深度优先编号顶点的编号
int num;//顶点编号赋值
//初始化
void init()
{
   int i;
   for(i=0;i<n;i++)
   {
      visited[i]=FALSE;
      dfn[i]=low[i]=-1;
   }
   num=0;
}
//v是u父节点
void bicon(int u,int v)
{
   node_pointer ptr;//图的结点
   int w,x,y;
   dfn[u]=low[u]=num++;
   for(ptr=graph[u];ptr;ptr=ptr->link)
   {
      w=ptr->vertex;//结点值
      if(v!=w&&dfn[w]<dfn[u])
         add(&top,u,w);//第一次遇到该边时，保存入栈
      //若没有访问过
      if(dfn[w]<0)
      {
         bicon(w,w);
         //获得对应顶点能到达最小深度优先编号的顶点
         low[u]=MIN2(low[u],low[w]);
         //若碰到关节点，则输出图子连通分支的边
         if(low[w]>=dfn[u])
         {

            printf("New biconnected component:");
            do
            {
               // 出栈
               delete(&top,&x,&y)；
               printf("<%d,%d>",x,y);
            }while(!((x==u)&&(y==w)));//直到输出其最后一条边
            printf("\n");
         }
      }
      else if(w!=v) low[u]=MIN2(low[u],dfn[w]);//经过其回退边
   }
}