数据结构之图论（续）

2020-04-27 16:48

前言

在之前的推文中，我们了解了什么是图，以及一些图的DFS和BFS的基本操作，这一期本小编将继续为大家介绍一些关于图的基本算法，一起看下吧。

NO．1关节点和双联通域

在一个无向图G中，若将某个节点v去除之后后G所包含的连通域增多，则v称作切割节点（cut vertex或关节点（articulation point）。如果一个图不含任何关节点则称之为双连通图，最典型的就是完全图。任一无向图都可视作由若干个极大的双连通子图组合而成，这样的每一子图都称作原图的一个双连通域（bi－connected component）。例如下图中的节点3和5就是关节点。

较之其它顶点，关节点更为重要。在网络系统中它们对应于网关，决定子网之间能否连通。在航空系统中，某些机场的损坏，将同时切断其它机场之间的交通。故在资源总量有限的前提下，找出关节点并重点予以保障，是提高系统整体稳定性和鲁棒性的基本策略。接下来就让我们来看下求关节点的算法吧。

NO．2关节点算法

遇事不决先暴力，按照暴力来解决：首先，通过BFS或DFS搜索统计出图G所含连通域的数目；然后逐一枚举每个顶点v，暂时将其从图G中删去，并再次通过搜索统计出图G｛v｝所含连通域的数目。于是，顶点v是关节点，当且仅当图G｛v｝包含的连通域多于图G。这一算法需执行n趟搜索，耗时O（n（n ＋ e）），等它算出来黄花菜都凉了。

那我们先分析下，首先在DFS树上面，叶节点不可能是关节点，因为将叶节点删去后不会影响树的连通性。另外，如果根节点有两个及两个以上的分支，则根节点一定是关节点，因为DFS会将此节点以下的所有点加入到分支中，如果有多个分支则这些分支是不相互连通的。

现在考虑内部节点。若节点C的移除导致其某一棵（比如以D为根的）真子树与其真祖先（比如A）之间无法连通，则C必为关节点。反之，若C的所有真子树都能（如以E为根的子树那样）与C的某一真祖先连通，则C就不可能是关节点。那么只要在DFS搜索过程记录并更新各顶点v所能（经由后向边）连通的最高祖先（highest connected ancestor， HCA）hca［v］，即可及时认定关节点，并报告对应的双连通域。

思路出来了，那就是代码实现了

＃include