本节所讨论的内容是图的遍历算法的具体应用。

无向图的连通分量与生成树

对于无向图，对其进行遍历时：

若是连通图：仅需从图中任一顶点出发，就能访问图中的所有顶点；
若是非连通图：需从图中多个顶点出发。每次从一个新顶点出发所访问的顶点集序列恰好是各个连通分量的顶点集；

从任意点出发按DFS算法得到生成树称为深度优先生成树；按BFS算法得到的生成树称为广度优先生成树。

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

对图的深度优先搜索遍历DFS(或BFS)算法稍作修改，就可得到构造图的DFS生成树算法。在算法中，树的存储结构采用孩子—兄弟表示法。首先建立从某个顶点V出发，建立一个树结点，然后再分别以V的邻接点为起始点，建立相应的子生成树，并将其作为V结点的子树链接到V结点上。显然，算法是一个递归算法。算法实现：

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) ;
}

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*/

图的生成森林算法
```
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) ;
}
```
连通分量（Connected Component）

由定义可知，图的生成森林中的每一棵树都是图的一个连通分量，则可以改进BFS或DFS，在算法中加上一些标记即可将算法改进为求CC的Connected Component Labeling，具体代码和生成树或生成森林差别不大，不再赘述。

有向图的强连通分量

对于有向图，在其每一个强连通分量中，任何两个顶点都是可达的。任意的V属于G，与V可相互到达的所有顶点就是包含V的强连通分量的所有顶点。设从V可到达(以V为起点的所有有向路径的终点)的顶点集合为T1(G)，而到达V (以V为终点的所有有向路径的起点)的顶点集合为T2(G)，则包含V的强连通分量的顶点集合是： T1(G)∩T2(G) 。

Kosaraju算法

求有向图G的强连通分量的基本步骤是：
对G进行深度优先遍历，生成G的深度优先生成森林T。
对森林T的顶点按中序遍历顺序进行编号。
改变G中每一条弧的方向，构成一个新的有向图G’。
按2中标出的顶点编号，从编号最大的顶点开始对G’进行深度优先搜索，得到一棵深度优先生成树。若一次完整的搜索过程没有遍历G’的所有顶点，则从未访问的顶点中选择一个编号最大的顶点，由它开始再进行深度优先搜索，并得到另一棵深度优先生成树。在该步骤中，每一次深度优先搜索所得到的生成树中的顶点就是G的一个强连通分量的所有顶点。
重复步骤4，直到G’中的所有顶点都被访问。

在算法实现时，建立一个数组in_order[n]存放深度优先生成森林的中序遍历序列。对每个顶点v，在调用DFS函数结束时，将顶点依次存放在数组in_order[n]中。图采用十字链表作为存储结构最合适。

算法实现：

int in_order[MAX_VEX] ;
void  DFS(OLGraph *G , int v)  //  按弧的正向搜索
{  ArcNode  *p ;
   Count=0 ;
   Visited[v]=TRUE ;
   for  (p=G->xlist[v].firstout ; p!=NULL ; p=p->tlink)
   if  (!Visited[p->headvex])  
      DFS(G , p->headvex) ;
   in_order[count++]=v ;
} 
void  Rev_DFS(OLGraph *G , int v) 
{  ArcNode  *p ;
   Visited[v]=TRUE ;
   printf(“%d” , v) ;     /*  输出顶点  */
   for  (p=G->xlist[v].firstin ; p!=NULL ; p=p->hlink)
   if  (!Visited[p->tailvex]) 
      Rev_DFS(G , p->tailvex) ;
}    /*  对图G按弧的逆向进行搜索  */
void  Connected_DG(OLGraph *G)
{   int  k=1, v, j ; 
    for (v=0; v<G->vexnum; v++)  
        Visited[v]=FALSE ;
    for (v=0; v<G->vexnum; v++)    /*  对图G正向遍历  */
        if (!Visited[v])  DFS(G,v) ;     
    for (v=0; v<G->vexnum; v++)  
        Visited[v]=FALSE ;
    for (j=G->vexnum-1; j>=0; j--)    /*  对图G逆向遍历  */
    {  v=in_order[j] ;
       if (!Visited[v])
       {  printf(“\n第%d个连通分量顶点: ”, k++) ;
          Rev_DFS(G, v) ;
       }
    }
}

Tarjan算法

Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

算法思想

算法的关键在于如何判定某结点是否是强连通分量的根。注意“强连通分量的根”这一说法仅针对此算法，事实上强连通分量是没有特定的“根”的。在这里根结点指深度优先搜索时强连通分量中首个被访问的结点。

