好吧，这是我在图中寻找割的算法(我不是在这里谈论最小割)
假设我们有一个无向图的邻接表。
- 选择图上的任意顶点(用枢轴表示)
- (随机)选择图上的任何其他顶点。 (用 x 表示)
- 如果两个顶点之间有一条边，则从图中删除这条边。并将 x 连接到的所有顶点转储到枢轴上。 (如果不是，则返回步骤 2。
- 如果任何其他顶点连接到 x，则更改邻接列表，以便现在 x 被枢轴替换。即它们连接到 Pivot。
- 如果顶点数大于2(回到第2步)
- 如果等于 2。只计算 2 个点中任何一个的邻接列表中存在的顶点数。这会给削减
我的问题是，这个算法是否正确？
最佳答案
这是对无向图的 Krager 最小割算法的一个很好的解释。
我认为您可能错过了一个细节。或者我只是误读了您的描述。
您想删除所有自循环。
例如，在您删除一个顶点并运行您的算法后，顶点 A 现在可能有一条从顶点 A 到顶点 A 的边。这称为自循环。并且它们在收缩两个顶点的过程中频繁产生。作为第一步，您可以简单地检查整个图形是否存在自环，但也有一些更复杂的方法。
这有意义吗？
关于algorithm - 用于在图中查找最小切割的随机收缩算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10055220/