解析Ford-Fulkerson算法并通过Python实现

from collections import defaultdictclass Graph:    def __init__(self, graph):        self.graph = graph        self. ROW = len(graph)    def searching_algo_BFS(self, s, t, parent):        visited = [False] * (self.ROW)        queue = []        queue.append(s)        visited[s] = True        while queue:            u = queue.pop(0)            for ind, val in enumerate(self.graph[u]):                if visited[ind] == False and val > 0:                    queue.append(ind)                    visited[ind] = True                    parent[ind] = u        return True if visited[t] else False    def ford_fulkerson(self, source, sink):        parent = [-1] * (self.ROW)        max_flow = 0        while self.searching_algo_BFS(source, sink, parent):            path_flow = float("Inf")            s = sink            while(s != source):                path_flow = min(path_flow, self.graph[parent[s]][s])                s = parent[s]            max_flow += path_flow            v = sink            while(v != source):                u = parent[v]                self.graph[u][v] -= path_flow                self.graph[v][u] += path_flow                v = parent[v]        return max_flowgraph = [[0, 8, 0, 0, 3, 0],         [0, 0, 9, 0, 0, 0],         [0, 0, 0, 0, 7, 2],         [0, 0, 0, 0, 0, 5],         [0, 0, 7, 4, 0, 0],         [0, 0, 0, 0, 0, 0]]g = Graph(graph)source = 0sink = 5print("Max Flow: %d " % g.ford_fulkerson(source, sink))