为找到根结点，我们给每个结点v一个深度优先搜索标号v.index，表示它是第几个被访问的结点。此外，每个结点v还有一个值v.lowlink，表示从v出发经有向边可到达的所有结点中最小的index。显然v.lowlink总是不大于v.index，且当从v出发经有向边不能到达其他结点时，这两个值相等。v.lowlink在深度优先搜索的过程中求得，v是强连通分量的根当且仅当v.lowlink = v.index。

算法说明

在栈里，当dfs遍历到v，而且已经遍历完v所能直接到达的顶点时，v.lowlink=v.index时，v一定能到达栈里v上面的顶点：因为当dfs遍历到v，而且已经dfs递归调用完v所能直接到达的顶点时（假设上面没有v.lowlink=v.index），这时如果发现v.lowlink=v.index，栈上面的顶点一定是刚才从顶点v递归调用时进栈的，所以v一定能够到达那些顶点。
dfs遍历时，如果已经遍历完v所能直接到达的顶点而v.lowlink=v.index，我们知道v一定能到达栈里v上面的顶点，这些顶点的lowlink一定小于自己的index，不然就会出栈了，也不会小于v.index,不然v.lowlink一定小于v.index,所以栈里v以其v以上的顶点组成的子图是一个强连通分量，如果它不是极大强连通分量的话v.lowlink也一定小于v.index（这里不再详细说），所以栈里v以其v以上的顶点组成的子图是一个极大强连通分量。

算法分析

因为所有的点都刚好进过一次栈，所有的边都访问的过一次，所以时间复杂度为O(n+m)。

Gabow算法

这个算法其实就是Tarjan算法的变异体，我们观察一下，只是它用第二个堆栈来辅助求出强连通分量的根，而不是Tarjan算法里面的index和lowlink数组。

算法思想

我们说一下如何使用第二个堆栈来辅助求出强连通分量的根。我们使用类比方法，在Tarjan算法中，每次v.lowlink的修改都是由于环的出现(不然，v.lowlink的值不可能变小)，每次出现环，在这个环里面只剩下一个v.lowlink没有被改变(深度最低的那个)，或者全部被改变，因为那个深度最低的节点在另一个环内。那么Gabow算法中的第二堆栈变化就是删除构成环的节点，只剩深度最低的节点，或者全部删除，这个过程是通过出栈来实现，因为深度最低的那个顶点一定比前面的先访问，那么只要出栈一直到栈顶那个顶点的访问时间不大于深度最低的那个顶点。其中每个被弹出的节点属于同一个强连通分量。那有人会问：为什么弹出的都是同一个强连通分量？因为在这个节点访问之前，能够构成强连通分量的那些节点已经被弹出了，这个对Tarjan算法有了解的都应该清楚，那么Tarjan算法中的判断根我们用什么来代替呢？想想，其实就是看看第二个堆栈的顶元素是不是当前顶点就可以了。现在，你应该明白其实Tarjan算法和Gabow算法其实是同一个思想的不同实现，但是，Gabow算法更精妙，时间更少(不用频繁更新v.lowlink)。

算法说明

找一个没有被访问过的节点v，goto 2 (v)。否则，算法结束。
(v): 将v压入堆栈stk1[]和stk2[] 对于v所有的邻接顶点u： a. 如果没有访问过，则call 2 (u) b. 如果访问过，但没有删除，维护stk2[](处理环的过程，出栈到u)
如果stk2[].top==v，那么stk1[]出栈输出相应的强连通分量，stk2[]出栈v。

整个递归过程需要好好在纸上划拉划拉。

算法分析

Gabow算法并没有改进多少Tarjan算法的时间复杂度，只是改进了一些原子操作的次数和复杂度，所以时间复杂度也是O(n+m)。

总结

Kosaraju算法的第二次深搜隐藏了一个拓扑性质，而Tarjan算法和Gabow算法省略了第二次深搜，所以，它们不具有拓扑性质。Tarjan算法用堆栈和标记，Gabow用两个堆栈（其中一个堆栈的实质是代替了Tarjan算法的标记部分）来代替Kosaraju算法的第二次深搜，所以只用一次深搜，效率比Kosaraju算法要高。

最小生成树

最小生成树在实际中具有重要用途，如设计通信网。设图的顶点表示城市，边表示两个城市之间的通信线路，边的权值表示建造通信线路的费用。n个城市之间最多可以建n*(n-1)/2条线路，如何选择其中的n-1条，使总的建造费用最低?

基本概念

