分析数据结构编码（43） 关节点

首先需要明确一些基本概念：

关节点：在无向图中，若删除某一顶点及其相关联的边后，原本的一个连通分量被分割为两个或多个连通分量，则该顶点被称为关节点。

若一个无向图中不存在任何关节点，则该图被称为重连通图。在重连通图中，任意两个顶点之间至少存在两条独立路径。

如果需要删除一个连通图中的k个节点才能使其失去连通性，则称该连通图的连通度为k。

以下算法用于求解连通图的关节点，目前仅适用于连通图的情况，若要扩展至整个图的关节点计算，只需增加一个循环语句for i = 0,...,g.verNum即可。

关于求解关节点的方法，目前已知主要有两种：

1.定义法：依次移除连通图中的各个顶点，并对剩余部分进行深度优先遍历以判断其是否仍保持连通。假设图中共有n个顶点和e条边，则该方法的时间复杂度为O(n * (n + e))。

2.基于关节点特性的深度优先遍历法：利用关节点所具有的两个特性对整个图进行深度优先搜索。此方法的时间复杂度为O(n + e)。

显然第二种方法更为高效。

教材中详细介绍了关节点所具备的两种特性

以下代码的编写完全基于这