다음과 같은 흐름 네트워크가 있다고 가정합니다. 우리가 알고 있듯이 s-t 컷은 소스 s 노드와 싱크 t 노드가 서로 다른 하위 집합에 있어야 하는 컷이며 소스 세트에서 싱크 쪽으로 가는 에지를 포함합니다. 여기서 s-t 컷의 용량은 컷 세트의 각 에지 용량의 합으로 표시됩니다. 여기서 우리는 주어진 네트워크의 최소 용량 s-cut을 찾아야 합니다. 여기서 예상되는 출력은 최소 컷의 모든 가장자리입니다.
따라서 입력이 다음과 같으면
그러면 출력은 [(1,3), (4,3), (4,5)]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
노드 =6
-
bfs() 함수를 정의하면 그래프, src, 싱크, 배열 파,
가 사용됩니다. -
− NODES 크기의 배열 시각화를 정의합니다. 0으로 채우기
-
하나의 대기열 대기열 정의
-
src를 que에 삽입
-
vis[src] :=true 및 par[src] :=-1
-
동안(que는 비어 있지 않음) -
-
u1 :=que의 첫 번째 요소
-
큐에서 요소 삭제
-
v1 초기화의 경우:=0, v1
-
vis[v1]이 거짓이고 graph[u1, v1]> 0이면 -
-
큐에 v1 삽입
-
par[v1] :=u1
-
vis[v1] :=참
-
-
-
-
vis[sink]가 true일 때 true를 반환합니다.
-
dfs() 함수를 정의하면 그래프, src, 배열 vis,
가 필요합니다. -
vis[src] :=참
-
for initialize i :=0, i
-
그래프[src, i]가 0이 아니고 vis[i]가 거짓이면 -
-
dfs(그래프, i, vis)
-
-
-
기본 방법에서 다음을 수행하십시오 -
-
배열 temp_graph를 정의하고 그래프를 복사하십시오.
-
NODES 크기의 배열을 정의하십시오.
-
bfs(temp_graph, src, sink, par)가 참인 동안 −
-
path_flow :=inf
-
v 초기화:=싱크의 경우 v가 src와 같지 않으면 v:=par[v]를 업데이트하고 -
를 수행합니다.-
유 :=par[v]
-
path_flow :=path_flow 및 temp_graph의 최소값[u, v]
-
-
v 초기화:=싱크의 경우 v가 src와 같지 않으면 v:=par[v]를 업데이트하고 -
를 수행합니다.-
유 :=par[v]
-
temp_graph[u, v] :=temp_graph[u, v] - path_flow
-
temp_graph[v, u] :=temp_graph[v, u] + path_flow
-
-
-
− NODES 크기의 배열 시각화를 정의합니다. 거짓으로 채우기
-
dfs(temp_graph, src, vis)
-
initialize i :=0의 경우 i − NODES일 때 업데이트(i 1만큼 증가), −
-
j 초기화의 경우:=0, j − NODES일 때 업데이트(j를 1만큼 증가), −
-
vis[i]가 0이 아니고 vis[j]가 false이고 graph[i, j]가 0이 아닌 경우 -
-
(i, j)를 가장자리로 표시
-
-
반환
-
예시(C++)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
#define NODES 6
int bfs(int graph[NODES][NODES], int src, int sink, int par[]) {
bool vis[NODES];
memset(vis, 0, sizeof(vis));
queue <int> que;
que.push(src);
vis[src] = true;
par[src] = -1;
while (!que.empty()) {
int u1 = que.front();
que.pop();
for (int v1=0; v1<NODES; v1++){
if (vis[v1]==false && graph[u1][v1] > 0) {
que.push(v1);
par[v1] = u1;
vis[v1] = true;
}
}
}
return (vis[sink] == true);
}
void dfs(int graph[NODES][NODES], int src, bool vis[]) {
vis[src] = true;
for (int i = 0; i < NODES; i++)
if (graph[src][i] && !vis[i])
dfs(graph, i, vis);
}
void minCut(int graph[NODES][NODES], int src, int sink) {
int u, v;
int temp_graph[NODES][NODES];
for (u = 0; u < NODES; u++)
for (v = 0; v < NODES; v++)
temp_graph[u][v] = graph[u][v];
int par[NODES];
while (bfs(temp_graph, src, sink, par)){
int path_flow = INT_MAX;
for (v=sink; v!=src; v=par[v]) {
u = par[v];
path_flow = min(path_flow, temp_graph[u][v]);
}
for (v=sink; v != src; v=par[v]) {
u = par[v];
temp_graph[u][v] -= path_flow;
temp_graph[v][u] += path_flow;
}
}
bool vis[NODES];
memset(vis, false, sizeof(vis));
dfs(temp_graph, src, vis);
for (int i = 0; i < NODES; i++)
for (int j = 0; j < NODES; j++)
if (vis[i] && !vis[j] && graph[i][j])
cout << "("<< i << ", " << j << ")" << endl;
return;
}
int main() {
int graph1[NODES][NODES] = {
{0, 17, 14, 0, 0, 0},
{0, 0, 11, 13, 0, 0},
{0, 5, 0, 0, 15, 0},
{0, 0, 9, 0, 0, 21},
{0, 0, 0, 8, 0, 5},
{0, 0, 0, 0, 0, 0}
};
minCut(graph1, 0, 5);
} 입력
{{0, 17, 14, 0, 0, 0},
{0, 0, 11, 13, 0, 0},
{0, 5, 0, 0, 15, 0},
{0, 0, 9, 0, 0, 21
{0, 0, 0, 8, 0, 5},
{0, 0, 0, 0, 0, 0}}; 출력
(1, 3) (4, 3) (4, 5)