The Connectivity of Graph
利用遍历图的算法求解图的连通性问题，并讨论最小代价生成树以及重连通性与通信网络的经济性和可靠性关系。
本文主要内容：
- 无向图的连通分量和生成树
- 有向图的强连通分量
- 最小生成树
- 关节点和重连通分量
无向图的连通分量和生成树
如何对无向图进行遍历：
- 连通图：从图中任一顶点出发，进行dfs或bfs，便可访问到图中所有顶点；
- 非连通图：需要从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。
关于分连通图的遍历，起始就是不断循环的几个步骤：找到一个未被遍历的点；从此点开始dfs或者bfs直到所有相邻的点都被搜索到。(如此两步，不停循环)
【极小连通子图】设E(G)为连通图G中所有边的集合，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T(G)和B(G)，其中T(G)是遍历图过程中历经的边的集合，B(G)是剩余的边的集合。显然，T(G)和图G中所有顶点一起构成连通图G的极小连通子图(而且，此连通子图为连通图的一棵生成树，并且称由dfs得到的为深度优先生成树，由bfs得到的是广度优先生成树)。
从上面描述来看，同一图G的极小连通子图并不一定唯一。
对于非连通图，每个连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。
有向图的强连通分量
dfs是求有向图的连通分两的一个新的有效方法。
每一次调用dfs作逆向深度优先遍历所访问到的顶点集便是有向图G中一个强连通分量的顶点集。
【大白话描述】第一步，正常的来一遍dfs，并将每个dfs的路径一次记录下来；第二步，在每条路径中，找到路径中的最后一个点，dfs到的顶点们构成的集合即为强连通分量的顶点集，若为空，则换到路径中倒数第二个顶点，如此循环…直到找到强连通分量的顶点集。 (再简单地说，第一步正向dfs，第二步逆向dfs，联想关于强来南通) 第上述的第二步中，所得深度优先生成森林中每一棵树的顶点集即为G的强连通分量的顶点集。
显然，利用遍历求强连通分量和遍历的时间复杂度相同。
最小生成树
【MST性质】假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边，其中，则必存在一棵包含边
(u,v)的最小生成树。
下面介绍两种利用MST性质构造最小生成树的算法：
- Prim算法
- Kruskal算法
（下面由例子来说明两种算法）
【Prim算法】
【Kruskal算法】
【两种算法的总结】Prim算法说白了就是俩集合，一个连起来了的集合A，一个散的点的集合B，每次找到一个集合B中离集合A最近的点p，连接p和集合A中最近的点，把p加入集合A中(也要把p从集合B中删去)；Kruscal算法从长度最小边开始选择，只要不能构成一个回路就将其纳入最小生成树的体系，直到结点都被纳入最小生成树的体系。
【优劣】Prim算法的时间复杂度为O(n^2)(n为结点的频度)，与网中的边数无关，因此适用于求边稠密的网的最小生成树；而Kruscal算法的时间复杂度为O(eloge)(e为网中边的数目)，因此它相对于Prim算法来说，更适合于边稀疏的网的最小生成树。
关节点和重连通分量
【关节点(articulation point)(也叫割点)】假若在删去顶点v以及和v相联的各边之后，将图的一个连通分量分隔成两个或两个以上的连通分量，则称顶点v为该图的一个关节点。
【重连通分量(biconnected graph)】一个没有关节点的连通图。
在重连通图上，任意一对顶点之间至少存在两条路径 -> 删去某个顶点以及依附于该顶点的各边时也不破坏图的连通性。
【连通度】若在连通图上至少删去k个顶点才能破坏图的连通性，则称此图的连通度为k。
关节点的两类特性：
- 若生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点。如下图中的A。
- 若生成树中某个非叶子顶点v，其某棵子树的根和子树中的其他结点均没有指向v的祖先的回边，则为关节点。如下图中的B、D、G。
