■ 그래프에서 포드-풀커슨(Ford Fulkerson) 알고리즘을 사용해 최대 유량을 구하는 방법을 보여준다.
▶ main.py
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
def getFordFulkersonMaximumFlow(graphListList, source, sink): def bfs(graph): visitedList = [False] * len(graph) queueList = [] queueList.append(source) visitedList[source] = True while queueList: u = queueList.pop(0) for index, value in enumerate(graph[u]): if visitedList[index] == False and value > 0: queueList.append(index) visitedList[index] = True parentList[index] = u if index == sink: return True return False parentList = [-1] * len(graphListList) maximumFlow = 0 while bfs(graphListList): pathFlow = float("inf") s = sink while(s != source): pathFlow = min(pathFlow, graphListList[parentList[s]][s]) s = parentList[s] maximumFlow += pathFlow v = sink while(v != source): u = parentList[v] graphListList[u][v] -= pathFlow graphListList[v][u] += pathFlow v = parentList[v] return maximumFlow graphListList = [ [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] ] maximumFlow = getFordFulkersonMaximumFlow(graphListList, 0, 5) print("최대 유량 :", maximumFlow) """ 최대 유량 : 23 """ |