मान लीजिए हमारे पास निम्नलिखित फ्लो नेटवर्क है। जैसा कि हम जानते हैं एक s-t कट एक ऐसा कट है जिसमें स्रोत s नोड और सिंक t नोड को अलग-अलग उपसमुच्चय में होना आवश्यक है, और इसमें स्रोत सेट से सिंक साइड की ओर जाने वाले किनारे शामिल हैं। यहां s-t कट की क्षमता कट-सेट में प्रत्येक किनारे की क्षमता के योग द्वारा दर्शाई जाती है। यहां हमें दिए गए नेटवर्क का न्यूनतम क्षमता s-t कट ढूंढना है। यहां अपेक्षित आउटपुट न्यूनतम कट के सभी किनारे हैं।
तो, यदि इनपुट जैसा है

तो आउटपुट [(1,3), (4,3), (4,5)] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
NODES = 6
एक फ़ंक्शन bfs() परिभाषित करें, यह ग्राफ, src, sink, सरणी par लेगा,
NODES आकार का एक सरणी vis परिभाषित करें। और 0 से भरें
एक क्यू que परिभाषित करें
src को que में डालें
vis[src] := true और par[src] := -1
जब तक (que खाली नहीं है), करें -
u1 := que का पहला तत्व
que से तत्व हटाएं
v1 := 0 से आरंभ करें, जब v1 < NODES, अपडेट करें (v1 को 1 से बढ़ाएं), करें -
यदि vis[v1] गलत है और graph[u1, v1] > 0, तो -
v1 को que में डालें
par[v1] := u1
vis[v1] := true
सच लौटाएं जब vis[sink] सच हो
एक फ़ंक्शन dfs() परिभाषित करें, यह ग्राफ, src, सरणी vis लेगा,
vis[src] := true
i := 0 से आरंभ करें, जब i < NODES, अपडेट करें (i को 1 से बढ़ाएं), करें -
यदि graph[src, i] शून्येतर है और vis[i] गलत है, तो -
dfs(graph, i, vis)
मुख्य विधि से, निम्नलिखित करें -
एक सरणी temp_graph परिभाषित करें और ग्राफ को इसमें कॉपी करें
आकार NODES का एक सरणी par परिभाषित करें।
जब तक bfs(temp_graph, src, sink, par) सच है, करें -
path_flow := inf
v := sink से आरंभ करें, जब v src के बराबर नहीं है, अपडेट v:=par[v], करें -
u := par[v]
path_flow := path_flow और temp_graph[u, v] का न्यूनतम
v := sink से आरंभ करें, जब v src के बराबर नहीं है, अपडेट v:=par[v], करें -
u := par[v]
temp_graph[u, v] := temp_graph[u, v] - path_flow
temp_graph[v, u] := temp_graph[v, u] + path_flow
आकार NODES का एक सरणी vis परिभाषित करें। और false से भरें
dfs(temp_graph, src, vis)
i := 0 से आरंभ करें, जब i < NODES, अपडेट करें (i को 1 से बढ़ाएं), करें -
j := 0 से आरंभ करें, जब j < NODES, अपडेट करें (j को 1 से बढ़ाएं), करें -
यदि vis[i] शून्येतर है और vis[j] गलत है और graph[i, j] शून्येतर है, तो -
(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 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)