流网络中的临界边和瓶颈边(最大流/最小割集问题)

def ford_fulkerson(graph, source, sink):
    def bfs(graph, s, t, parent):
        visited = set()
        queue = []
        queue.append(s)
        visited.add(s)
        while queue:
            u = queue.pop(0)
            for ind, val in enumerate(graph[u]):
                if val > 0 and ind not in visited:
                    queue.append(ind)
                    visited.add(ind)
                    parent[ind] = u
                    if ind == t:
                        return True
        return False

    max_flow = 0
    parent = [-1] * len(graph)
    while bfs(graph, source, sink, parent):
        path_flow = float("Inf")
        s = sink
        while s != source:
            path_flow = min(path_flow, graph[parent[s]][s])
            s = parent[s]
        max_flow += path_flow
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            graph[v][u] += path_flow
            v = u
    return max_flow

# Example usage
graph = [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0]
]
source = 0
sink = 5
print("Max Flow:", ford_fulkerson(graph, source, sink))