फोर्ड-फुल्करसन एल्गोरिदम का उपयोग दिए गए ग्राफ में प्रारंभ शीर्ष से सिंक शीर्ष तक अधिकतम प्रवाह का पता लगाने के लिए किया जाता है। इस ग्राफ में, प्रत्येक किनारे की क्षमता होती है। दो शीर्ष दिए गए हैं जिन्हें स्रोत और सिंक नाम दिया गया है। स्रोत शीर्ष में सभी जावक किनारे होते हैं, कोई आवक किनारा नहीं, और सिंक में सभी आवक किनारे होंगे कोई जावक किनारा नहीं।
कुछ प्रतिबंध हैं:
- किसी किनारे पर प्रवाह उस ग्राफ की दी गई क्षमता से अधिक नहीं होता।
- आवक प्रवाह और जावक प्रवाह भी प्रत्येक किनारे के लिए समान होंगे, स्रोत और सिंक को छोड़कर।
इनपुट और आउटपुट
इनपुट: आसन्नता मैट्रिक्स: 0 10 0 10 0 0 0 0 4 2 8 0 0 0 0 0 0 10 0 0 0 0 9 0 0 0 6 0 0 10 0 0 0 0 0 0 आउटपुट: अधिकतम प्रवाह है: 19
एल्गोरिदम
bfs(vert, start, sink)
इनपुट: शीर्षों की सूची, प्रारंभ नोड, और सिंक नोड।
आउटपुट: जब सिंक देखा गया तो सच।
शुरू प्रारंभ में सभी नोड्स को अनदेखा चिह्नित करें प्रारंभ की स्थिति को देखा गया चिह्नित करें प्रारंभ नोड का पूर्ववर्ती φ है प्रारंभ को कतार qu में डालें जब तक qu खाली नहीं है, करें कतार से तत्व हटाएं और u शीर्ष पर सेट करें अवशिष्ट ग्राफ में सभी शीर्ष i के लिए, करें यदि u और i जुड़े हुए हैं, और i अनदेखा है, तो शीर्ष i को कतार में जोड़ें i का पूर्ववर्ती u है i को देखा गया चिह्नित करें किया किया वापस करें सच यदि सिंक शीर्ष की स्थिति देखी गई है अंत
fordFulkerson(vert, source, sink)
इनपुट: शीर्षों की सूची, स्रोत शीर्ष, और सिंक शीर्ष।
आउटपुट: प्रारंभ से सिंक तक अधिकतम प्रवाह।
शुरू एक अवशिष्ट ग्राफ बनाएं और दिए गए ग्राफ को इसमें कॉपी करें जब तक bfs(vert, source, sink) सच है, करें pathFlow := ∞ v := सिंक शीर्ष जब तक v ≠ प्रारंभ शीर्ष, करें u := v का पूर्ववर्ती pathFlow := pathFlow और residualGraph[u, v] का न्यूनतम v := v का पूर्ववर्ती किया v := सिंक शीर्ष जब तक v ≠ प्रारंभ शीर्ष, करें u := v का पूर्ववर्ती residualGraph[u,v] := residualGraph[u,v] – pathFlow residualGraph[v,u] := residualGraph[v,u] – pathFlow v := v का पूर्ववर्ती किया maxFlow := maxFlow + pathFlow किया maxFlow वापस करें अंत
उदाहरण
#include<iostream> #include<queue> #define NODE 6 using namespace std; typedef struct node { int val; int state; //स्थिति int pred; //पूर्ववर्ती }node; int minimum(int a, int b) { return (a 0 && vert[i].state == 0) { que.push(vert[i]); vert[i].pred = u.val; vert[i].state = 1; } } } return (vert[sink.val].state == 1); } int fordFulkerson(node *vert, node source, node sink) { int maxFlow = 0; int u, v; for(int i = 0; i
आउटपुट
Maximum flow is: 19
