给我写一个用Python实现的最小割算法

以下是用Python实现的最小割算法，基于 Stoer-Wagner 算法：

import random

def min_cut(graph):
    n = len(graph)
    # 初始化点集和边集
    vertices = [i for i in range(n)]
    edges = []
    for i in range(n):
        for j in range(i+1, n):
            if graph[i][j] > 0:
                edges.append((i, j))

    while len(vertices) > 1:
        # 随机选择一个点作为源点
        s = random.choice(vertices)
        # 初始化两个集合
        A = [s]
        B = [v for v in vertices if v != s]
        # 初始化两个集合的权值和
        wA = [0] * n
        wB = [0] * n

        while len(B) > 0:
            # 找到连接A和B的最小横切边
            min_cut_edge = (-1, -1)
            min_cut_weight = float('inf')
            for i, j in edges:
                if i in A and j in B and graph[i][j] < min_cut_weight:
                    min_cut_edge = (i, j)
                    min_cut_weight = graph[i][j]
                elif j in A and i in B and graph[j][i] < min_cut_weight:
                    min_cut_edge = (j, i)
                    min_cut_weight = graph[j][i]

            # 将该边的两个端点合并到同一个集合中
            if min_cut_edge[0] in A:
                A.append(min_cut_edge[1])
                B.remove(min_cut_edge[1])
                for i in range(n):
                    wA[i] += graph[min_cut_edge[1]][i]
                    wB[i] -= graph[min_cut_edge[1]][i]
            else:
                B.append(min_cut_edge[0])
                A.remove(min_cut_edge[0])
                for i in range(n):
                    wB[i] += graph[min_cut_edge[0]][i]
                    wA[i] -= graph[min_cut_edge[0]][i]

        # 计算剩余边的权值
        cut_weight = 0
        for i in range(n):
            if i in B:
                cut_weight += wB[i]

        # 删除该点和与该点相连的所有边
        vertices.remove(s)
        new_graph = [[0] * (len(vertices)) for _ in range(len(vertices))]
        for i in range(len(vertices)):
            for j in range(i+1, len(vertices)):
                new_graph[i][j] = graph[vertices[i]][vertices[j]]
                new_graph[j][i] = graph[vertices[j]][vertices[i]]

        # 更新边集
        edges = []
        for i in range(len(vertices)):
            for j in range(i+1, len(vertices)):
                if new_graph[i][j] > 0:
                    edges.append((i, j))

        # 更新图
        graph = new_graph

    # 返回最小割的权值
    return cut_weight

使用方法：

graph = [[0, 2, 3, 4],
         [2, 0, 1, 0],
         [3, 1, 0, 5],
         [4, 0, 5, 0]]

min_cut_weight = min_cut(graph)
print(min_cut_weight)

其中，graph为邻接矩阵表示的图，min_cut_weight为最小割的权值。