C# QuickGraph 的最小割算法

Question

我有一个带有节点和边的无向未加权图。我需要找到给定源节点和目标节点之间图形的所有可能的最小切割的集合/列表（切割是一组边，在删除的情况下，将图划分为 2 个不相交的较小图） 。我发现了很多关于可以完成此任务的算法的摘要文章，但是它们的描述要么太复杂，要么太模糊。我找到了 Karger、min S-T cut 或 Stoer-Wagner 算法的一些基本描述，但我不太明白算法中的 cut 应该是什么。

我使用 C# QuickGraph 来完成此任务，并决定编写自己的递归算法，但它没有按预期工作。

public class GraphHandler
{
    public UndirectedGraph<Node, Edge<Node>> Graph { get; private set; }
    private readonly List<List<Edge<Node>>> MinPaths = new();
    private readonly List<List<Edge<Node>>> MinCuts = new();
    private UndirectedDepthFirstSearchAlgorithm<Node, Edge<Node>> Algorithm;
    private UndirectedVertexPredecessorRecorderObserver<Node, Edge<Node>> Observer;

    public GraphHandler(UndirectedGraph<Node, Edge<Node>> graph)
    {
        Graph = graph;
    }

    public List<List<Edge<Node>>> AllMinCuts(Node Source, Node Target)
    {
        MinCuts.Clear();
        FindMinCuts(Graph.Clone(), Source, Target, new List<Edge<Node>>());
        var Cuts = MinCuts.OrderBy(Cut => Cut.Count).ToArray();
        var OtherCuts = MinCuts.ToArray();
        foreach (List<Edge<Node>> Cut in Cuts)
        {
            foreach(List<Edge<Node>> OtherCut in OtherCuts)
            {
                // If a cut isn't the same, and contains all edges of a small cut
                // Delete this cut form the list
                if (!Cut.Equals(OtherCut) && Cut.All(Edge => OtherCut.Contains(Edge)))
                {
                    MinCuts.Remove(OtherCut);
                }
            }
        }
        return MinCuts;
    }

    private void FindMinCuts(UndirectedGraph<Node, Edge<Node>> graph, Node Source, Node Target, List<Edge<Node>> Cut)
    {
        Algorithm = new(graph);
        Observer = new();
        Observer.Attach(Algorithm);
        Algorithm.Compute(Source);
        if (!Observer.TryGetPath(Target, out _))
        {
            MinCuts.Add(new List<Edge<Node>> (Cut));
            return;
        }
        var Edges = graph.Edges.ToArray();
        foreach (Edge<Node> edge in Edges)
        {
            if (!Cut.Contains(edge))
            {
                Cut.Add(edge);
                graph.RemoveEdge(edge);
                FindMinCuts(graph, Source, Target, Cut);
                graph.AddEdge(edge);
            }
        }
    }
}

更重要的是，这段代码很可能会因顶点过多而导致溢出异常，并且非常无效，但我不太明白替代方案。

Answer 1

拉米纸牌是一种用筹码玩的棋盘游戏。说明的简单性允许所有年龄段的玩家参与。每个游戏都是不同的，所以玩它总是有新的体验。游戏包括 4 种颜色的图块（黑色、红色、蓝色和黄色）。 https://rummybo.com/