如果连通图是一个带权图，则其生成树中的边也带权，生成树中所有边的权值之和称为生成树的代价。最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树。

基本性质

构造最小生成树的算法有许多，基本原则是：

尽可能选取权值最小的边，但不能构成回路；
选择n-1条边构成最小生成树。

以上的基本原则是基于MST的如下性质：设G=(V，E)是一个带权连通图，U是顶点集V的一个非空子集。若u∈U ，v∈V-U，且(u, v)是U中顶点到V-U中顶点之间权值最小的边，则必存在一棵包含边(u, v)的最小生成树。

证明：用反证法证明。设图G的任何一棵最小生成树都不包含边(u,v)。设T是G的一棵生成树，则T是连通的，从u到v必有一条路径(u,…,v)，当将边(u,v)加入到T中时就构成了回路。则路径(u, …,v)中必有一条边(u’,v’) ，满足u’∈U ，v’∈V-U 。删去边(u’,v’) 便可消除回路，同时得到另一棵生成树T’。由于(u,v)是U中顶点到V-U中顶点之间权值最小的边，故(u,v)的权值不会高于(u’,v’)的权值，T’的代价也不会高于T， T’是包含(u,v) 的一棵最小生成树，与假设矛盾。

普里姆(Prim)算法

从连通网N=(U，E)中找最小生成树T=(U，TE) 。

算法思想

若从顶点v0出发构造，U={v0}，TE={}；
先找权值最小的边(u，v)，其中u∈U且v∈V-U，并且子图不构成环，则U= U∪{v}，TE=TE∪{(u，v)}；
重复2 ，直到U=V为止。则TE中必有n-1条边， T=(U，TE)就是最小生成树。

算法实现说明

设用邻接矩阵(二维数组)表示图，两个顶点之间不存在边的权值为机内允许的最大值。为便于算法实现，设置一个一维数组closedge[n]，用来保存V- U中各顶点到U中顶点具有权值最小的边。数组元素的类型定义是：

struct 
{   int  adjvex ;     /*   边所依附于U中的顶点   */
    int  lowcost ;    /*   该边的权值   */
} closedge[MAX_EDGE] ;

例如： closedge[j].adjvex=k，表明边(vj, vk)是V-U中顶点vj到U中权值最小的边，而顶点vk是该边所依附的U中的顶点。 closedge[j].lowcost存放该边的权值。

假设从顶点vs开始构造最小生成树。初始时令：

Closedge[s].lowcost=0 ：表明顶点vs首先加入到U中；
Closedge[k].adjvex=s ，Closedge[k].lowcost=cost(k, s)：表示V-U中的各顶点到U中权值最小的边(k≠s) ，cost(k, s)表示边(vk, vs) 权值。

算法步骤

从closedge中选择一条权值(不为0)最小的边(vk, vj) ，然后做： a. 置closedge[k].lowcost为0 ，表示vk已加入到U中。 b. 根据新加入vk的更新closedge中每个元素： 任意的vi∈V-U ，若cost(i, k)≦colsedge[i].lowcost，表明在U中新加入顶点vk后， (vi, vk)成为vi到U中权值最小的边，置： Closedge[i].lowcost=cost(i, k) Closedge[i].adjvex=k
重复1 n-1次就得到最小生成树。

在Prime算法中，图采用邻接矩阵存储，所构造的最小生成树用一维数组存储其n-1条边，每条边的存储结构描述：

typedef struct MSTEdge
{  int  vex1, vex2 ;    /*  边所依附的图中两个顶点 */
   WeightType  weight ;     /*  边的权值  */
} MSTEdge ;

算法实现

#define INFINITY  MAX_VAL     /* 最大值 */ 
MSTEdge *Prim_MST(AdjGraph *G , int u)
      /*   从第u个顶点开始构造图G的最小生成树   */
{  MSTEdge TE[] ;  //  存放最小生成树n-1条边的数组指针
   int j , k , v , min ;
   for (j=0; j<G->vexnum; j++)
   {  closedge[j].adjvex=u  ; 
      closedge[j].lowcost=G->adj[j][u]  ;
   }    /*   初始化数组closedge[n]  */ 
   closedge[u].lowcost=0 ;      /*   初始时置U={u}  */ 
   TE=(MSTEdge *) malloc((G->vexnum-1) * sizeof(MSTEdge)) ;
   for (j=0; j<G->vexnum-1; j++)
   {   min= INFINITY ;
       for (v=0; v<G->vexnum; v++) 
          if  (closedge[v].lowcost!=0&& closedge[v].Lowcost < min)
          {  min=closedge[v].lowcost ; k=v ;  }
       TE[j].vex1=closedge[k].adjvex ; 
       TE[j].vex2=k ;
       TE[j].weight=closedge[k].lowcost ;
       closedge[k].lowcost=0 ;      /*   将顶点k并入U中  */
       for (v=0; v<G->vexnum; v++)
          if (G->adj[v][k] < closedge[v]. lowcost)
          {  closedge[v].lowcost= G->adj[v][k] ;
             closedge[v].adjvex=k ; 
          }  /*   修改数组closedge[n]的各个元素的值   */
   }
   return(TE) ;
}   /*   求最小生成树的Prime算法   */

