时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

• 双连通分量(Biconnected-Components)

双连通图定义为没有割点的图。双连通图的极大子图就为双连通分量。双连通分量就是在割点分割成多个连通分量处，共享割点。也就是说双连通分量是去掉割点后构成的连通分量，加上割点和到达割点的边。可以看出，双连通分量可分为不含有割点、一个割点、两个割点三种情况。对于不含有割点，说明图为双连通图。对于含有一个割点，可能为初始搜索的顶点到第一个割点之间的边构成的双连通分量，可能为遇到一个割点后到不再遇到割点之间的边构成双连通分量。对于含有两个割点，两个割点之间的边构成了一个双连通分量。

求解此问题，只要在求割点的算法上做更改就可以了。按照求割点的算法求解割点，找到一个割点，输出找到的边，然后删除找到的边的记录，再去搜索下一个割点。每搜索完图某个顶点的可达顶点，输出找到的边。这样就涵盖了所有的情况。

伪代码：
BICONNECTED-COMPONENTS(g)
  let disc be new Array
  let low be new Array
  let stack be new Stack
  let parent be new Array
  for i from 1 to the number of vertex in g
    disc [i] = -1
    low [i] = -1
    parent [i] = -1
  end
  for u from 1 to the number of vertex in g 
    if disc[i] == -1
      BICONNECTED-COMPONENTS-UTIL(u,disc,low,stack,parent)
    let flag = flase
    while stack.empty() == false
      flag = true
      print stack.top().src -> stack.top().des
      stack.pop()
    end
    if flag == true
      print '\n Found a Bioconnected-Components \n'
  end
  
BICONNECTED-COMPONENTS-UTIL(u,disc,low,stack,parent)
  let time be static
  time = time + 1
  let children = 0
  disc[u] = low[u] = time
  for v equal to every vertex adjacent to u
    if disc[v] == -1
      children = children + 1
      parent[v] = u
      stack.push(u->v)
      BICONNECTED-COMPONENTS-UTIL(u,disc,low,stack,parent)
      low[u] = min(low[u],low[v])
      if (parnet[u] == -1 and children > 1) or (parent[u] != -1 and low[v] >= disc[u])
        while stack.top().src != u or stack.top().des != v
          print stack.top().src -> stack.top().des
          stack.pop()
        end
        print stack.top().src -> stack.top().des
        stack.pop()
        print '\n Found a Bioconnected-Components \n'
    else if v != parent[u] and disc[v] < low[u]
      low[u] = min(low[u],disc[v])
      stack.push(u->v)
  end

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

最小生成树(Minimum-Spanning-Tree)

生成树是指，在一个连通、无向、有权的图中，所有顶点构成的一颗树。图中可以有多颗生成树，而生成树的代价就是树中所有边的权重的和。最小生成树就是生成树中代价最小的。

朴素的想法就是从图中选择最小权重的边，直到生成一颗树。看通用的算法之前，同样要讨论一下最小生成树的性质。

对于一个连通、无向、有权图中，一定有最小生成树。如果图不包含最小生成树的任意一条边，那么图就是不连通的了，这与已知连通图不符，所以图必包含最小生成树。

假设，A为某个最小生成树的子集(任意一个顶点都是最小生成树的子集)。

那么，为A一直添加对的边，A最后就会成为一颗最小生成树。那么最小生成树问题就转换成为了，一直找到对的边，直到成为一颗最小生成树。这个对的边可以叫做安全边。

安全边如何寻找显然就成了解决这个问题的关键点。

再假设，图中所有顶点为V，将所有顶点切割成两个部分S和V减去S。所有连接这两个部分的边，很形象的叫做横跨切割，这些边横跨了两个部分，成为这两个部分的桥梁。这里还有个问题，如何切割？使A不包含横跨切割。这样的切割有多种切法，切割后，横跨切割的最小代价边就为A的安全边。将这个作为定理1。

定理1：存在这样一个将所有顶点分成两个部分的切割，且使某个最小生成树子集A不包含横跨切割。则横跨此切割的最小代价边，就是A的安全边。

以下为此定理的证明，这个定理的基础实际上是连通性。

命题：横跨切割的最小代价边为A的安全边。

假设：横跨切割后的最小代价边为x，有最小生成树T包含A，但是不包含x。

证明：既然T不包含x，那么T必须包含另一条连接x两端顶点的路径，这条路径上又必须有条边横跨切割。假设这条边为y。T将y减去后，x两端的顶点就无法互相到达。这时如果再加上x，那么x两端的顶点又可以互相到达，并且构造了另一颗生成树T’。可以看到，x的代价小于或等于y的代价，那么T‘的代价也小于或等于T的代价，那么T’也就是一颗最小生成树。那么x既不在A中，x又在一颗包含A的最小生成树中。命题得证。

可以看到这个证明过程使用的就是经常拿来证明贪心选择的技巧，也就是说最小生成树问题符合贪心算法的特征，也就解释了为什么下面将要提到的两个算法都是贪心算法。

定理1还可以进行推论，既然切割有多种方法，那可不可以对A和其余的顶点进行切割，设B为包括A和所有顶点构成的一个森林，C是其中的一个连通分量，那么C连接其他的连通分量的最小代价边是A的安全边。这个推论很好证明，因为A是B中的一个或者多个连通分量，如果按照C去切割图分成C和B减去C，不可能切割A，即A中必定不包含横跨切割。那么，横跨这个切割的最小代价边就是安全边，即C连接其他连通分量的最小代价边，推论成立。将这个推论作为推论1。

推论1:某个最小生成树子集A和其他顶点构成的森林中，任意一个连通分量连接其他连通分量的最小代价边都为A的安全边。

如果从所有不在A中的边选择最小代价的边，这个边一定连接着某个连通分量，这个推论也就将选安全边的范围拓展到任意一条不在A中的边。这个推论正好可以证明朴素想法的正确性。

接下来看一下最小生成树的三个通用的算法Kruskal、Prime、Boruvka。

• Kruskal