| 1 | # Minimum cut on Ford_Fulkerson algorithm. |
| 2 | |
| 3 | def BFS(graph, s, t, parent): |
| 4 | # Return True if there is node that has not iterated. |
| 5 | visited = [False]*len(graph) |
| 6 | queue=[] |
| 7 | queue.append(s) |
| 8 | visited[s] = True |
| 9 | |
| 10 | while queue: |
| 11 | u = queue.pop(0) |
| 12 | for ind in range(len(graph[u])): |
| 13 | if visited[ind] == False and graph[u][ind] > 0: |
| 14 | queue.append(ind) |
| 15 | visited[ind] = True |
| 16 | parent[ind] = u |
| 17 | |
| 18 | return True if visited[t] else False |
| 19 | |
| 20 | def mincut(graph, source, sink): |
| 21 | # This array is filled by BFS and to store path |