Giả sử chúng ta có mạng luồng sau. Như chúng ta biết một phép cắt s-t là một phép cắt yêu cầu nút nguồn s và một nút chìm t nằm trong các tập con khác nhau và nó bao gồm các cạnh đi từ tập nguồn đến phía chìm. Ở đây dung lượng của một vết cắt s-t được biểu thị bằng tổng của mỗi công suất cạnh trong tập hợp vết cắt. Ở đây chúng ta phải tìm mức cắt công suất tối thiểu của mạng đã cho. Ở đây, sản lượng mong đợi là tất cả các cạnh của đường cắt tối thiểu.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là [(1,3), (4,3), (4,5)]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
NODES =6
-
Xác định một hàm bfs (), điều này sẽ lấy đồ thị, src, chìm, par mảng,
-
Xác định kích thước vis mảng - NODES. và điền bằng 0
-
Xác định một hàng đợi
-
chèn src vào que
-
vis [src]:=true và par [src]:=-1
-
while (que không trống), do -
-
u1:=phần tử đầu tiên của que
-
xóa phần tử khỏi hàng đợi
-
để khởi tạo v1:=0, khi v1
-
nếu vis [v1] là false và đồ thị [u1, v1]> 0, thì -
-
chèn v1 vào hàng đợi
-
mệnh [v1]:=u1
-
vis [v1]:=true
-
-
-
-
trả về true khi vis [chìm] là true
-
Xác định một hàm dfs (), điều này sẽ lấy đồ thị, src, mảng vis,
-
vis [src]:=true
-
để khởi tạo i:=0, khi tôi
-
nếu graph [src, i] khác 0 và vis [i] là false, thì -
-
dfs (graph, i, vis)
-
-
-
Từ phương thức chính, thực hiện như sau -
-
Xác định một temp_graph mảng và sao chép đồ thị vào đó
-
Xác định một mảng có kích thước:NODES.
-
trong khi bfs (temp_graph, src, chìm, par) là true, do -
-
path_flow:=inf
-
để khởi tạo v:=chìm, khi v không bằng src, hãy cập nhật v:=par [v], do -
-
u:=par [v]
-
path_flow:=tối thiểu của path_flow và temp_graph [u, v]
-
-
để khởi tạo v:=chìm, khi v không bằng src, hãy cập nhật v:=par [v], do -
-
u:=par [v]
-
temp_graph [u, v]:=temp_graph [u, v] - path_flow
-
temp_graph [v, u]:=temp_graph [v, u] + path_flow
-
-
-
Xác định kích thước vis mảng - NODES. và điền sai
-
dfs (temp_graph, src, vis)
-
để khởi tạo i:=0, khi tôi - NODES, cập nhật (tăng tôi lên 1), thực hiện -
-
để khởi tạo j:=0, khi j - NODES, cập nhật (tăng j lên 1), thực hiện -
-
nếu vis [i] khác 0 và vis [j] sai và đồ thị [i, j] khác 0 thì -
-
hiển thị (i, j) dưới dạng cạnh
-
-
trở lại
-
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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);
} Đầu vào
{{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}}; Đầu ra
(1, 3) (4, 3) (4, 5)