基于C# QuickGraph的S-T最小割求解及算法优化咨询

先搞懂核心定义 #

你混淆的几种算法的割定义差异：

• S-T最小割：把图分成两个不相交子集，源s在其中一个，目标t在另一个，割的大小是连接两个子集的边数。你要找的是所有这类割中边数最少的集合。
• Karger/Stoer-Wagner：这俩是找全局最小割——任意节点对之间的最小割，不是针对特定s-t的，对你的需求不直接适用。
• 基于最大流的S-T割算法：根据最大流最小割定理，无向无权图中s-t的最大流值等于最小割的边数，这是解决你问题的核心依据。

替代方案：基于最大流的迭代式实现 #

你的递归算法栈溢出、效率低，直接换用迭代版Dinic算法计算最大流，再基于残留网络枚举所有最小割，完全规避递归问题。

步骤1：用Dinic算法算最大流与残留网络 #

Dinic是当前效率最高的最大流算法之一，适合大规模图，而且本身就是迭代为主的实现（即使保留部分递归逻辑，也是分层后的短路径，栈深度不会爆炸）。

无向图的每条边等价于两条容量为1的有向边，构建残留网络后：

• 最大流的值就是最小割的边数
• 残留网络中从s可达的节点集合S，和不可达的T（包含t），就是一个最小割

步骤2：枚举所有最小割 #

要找所有满足条件的S子集：

1. s ∈ S，t ∉ S
2. 连接S和T的边数等于最小割大小
3. S内的节点在残留网络中相互可达（没有被饱和边阻断）

枚举时必须用迭代式回溯/BFS，不能用递归，避免栈溢出。核心思路是：从初始的S集合出发，尝试将某些节点从S移到T，但要保证割的大小不变——只有当移动该节点后，新增的割边数等于减少的割边数时，才是有效的最小割。

C# 代码实现参考 #

1. 自定义无向图结构（也可以用QuickGraph替代） #

public class UndirectedGraph
{
    public Dictionary<int, List<int>> AdjacencyList { get; } = new();

    public void AddEdge(int u, int v)
    {
        if (!AdjacencyList.ContainsKey(u)) AdjacencyList[u] = new();
        if (!AdjacencyList.ContainsKey(v)) AdjacencyList[v] = new();
        AdjacencyList[u].Add(v);
        AdjacencyList[v].Add(u);
    }
}

2. 迭代版Dinic算法（彻底规避栈溢出） #

public class Dinic
{
    private class Edge
    {
        public int To { get; }
        public int Rev { get; }
        public int Capacity { get; set; }
        public Edge(int to, int rev, int capacity) => (To, Rev, Capacity) = (to, rev, capacity);
    }

    private readonly List<List<Edge>> _graph;
    private readonly int[] _level;
    private readonly int[] _ptr;

    public Dinic(int nodeCount)
    {
        _graph = new List<List<Edge>>(nodeCount);
        for (int i = 0; i < nodeCount; i++) _graph.Add(new());
        _level = new int[nodeCount];
        _ptr = new int[nodeCount];
    }

    public void AddEdge(int from, int to, int capacity)
    {
        _graph[from].Add(new Edge(to, _graph[to].Count, capacity));
        _graph[to].Add(new Edge(from, _graph[from].Count - 1, capacity));
    }

    private bool Bfs(int s, int t)
    {
        Array.Fill(_level, -1);
        _level[s] = 0;
        var q = new Queue<int>();
        q.Enqueue(s);
        while (q.Count > 0)
        {
            int u = q.Dequeue();
            foreach (var edge in _graph[u])
            {
                if (edge.Capacity > 0 && _level[edge.To] == -1)
                {
                    _level[edge.To] = _level[u] + 1;
                    q.Enqueue(edge.To);
                    if (edge.To == t) return true;
                }
            }
        }
        return false;
    }

    // 迭代版DFS，彻底避免栈溢出
    private int IterativeDfs(int s, int t, int flow)
    {
        var stack = new Stack<(int u, int ptr, int currentFlow, List<(Edge edge, int pushed)> path)>();
        stack.Push((s, 0, flow, new List<(Edge, int)>()));
        int totalPushed = 0;

        while (stack.Count > 0)
        {
            var (u, ptr, currentFlow, path) = stack.Pop();
            if (u == t)
            {
                totalPushed = currentFlow;
                foreach (var (edge, pushed) in path)
                {
                    edge.Capacity -= pushed;
                    _graph[edge.To][edge.Rev].Capacity += pushed;
                }
                break;
            }
            for (; ptr < _graph[u].Count; ptr++)
            {
                var edge = _graph[u][ptr];
                if (edge.Capacity > 0 && _level[edge.To] == _level[u] + 1)
                {
                    int pushed = Math.Min(currentFlow, edge.Capacity);
                    var newPath = new List<(Edge, int)>(path) { (edge, pushed) };
                    stack.Push((u, ptr + 1, currentFlow, path));
                    stack.Push((edge.To, 0, pushed, newPath));
                    break;
                }
            }
        }
        return totalPushed;
    }

    public int MaxFlow(int s, int t)
    {
        int total = 0;
        while (Bfs(s, t))
        {
            Array.Fill(_ptr, 0);
            while (int pushed = IterativeDfs(s, t, int.MaxValue))
                total += pushed;
        }
        return total;
    }

    public HashSet<int> GetReachableNodes(int s)
    {
        var reachable = new HashSet<int>();
        var q = new Queue<int>();
        q.Enqueue(s);
        reachable.Add(s);
        while (q.Count > 0)
        {
            int u = q.Dequeue();
            foreach (var edge in _graph[u])
            {
                if (edge.Capacity > 0 && !reachable.Contains(edge.To))
                {
                    reachable.Add(edge.To);
                    q.Enqueue(edge.To);
                }
            }
        }
        return reachable;
    }
}

3. 枚举所有最小割的核心逻辑 #

public static List<HashSet<int>> EnumerateAllMinSTCuts(UndirectedGraph graph, int s, int t)
{
    int maxNodeId = graph.AdjacencyList.Keys.Max();
    var dinic = new Dinic(maxNodeId + 1);
    
    // 向Dinic添加所有边（无向边转双向有向边）
    foreach (var (u, neighbors) in graph.AdjacencyList)
    {
        foreach (var v in neighbors)
        {
            if (u < v) dinic.AddEdge(u, v, 1);
        }
    }

    int minCutSize = dinic.MaxFlow(s, t);
    var initialCut = dinic.GetReachableNodes(s);
    var allCuts = new List<HashSet<int>> { new(initialCut) };

    // 迭代式枚举所有可能的最小割：
    // 1. 找出残留网络中s可达的节点集合
    // 2. 尝试将集合中的节点移到T侧，检查割大小是否仍为minCutSize
    // 3. 若满足则加入结果集，继续迭代处理新的集合
    // 这里给出框架，具体实现需要根据你的图规模调整优化

    return allCuts;
}

关键注意点 #

• 节点数量大时，最小割的数量可能是指数级的，要评估是否真的需要全部枚举，或者只取代表性的割
• 所有递归逻辑必须替换为迭代实现，彻底避免栈溢出
• 如果用QuickGraph，它自带Dinic算法实现，直接调用即可，不用自己写，但要注意其API的使用方式，避免触发递归逻辑

内容的提问来源于stack exchange，提问作者Denis Berezniuk