给定一个只有一个顶点的无权图，那唯一一个顶点是不是割点？
来源：8-7 实现寻找割点算法
慕村510262
2022-10-03
删除图中那唯一一个顶点后，整个图的连通分量数量从 1 变成 0。根据割点的定义，这个顶点是割点？
看了视频后，感觉视频代码中没有处理「无权图中一些连通分量中只有一个顶点」的情况。
或许我理解有误？
写回答
1回答
-
liuyubobobo
2022-10-03
大赞！非常棒的观察！
这个问题本身还是要归于割点如何定义了。如果按照我在 PPT 上的定义，这个唯一的顶点确实叫割点。
我查了一下，我在 PPT 中的定义确实不是严谨的拓扑学上的割点定义。所以这里我给出的定义有误。
严谨的拓扑学上的割点定义如下：
在一个联通图 X 中（即一个非联通的图不存在“割点”的概念。但你可以拿出一个联通分量，求这个联通分量的割点。）割点 p 满足，X - {p} （即从 X 中删除点 p，对应 p 相应的边也都删除了）不再联通。
在这个定义下，你说的这种情况，这个唯一的顶点不是割点。
==========
根据这个定义，这个割点的类要重新封装：
1）确认传来的整个图只有一个联通分量，否则抛异常；
2）只调用一次 dfs 即可，得到这个连通图的割点；
否则，如果在一个图中（可能非联通），求解图中所有的是删除会影响图的联通分量个数的点，应该特判一下只有一个顶点的联通分量（也加入到解中。）
课程的代码相当于是在求解每一个联通分量的割点的并集。（确实有些奇怪）
有时间我更新一下课程的这部分内容。
感谢提醒，继续加油！：）
022022-10-03
相似问题