C++ में फ्लो नेटवर्क में न्यूनतम s-t कट का पता लगाएं

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

तो, अगर इनपुट पसंद है

तो आउटपुट [(1,3), (4,3), (4,5)]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• नोड्स =6

• फ़ंक्शन bfs () को परिभाषित करें, यह ग्राफ़, src, सिंक, सरणी बराबर,

  लेगा

• आकार की एक सरणी को परिभाषित करें - नोड्स। और 0 से भरें

• एक कतार को परिभाषित करें

• src को que में डालें

• विज़ [src] :=true और par[src] :=-1

• जबकि (क्यू खाली नहीं है), करें -

  • u1 :=क्यू का पहला तत्व

  • क्यू से तत्व हटाएं

  • इनिशियलाइज़ v1 :=0 के लिए, जब v1

    • अगर vis[v1] गलत है और ग्राफ[u1, v1]> 0 है, तो -

      • v1 को क्यू में डालें

      • par[v1] :=u1

      • विज़ [v1] :=सच

• जब vis[sink] सच हो तब वापस लौटें

• फ़ंक्शन dfs() को परिभाषित करें, यह ग्राफ़, src, array vis,

  . लेगा

• विज़ [src] :=सच

• इनिशियलाइज़ i :=0 के लिए, जब i

  • अगर ग्राफ [src, i] शून्य नहीं है और vis [i] गलत है, तो -

    • dfs(ग्राफ, आई, विज़)

• मुख्य विधि से, निम्न कार्य करें -

• एक सरणी temp_graph परिभाषित करें और उसमें ग्राफ़ कॉपी करें

• आकार के बराबर सरणी परिभाषित करें:नोड्स।

• जबकि bfs(temp_graph, src, sync, par) सत्य है, करें -

  • path_flow :=inf

  • इनिशियलाइज़ v:=सिंक के लिए, जब v src के बराबर नहीं है, अपडेट करें v:=par[v], करें -

    • आप:=बराबर[v]

    • path_flow :=कम से कम path_flow और temp_graph[u, v]

  • इनिशियलाइज़ v:=सिंक के लिए, जब v src के बराबर नहीं है, अपडेट करें v:=par[v], करें -

    • आप:=बराबर[v]

    • temp_graph[u, v] :=temp_graph[u, v] - path_flow

    • temp_graph[v, u] :=temp_graph[v, u] + path_flow

• आकार की एक सरणी को परिभाषित करें - नोड्स। और असत्य भरें

• dfs(temp_graph, src, vis)

• इनिशियलाइज़ i :=0 के लिए, जब i - NODES, अपडेट करें (i को 1 से बढ़ाएँ), करें -

• इनिशियलाइज़ j :=0 के लिए, जब j - NODES, अपडेट करें (j को 1 से बढ़ाएँ), करें -

  • अगर vis[i] शून्य नहीं है और vis[j] गलत है और ग्राफ[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<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)