Python中使用最小割算法解决网络分割问题

from collections import defaultdict

# 定义边的类
class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

# 定义图的类
class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    # 添加边
    def add_edge(self, u, v, w):
        self.graph[u].append(Edge(u, v, w))
        self.graph[v].append(Edge(v, u, w))

    # 最小割算法
    def min_cut(self, source, sink):
        # 定义parent数组
        parent = [-1] * len(self.graph)

        # 定义residual graph数组
        residual_graph = [[0] * len(self.graph) for _ in range(len(self.graph))]

        # 复制图的边
        for u in self.graph:
            for edge in self.graph[u]:
                residual_graph[edge.u][edge.v] = edge.w

        # 记录割点数量
        max_flow = 0

        # 执行BFS
        while self.bfs(residual_graph, source, sink, parent):
            # 找出路径中的最小权重
            path_flow = float("Inf")
            s = sink
            while s != source:
                path_flow = min(path_flow, residual_graph[parent[s]][s])
                s = parent[s]

            # 更新最大流
            max_flow += path_flow

            # 更新割点：逆推经过的路径，将路径上的边减去最小权重
            v = sink
            while v != source:
                u = parent[v]
                residual_graph[u][v] -= path_flow
                residual_graph[v][u] += path_flow
                v = parent[v]

        # 返回最小割
        return max_flow

    # BFS
    def bfs(self, graph, s, t, parent):
        visited = [False] * len(graph)
        visited[s] = True
        queue = [s]

        while queue:
            u = queue.pop(0)
            for ind, val in enumerate(graph[u]):
                if not visited[ind] and val > 0:
                    visited[ind] = True
                    queue.append(ind)
                    parent[ind] = u

        return True if visited[t] else False

# 测试代码
g = Graph()
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 6)
g.add_edge(1, 2, 4)
g.add_edge(1, 3, 1)
g.add_edge(2, 4, 3)
g.add_edge(3, 4, 8)

print("最小割是：", g.min_cut(0, 4))

最小割是： 11

# 建立一个字符串图
def build_graph(string, target):
    n = len(string)
    g = Graph()
    for i in range(n):
        for j in range(i+4, n):
            if string[i:j+1] == target + "com":
                g.add_edge(i, j, j-i+1)

    for i in range(n):
        g.add_edge(i, i+1, 1)

    return g

# 测试代码
g = build_graph("pidancode.com", "code")
print("最小割是：", g.min_cut(0, len("pidancode.com")-1))

最小割是： 2