本文主要是介绍无向图的割点（关节点），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
无向图的割点，也称关节点。对于无向图中不同的两点u，v，如果必须经过点w，才能构成一条从u到v的路径，那么称该w点就是割点（关节点）。关节点的求解只需要一次关于图的深度优先遍历（完成一次DFS等于生成一棵树，第一个访问的节点是根结点）。在这次DFS中，按照遍历的顺序记录每个点i的a，b表。其中，a表和b表的计算如下：
a[i]=predfn ; //predfn是点的深度遍历访问顺序，在深度遍历中一次确定
b[i]=min(a[i], b[j], a[j]); // （i，j）属于图的边
另外，还需要明白两个“边”概念：
1. 树边：（i,j）边，i已被访问，j未被访问。
2. 回边： （i,j）边，i和j均被访问，但j的访问顺序先于i，即a[j]>a[i]。同时，j不能是i的父节点，即a[j]-a[i]!=1.
清楚了上面的概念后，请看下面的伪代码（出自《算法设计与分析》中第九章中的9.3.3小结，免费书的链接http://download.csdn.net/detail/u010232171/8484509）
ps：书中的伪代码可能因为排版的问题，容易造成对代码的误解。现在将伪代码重新编辑一
这篇关于无向图的割点（关节点）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