算法分析

设带权连通图有n个顶点，则算法的主要执行是二重循环：求closedge中权值最小的边，频度为n-1；修改closedge数组，频度为n 。因此，整个算法的时间复杂度是O(n^2)，与边的数目无关。

克鲁斯卡尔(Kruskal)算法

算法思想

设G=(V, E)是具有n个顶点的连通网，T=(U, TE)是其最小生成树。初值：U=V，TE={} 。对G中的边按权值大小从小到大依次选取。

选取权值最小的边(vi，vj)，若边(vi，vj)加入到TE后形成回路，则舍弃该边(边(vi，vj)) ；否则，将该边并入到TE中，即TE=TE∪{(vi，vj)} 。
重复1 ，直到TE中包含有n-1条边为止。

算法实现说明

Kruskal算法实现的关键是：当一条边加入到TE的集合后，如何判断是否构成回路?

简单的解决方法是：定义一个一维数组Vset[n] ，存放图T中每个顶点所在的连通分量的编号。

初值：Vset[i]=i，表示每个顶点各自组成一个连通分量，连通分量的编号简单地使用顶点在图中的位置(编号)。
当往T中增加一条边(vi，vj) 时，先检查Vset[i]和Vset[j]值：
若Vset[i]=Vset[j]：表明vi和vj处在同一个连通分量中，加入此边会形成回路；
若Vset[i]≠Vset[j]，则加入此边不会形成回路，将此边加入到生成树的边集中。
加入一条新边后，将两个不同的连通分量合并：将一个连通分量的编号换成另一个连通分量的编号。

算法实现

MSTEdge *Kruskal_MST(ELGraph *G)
      /*   用Kruskal算法构造图G的最小生成树   */
{  MSTEdge TE[] ; 
   int  j, k, v, s1, s2, Vset[] ;
   WeightType  w ;
   Vset=(int  *) malloc(G->vexnum * sizeof(int)) ;
   for (j=0; j<G->vexnum; j++)
      Vset[j]=j  ;     /*   初始化数组Vset[n]  */ 
   sort(G->edgelist) ;   /*   对表按权值从小到大排序  */
   j=0 ; k=0 ;
   while (k<G->vexnum-1&&j< G->edgenum)
   {  s1=Vset[G->edgelist[j].vex1] ;
      s2=Vset[G->edgelist[j].vex2] ;
/*  若边的两个顶点的连通分量编号不同, 边加入到TE中  */
      if  (s1!=s2)
      {  TE[k].vex1=G->edgelist[j].vex1 ;
         TE[k].vex2=G->edgelist[j].vex2 ;
         TE[k].weight=G->edgelist[j].weight ;         
         k++ ;
         for (v=0; v<G->vexnum; v++)
             if  (Vset[v]==s2)  Vset[v]=s1 ;
      }
      j++ ;
   }
   free(Vset) ;  
   return(TE) ;
}     /*   求最小生成树的Kruskal算法   */

算法分析

设带权连通图有n个顶点，e条边，则算法的主要执行是：

Vset数组初始化：时间复杂度是O(n) ；
边表按权值排序：若采用堆排序或快速排序，时间复杂度是O(e㏒e) ；
while循环：最大执行频度是O(n)，其中包含修改Vset数组，共执行n-1次，时间复杂度是O(n^2) ；

整个算法的时间复杂度是O(e㏒e+n^2) 。

关节点和重连通分量

关节点（Articulation Point）、重连通图（Biconnected Graph）

假若在删去顶点v以及和v相关联的各边之后，将图的一个连通分量分割成两个或两个以上的连通分量，则称顶点v为该图的一个关节点(articulation point) 也称割点。一个没有关节点的连通图称为重连通图(biconnected graph) 。在重连通图上，任意一对顶点之间至少存在两条路径，则在删去某个顶点以及依附于该顶点的各边时也不破坏图的连通性。若在连通图上至少删去k个顶点才能破坏图的连通性，则称此图的连通度为k。关节点和重连通图在实际中较多应用。

