好的，这里是我关于在图形中查找割点的算法（我不是在谈论最小割）的算法：
假设我们有一个非定向图的邻接列表。
我的问题是，这个算法正确吗？
这是一个关于无向图的 Krager 最小割算法的很好的解释。
我觉得可能有一个细节你忽略了，或者说我没有看清你的描述。
你需要移除所有自环。
例如，在你移除一个顶点并运行算法之后，顶点 A 可能现在有一条从顶点 A 到顶点 A 的边。这被称为自环。在缩小两个顶点的过程中，它们通常会产生。作为第一步，你可以简单地检查自环是否存在于整个图中，虽然也有一些更复杂的方法。
这样说你明白了吗？
using System;
using System.Collections.Generic;
using System.Linq;
namespace MinCut
{
internal struct Graph
{
public int N { get; private set; }
public readonly List<int> Connections;
public Graph(int n) : this()
{
N = n;
Connections = new List<int>();
}
public override bool Equals(object obj)
{
return Equals((Graph)obj);
}
public override int GetHashCode()
{
return base.GetHashCode();
}
private bool Equals(Graph g)
{
return N == g.N;
}
}
internal sealed class GraphContraction
{
public static void Run(IList<Graph> graphs, int i)
{
var liveGraphs = graphs.Count;
if (i >= liveGraphs)
{
throw new Exception("Wrong random index generation; index cannot be larger than the number of nodes");
}
var leftV = graphs[i];
var r = new Random();
var index = r.Next(0, leftV.Connections.Count);
var rightV = graphs.Where(x=>x.N == leftV.Connections[index]).Single();
foreach (var v in graphs.Where(x => !x.Equals(leftV) && x.Connections.Contains(leftV.N)))
{
v.Connections.RemoveAll(x => x == leftV.N);
}
foreach (var c in leftV.Connections)
{
if (c != rightV.N)
{
rightV.Connections.Add(c);
int c1 = c;
graphs.Where(x=> x.N == c1).First().Connections.Add(rightV.N);
}
}
graphs.Remove(leftV);
}
}
}