Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


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

तो, यदि इनपुट जैसा है

C++ में फ्लो नेटवर्क में न्यूनतम 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)

  1. C++ में फ्लो नेटवर्क में न्यूनतम s-t कट ढूंढना C++ में फ्लो नेटवर्क में न्यूनतम s-t कट ढूंढना

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

  1. - C++ में सरणी का न्यूनतम और अधिकतम तत्व खोजने का प्रोग्राम

    इस समस्या में, हमें n पूर्णांकों की एक सरणी arr[] दी गई है। हमारा कार्य C++ में सरणी के न्यूनतम और अधिकतम तत्व को खोजने के लिए एक प्रोग्राम बनाना है। समस्या विवरण यहां, हमारे पास एक सरणी arr[] है। इसमें n पूर्णांक मान हैं। हमें सरणी के सभी मानों में से अधिकतम मान और न्यूनतम मान ज्ञात करना है। उदाह

  1. C++ में नेटवर्क में क्रिटिकल कनेक्शन (Critical Connections in a Network) C++ में नेटवर्क में क्रिटिकल कनेक्शन (Critical Connections in a Network)

    समस्या विवरण n सर्वर हैं जो 0 से n-1 तक संख्यांकित हैं। connections[i] = [a,b] सर्वर a और b के बीच अनिर्देशित कनेक्शन दर्शाता है। सभी सर्वर प्रत्यक्ष या अप्रत्यक्ष रूप से जुड़े हैं। एक क्रिटिकल कनेक्शन वह किनारा है जिसे हटाने पर कुछ सर्वर अन्य सर्वरों तक नहीं पहुंच पाएंगे (यानी ग्राफ असंबद्ध हो जाए