포드 풀커슨 알고리즘

Ford-Fulkerson 알고리즘은 주어진 그래프에서 시작 정점에서 싱크 정점까지의 최대 흐름을 감지하는 데 사용됩니다. 이 그래프에서 모든 간선에는 용량이 있습니다. Source 및 Sink라는 두 개의 정점이 제공됩니다. 소스 꼭짓점에는 바깥쪽 가장자리가 없고 안쪽 가장자리가 없으며 싱크에는 바깥쪽 가장자리가 없는 모든 안쪽 가장자리가 있습니다.

몇 가지 제약이 있습니다.

• 가장자리의 흐름은 해당 그래프의 주어진 용량을 초과하지 않습니다.
• 들어오는 흐름과 나가는 흐름도 소스와 싱크를 제외한 모든 가장자리에 대해 동일합니다.

입력 및 출력

입력:인접 행렬:0 10 0 10 0 00 0 4 2 8 00 0 0 0 0 100 0 0 9 00 0 6 0 0 100 0 0 0 0 0Output:최대 흐름:19

bfs (수직, 시작, 가라앉음)

입력: 정점 목록, 시작 노드 및 싱크 노드.

출력 - 싱크를 방문하면 true입니다.

시작 노드의 방문 전임자는 φ이므로 시작의 모든 노드를 방문하지 않은 상태로 시작 시작으로 표시합니다. 큐가 비어 있지 않은 동안 큐에 시작을 삽입하고 큐에서 요소를 삭제하고 모든 정점 i에 대해 정점 u로 설정합니다. 잔차 그래프, u와 i가 연결되어 있고 i가 방문하지 않은 경우 수행한 다음 i의 선행 작업은 큐에 정점 i를 추가합니다. 

 fordFulkerson(vert, 소스, 싱크) 
 

 입력: 정점 목록, 소스 정점 및 싱크 정점.
 

 출력 -  시작에서 싱크까지의 최대 흐름입니다.
 
잔차 그래프 생성을 시작하고 bfs(vert, source, sink)가 참인 동안 주어진 그래프를 복사합니다. do pathFlow :=∞ v :=싱크 정점 동안 v ≠ 시작 정점, do u :=v pathFlow의 선행자 :=pathFlow 및 residualGraph[u, v]의 최소값 v :=v의 선행 작업 완료 v :=정점 싱크 동안 v ≠ 시작 정점, do u :=v의 선행 작업 잔여 그래프[u,v] :=잔여 그래프[u,v ] – pathFlow residualGraph[v,u] :=residualGraph[v,u] – pathFlow v :=v의 선행 작업 완료 maFlow :=maxFlow + pathFlow 완료 return maxFlowEnd
 
예시
 
#include#include#define NODE 6 네임스페이스 사용 std;typedef struct node { int val; 정수 상태; //상태 int pred; // 선행자}node;int minimum(int a, int b) { return (a큐; for(i =0; i 0 &&vert[i].state ==0) { que.push(vert[i]); vert[i].pred =u.val; vert[i].state =1; } } } return (vert[sink.val].state ==1);}int fordFulkerson(노드 *vert, 노드 소스, 노드 싱크) { int maxFlow =0; int u, v; for(int i =0; i 
출력
 
최대 흐름:19