图的关节点算法

利用深度优先搜索便可求得图的关节点，并由此可判别图是否是重连通的。

算法描述

在图的深优先生成树中，对树中任一顶点v而言，其孩子结点为在它之后搜索到的邻接点，而其双亲结点和由回边连接的祖先结点是在它之前搜索到的邻接点。由深度优先生成树可得出两类关节点的特性：

若生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点。因为图中不存在联结不同子树中顶点的边，因此，若删去根顶点，生成树便变成生成森林。
若生成树中某个非叶子顶点v，其某棵子树的根和子树中的其它结点均没有指向v的祖先的回边，则v为关节点。因为，若删去v，则其子树和图的其它部分被分割开来。

若对图Graph＝(V，{Edge})重新定义遍历时的访问函数visited，并引入一个新的函数low，则由一次深度优先遍历便可求得连通图中存在的所有关节点。

定义visited[v]为深度优先搜索遍历连通图时访问顶点v的次序号；定义：若对于某个顶点v，存在孩子结点w且low[w]≧visited[v]，则该顶点v必为关节点。因为当w是v的孩子结点时，low[w]≧visited[v]，表明w及其子孙均无指向v的祖先的回边。由定义可知，visited[v]值即为v在深度优先生成树的前序序列的序号，只需将DFS函数中头两个语句改为visited[v0]=++count（在DFSTraverse中设初值count=1）即可；low[v]可由后序遍历深度优先生成树求得，而v在后序序列中的次序和遍历时退出DFS函数的次序相同，由此修改深度优先搜索遍历的算法便可得到求关节点的算法。

void FindArticul(ALGraph G)
{ /* 连通图G 以邻接表作存储结构，查找并输出G 上全部关节点 */
    count=1; /* 全局变量count 用于对访问计数 */
    visited[0]=1; /* 设定邻接表上0 号顶点为生成树的根 */
    for(i=1;i<G.vexnum;++i) /* 其余顶点尚未访问 */
        visited[i]=0;
    p=G.adjlist[0].first;
    v=p->adjvex;
    DFSArticul(g,v); /* 从顶点v 出发深度优先查找关节点 */
    if(count<G.vexnum) /* 生成树的根至少有两棵子树 */
    {
        printf(0,G.adjlist[0].vertex); /* 根是关节点，输出 */
        while(p->next)
        {
            p=p->next;
            v=p->adjvex;
            if(visited[v]==0) DFSArticul(g,v);
        }
    }
} /* FindArticul */
void DFSArticul(ALGraph G,int v0)
/* 从顶点v0 出发深度优先遍历图G，查找并输出关节点 */
{
  visited[v0]=min=++count; /* v0 是第count 个访问的顶点 */
  for(p=G.adjlist[v0].firstedge; p; p=p->next;) /* 对v0 的每个邻接点检查 */
  {
    w=p->adjvex; /* w 为v0 的邻接点 */
    if(visited[w]==0) /* 若w 未曾访问，则w 为v0 的孩子 */
    {
      DFSArticul(G,w); /* 返回前求得low[w] */
      if(low[w] < min)
        min=low[w];
      if(low[w]>=visited[v0])
        printf(v0,G.adjlist[v0].vertex); /* 输出关节点 */
    }
    else if(visited[w]< min)
      min=visited[w]; /* w 已访问，w 是v0 在生成树上的祖先 */
  }
  low[v0]=min;
}

顺便提一句，上述算法中将指向双亲的树边也看成是回边，由于不影响关节点的判别，因此，为使算法简明起见，在算法中没有区别之。

算法分析

由于上述算法的过程就是一个遍历的过程，因此，求关节点的时间复杂度仍为O（n+e）。

这个算法和有向图的强连通分量算法Tarjan算法有点类似，具体细节请读者自己比较。

总结自：《数据结构（C语言版）》清华大学出版社严蔚敏、吴伟民编著

无向图的连通分量与生成树

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

连通分量（Connected Component）

有向图的强连通分量

Kosaraju算法

Tarjan算法

算法思想

算法说明

算法分析

Gabow算法

算法思想

算法说明

算法分析

总结

最小生成树

基本概念

基本性质

普里姆(Prim)算法

算法思想

算法实现说明

算法步骤

算法实现

算法分析

克鲁斯卡尔(Kruskal)算法

算法思想

算法实现说明

算法实现

算法分析

关节点和重连通分量

关节点（Articulation Point）、重连通图（Biconnected Graph）

图的关节点算法

算法描述

算法分析