用 Python 实现最小割算法：Ford-Fulkerson 和 Stoer-Wagner

def ford_fulkerson(graph, source, sink):

    # 残量图
    residual_graph = [[0 for _ in range(len(graph))] for _ in range(len(graph))]
    for i in range(len(graph)):
        for j in range(len(graph)):
            residual_graph[i][j] = graph[i][j]

    parent = [-1] * len(graph)

    # bfs遍历寻找增广路径
    def bfs(start, end):
        visited = [False] * len(graph)
        visited[start] = True
        queue = []
        queue.append((start))

        while queue:
            u = queue.pop(0)
            for v in range(len(graph)):
                if not visited[v] and residual_graph[u][v] > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u
        return visited[end]

    max_flow = 0

    while bfs(source, sink):
        flow = float("inf")
        v = sink
        while v != source:
            u = parent[v]
            flow = min(flow, residual_graph[u][v])
            v = u

        v = sink
        while v != source:
            u = parent[v]
            residual_graph[u][v] -= flow
            residual_graph[v][u] += flow
            v = u

        max_flow += flow

    return max_flow, parent

def min_cut_ford_fulkerson(graph):

    n = len(graph)
    source = 0
    sink = n - 1

    # 首先获取源点到汇点的最大流量
    max_flow, parent = ford_fulkerson(graph, source, sink)

    # 找出剩余的不连通部分
    min_cut = []
    visited = [False] * n
    visited[source] = True
    queue = []
    queue.append(source)

    while queue:
        u = queue.pop(0)
        for v in range(len(graph)):
            if not visited[v] and graph[u][v] > 0:
                queue.append(v)
                visited[v] = True

    # 拆分为两个不连通的部分
    for u in range(n):
        for v in range(n):
            if visited[u] and not visited[v] and graph[u][v] > 0:
                min_cut.append((u, v))

    return min_cut

def min_cut_stoer_wagner(graph):

    n = len(graph)

    # 初始化顶点集合
    vertices = [i for i in range(n)]

    # 初始化最小割为正无穷大
    min_cut = float('inf')

    while len(vertices) > 1:
        # 初始化每个点的电荷值为0
        charge = [0] * n

        # 重复n-1次计算最短跨越边
        for i in range(n - 1):
            # 初始化最小边权为正无穷大
            min_edge = float('inf')

            # 选择最小边权的跨越边
            for u in vertices:
                if charge[u] > 0:
                    for v in vertices:
                        if charge[v] == 0 and graph[u][v] < min_edge:
                            min_edge = graph[u][v]
                            min_u = u
                            min_v = v

            # 更新电荷值
            charge[min_v] += min_edge

        # 切分点
        cut_vertex = vertices[1]

        # 初始化最小割点集为空
        min_cut_vertices = []

        # 将每个点归入到源点or汇点中
        source, sink = vertices[0], cut_vertex
        visited = [False] * n
        visited[source] = True
        for _ in range(n - 1):
            visited[cut_vertex] = True

            # 将cut_vertex归入到源点集合（以source为代表）
            min_cut_vertices.append(cut_vertex)

            # 查找下一个切割点，谁的电荷值最大就归他
            max_charge = -float('inf')
            for u in vertices:
                if not visited[u]:
                    charge[u] += graph[cut_vertex][u]
                    if charge[u] > max_charge:
                        max_charge = charge[u]
                        next_cut_vertex = u

            cut_vertex = next_cut_vertex

        # 记录最小割
        cut = 0
        for u in min_cut_vertices:
            for v in range(n):
                if v not in min_cut_vertices:
                    if graph[u][v] > 0:
                        cut += graph[u][v]

        if cut < min_cut:
            min_cut = cut

        # 缩小顶点集合
        vertices.remove(cut_vertex)

        # 合并切割点前的所有点
        for u in range(n):
            graph[source][u] += graph[cut_vertex][u]
            graph[u][source] += graph[u][cut_vertex]

    return min_cut