好的,这里是我关于在图形中查找割点的算法(我不是在谈论最小割)的算法:
假设我们有一个非定向图的邻接列表。
- 在图上选择任何一个顶点(称为枢轴)
- 在图上随机选择另一个顶点(将其表示为 x)
- 如果这两个顶点之间有一条边,则从图中删除该边。并将 x 连接到的所有顶点转移到枢轴上。(如果没有,则返回步骤 2。)
- 如果其他任何顶点都连接到了 x,则更改邻接列表,使现在 x 被替换为枢轴。也就是说,它们与枢轴相连。
- 如果顶点数量大于 2(返回步骤 2)
- 如果等于 2。只需计算两个点中任意一个的邻接列表中存在的顶点数。这将给出割。
我的问题是,这个算法正确吗?