给定一个只有一个顶点的无权图，那唯一一个顶点是不是割点？

Question

删除图中那唯一一个顶点后，整个图的连通分量数量从 1 变成 0。根据割点的定义，这个顶点是割点？
看了视频后，感觉视频代码中没有处理「无权图中一些连通分量中只有一个顶点」的情况。
或许我理解有误？

Answer 1

liuyubobobo 2022-10-03 12:31:53

大赞！非常棒的观察！

这个问题本身还是要归于割点如何定义了。如果按照我在 PPT 上的定义，这个唯一的顶点确实叫割点。

我查了一下，我在 PPT 中的定义确实不是严谨的拓扑学上的割点定义。所以这里我给出的定义有误。

严谨的拓扑学上的割点定义如下：

在一个联通图 X 中（即一个非联通的图不存在“割点”的概念。但你可以拿出一个联通分量，求这个联通分量的割点。）割点 p 满足，X - {p} （即从 X 中删除点 p，对应 p 相应的边也都删除了）不再联通。

在这个定义下，你说的这种情况，这个唯一的顶点不是割点。

==========

根据这个定义，这个割点的类要重新封装：

1）确认传来的整个图只有一个联通分量，否则抛异常；

2）只调用一次 dfs 即可，得到这个连通图的割点；

否则，如果在一个图中（可能非联通），求解图中所有的是删除会影响图的联通分量个数的点，应该特判一下只有一个顶点的联通分量（也加入到解中。）

课程的代码相当于是在求解每一个联通分量的割点的并集。（确实有些奇怪）

有时间我更新一下课程的这部分内容。

感谢提醒，继续加油！：）

• 提问者 慕村510262 #1

  现在我的疑问变成是:一个没有任何顶点和边的图，到底应该说它是连通的还是不连通的？（我也知道纠结这个意义不大，就是心里有点小纠结）

• liuyubobobo 回复 提问者 慕村510262 #2

  一个空图没有任何联通分量，所以也就没有联通还是不连通的概念。