깊이 우선 탐색을 사용하는 Ford-Fulkerson 알고리즘

Question

Ford-Fulkerson 알고리즘 구현의 숙제를하고 있는데, 경로 찾기에 DFS를 사용해야하지만 어딘가에 머물러 있다고했습니다. 코드가 너무 많이 현지화되어 있으므로 게시하지 않습니다. 사실 내 DFS 알고리즘은 잘 작동하지만 난 그

0 => 1 1 => 2 일 => 3 3 => 5

같은 DFS의 출력을 얻을 내 코드를 실행하면 막 다른 골목 예를 들어 문제가 발생

0에서 시작하여 5로 끝나지만 1 => 2 부분은 내 알고리즘에 대해 부정확합니다. 또한 [N] [2] 행렬을 사용하여 경로를 저장합니다. 내 질문은 내 결과 행렬에있는 막 다른 부분을 어떻게 제거 할 수 있습니까? (아마도 DFS 재귀 안쪽에 있습니까?)

Answer 1

소스와 싱크 사이의 경로를 찾으려면 DFS를 수행해야합니다. 그런 다음 dfs가 재조정 될 때 흐름을 추가해야합니다.

다음은 예입니다. "보내기"기능은 DFS입니다. 나는 DFS와 검색 중 발견 된 최소 용량 값에 따라 통과 공지 사항 :

https://github.com/juanplopes/icpc/blob/master/uva/820.cpp

int send(int s, int t, int minn) { 
    V[s] = true; 

    if (s==t) return minn; 

    for(int i=1; i<=n; i++) { 
     int capacity = G[s][i]-F[s][i]; 
     if (!V[i] && capacity > 0) { 
      if (int sent = send(i, t, min(minn, capacity))) { 
       F[s][i] += sent; 
       F[i][s] -= sent; 
       return sent; 
      } 
     } 
    } 

    return 0; 
}