मजबूती से जुड़े घटक

विषय - सूची

कोसाराजू का एल्गोरिथम
पायथन, जावा, सी ++ उदाहरण
कोसाराजू की एल्गोरिथम जटिलता
दृढ़ता से जुड़े घटक अनुप्रयोग

इस ट्यूटोरियल में, आप सीखेंगे कि कैसे मजबूती से जुड़े हुए घटक बनते हैं। इसके अलावा, आपको C, C ++, Java और पायथन में कोसरजू के एल्गोरिथ्म के काम करने के उदाहरण मिलेंगे।

एक दृढ़ता से जुड़ा घटक एक निर्देशित ग्राफ का हिस्सा है जिसमें प्रत्येक शीर्ष से दूसरे शीर्ष पर एक मार्ग होता है। यह केवल एक निर्देशित ग्राफ पर लागू होता है ।

उदाहरण के लिए:

नीचे दिए गए ग्राफ को लेते हैं।

प्रारंभिक ग्राफ

उपरोक्त ग्राफ के दृढ़ता से जुड़े घटक हैं:

मजबूती से जुड़े घटक

आप देख सकते हैं कि पहले दृढ़ता से जुड़े घटक में, प्रत्येक शीर्ष निर्देशित मार्ग से दूसरे शीर्ष पर पहुंच सकता है।

इन घटकों को कोसाराजू के एल्गोरिथ्म का उपयोग करके पाया जा सकता है ।

कोसाराजू का एल्गोरिथम

कोसाराजू का एल्गोरिथ्म दो बार लागू गहराई-पहले खोज एल्गोरिदम पर आधारित है।

तीन चरण शामिल हैं।

पूरे ग्राफ पर पहले गहराई की खोज करें।
हमें वर्टेक्स -० से शुरू करते हैं, उसके सभी बच्चे कोने पर जाएँ, और किए गए कोने पर जाएँ। यदि कोई शीर्ष पहले से ही देखी गई शीर्ष पर जाता है, तो इस शीर्ष को स्टैक पर ले जाएँ।
उदाहरण के लिए: वर्टेक्स -० से शुरू करके, वर्टेक्स -१, वर्टेक्स -२, और फिर वर्टेक्स -३ पर जाएँ। वर्टेक्स -3 पहले से ही वर्टेक्स -0 पर जाता है, इसलिए स्टैक में सोर्स वर्टेक्स (यानी वर्टेक्स -3) को पुश करें। ग्राफ पर डीएफएस
पिछले वर्टेक्स (वर्टेक्स -2) पर जाएं और इसके चाइल्ड वर्टिस यानी वर्टेक्स -4, वर्टेक्स -5, वर्टेक्स -6 और वर्टेक्स -7 क्रमिक रूप से विजिट करें। चूंकि वर्टेक्स -7 से कहीं जाना नहीं है, इसे स्टैक में धकेल दें। ग्राफ पर डी.एफ.एस.
पिछले शीर्ष (वर्टेक्स -6) पर जाएं और उसके बच्चे के कोने पर जाएं। लेकिन, इसके सभी बच्चे लंबवत होते हैं, इसलिए इसे स्टैक में धकेलें। स्टैकिंग
इसी तरह, एक अंतिम स्टैक बनाया जाता है। फाइनल स्टैक
मूल ग्राफ को उलट दें। उल्टे ग्राफ पर डी.एफ.एस.
उलटे ग्राफ पर गहराई-पहली खोज करें।
स्टैक के शीर्ष शीर्ष से शुरू करें। अपने सभी बच्चे कोने के माध्यम से पार। एक बार पहले से ही देखे गए शीर्ष पर पहुंचने के बाद, एक दृढ़ता से जुड़ा घटक बनता है।
उदाहरण के लिए: स्टैक से पॉप वर्टेक्स -0। वर्टेक्स -0 से शुरू होकर, अपने बच्चे के कोने (वर्टेक्स -0, वर्टेक्स -1, वर्टेक्स -2, वर्टेक्स -3 इन सीक्वेंस) के माध्यम से आगे बढ़ें और उन्हें दौरा किया। वर्टेक्स -3 के बच्चे को पहले से ही दौरा किया जाता है, इसलिए ये विज़िट किए गए कोने एक दृढ़ता से जुड़े घटक बनाते हैं। ऊपर से शुरू करें और सभी चक्करों से गुजरें
। स्टैक पर जाएं और यदि पहले से ही दौरा किया है तो शीर्ष शीर्ष को पॉप करें। अन्यथा, स्टैक से शीर्ष शीर्ष चुनें और ऊपर प्रस्तुत किए गए के रूप में अपने बच्चे के कोने के माध्यम से पार करें। पहले से ही जाने पर शीर्ष शीर्ष पॉप मजबूती से जुड़ा घटक
इस प्रकार, दृढ़ता से जुड़े घटक हैं: सभी दृढ़ता से जुड़े घटक

पायथन, जावा, सी ++ उदाहरण

पायथन जावा सी ++

 # Kosaraju's algorithm to find strongly connected components in Python from collections import defaultdict class Graph: def __init__(self, vertex): self.V = vertex self.graph = defaultdict(list) # Add edge into the graph def add_edge(self, s, d): self.graph(s).append(d) # dfs def dfs(self, d, visited_vertex): visited_vertex(d) = True print(d, end='') for i in self.graph(d): if not visited_vertex(i): self.dfs(i, visited_vertex) def fill_order(self, d, visited_vertex, stack): visited_vertex(d) = True for i in self.graph(d): if not visited_vertex(i): self.fill_order(i, visited_vertex, stack) stack = stack.append(d) # transpose the matrix def transpose(self): g = Graph(self.V) for i in self.graph: for j in self.graph(i): g.add_edge(j, i) return g # Print stongly connected components def print_scc(self): stack = () visited_vertex = (False) * (self.V) for i in range(self.V): if not visited_vertex(i): self.fill_order(i, visited_vertex, stack) gr = self.transpose() visited_vertex = (False) * (self.V) while stack: i = stack.pop() if not visited_vertex(i): gr.dfs(i, visited_vertex) print("") g = Graph(8) g.add_edge(0, 1) g.add_edge(1, 2) g.add_edge(2, 3) g.add_edge(2, 4) g.add_edge(3, 0) g.add_edge(4, 5) g.add_edge(5, 6) g.add_edge(6, 4) g.add_edge(6, 7) print("Strongly Connected Components:") g.print_scc()

 // Kosaraju's algorithm to find strongly connected components in Java import java.util.*; import java.util.LinkedList; class Graph ( private int V; private LinkedList adj(); // Create a graph Graph(int s) ( V = s; adj = new LinkedList(s); for (int i = 0; i < s; ++i) adj(i) = new LinkedList(); ) // Add edge void addEdge(int s, int d) ( adj(s).add(d); ) // DFS void DFSUtil(int s, boolean visitedVertices()) ( visitedVertices(s) = true; System.out.print(s + " "); int n; Iterator i = adj(s).iterator(); while (i.hasNext()) ( n = i.next(); if (!visitedVertices(n)) DFSUtil(n, visitedVertices); ) ) // Transpose the graph Graph Transpose() ( Graph g = new Graph(V); for (int s = 0; s < V; s++) ( Iterator i = adj(s).listIterator(); while (i.hasNext()) g.adj(i.next()).add(s); ) return g; ) void fillOrder(int s, boolean visitedVertices(), Stack stack) ( visitedVertices(s) = true; Iterator i = adj(s).iterator(); while (i.hasNext()) ( int n = i.next(); if (!visitedVertices(n)) fillOrder(n, visitedVertices, stack); ) stack.push(new Integer(s)); ) // Print strongly connected component void printSCC() ( Stack stack = new Stack(); boolean visitedVertices() = new boolean(V); for (int i = 0; i < V; i++) visitedVertices(i) = false; for (int i = 0; i < V; i++) if (visitedVertices(i) == false) fillOrder(i, visitedVertices, stack); Graph gr = Transpose(); for (int i = 0; i < V; i++) visitedVertices(i) = false; while (stack.empty() == false) ( int s = (int) stack.pop(); if (visitedVertices(s) == false) ( gr.DFSUtil(s, visitedVertices); System.out.println(); ) ) ) public static void main(String args()) ( Graph g = new Graph(8); g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(2, 3); g.addEdge(2, 4); g.addEdge(3, 0); g.addEdge(4, 5); g.addEdge(5, 6); g.addEdge(6, 4); g.addEdge(6, 7); System.out.println("Strongly Connected Components:"); g.printSCC(); ) )

 // Kosaraju's algorithm to find strongly connected components in C++ #include #include #include using namespace std; class Graph ( int V; list *adj; void fillOrder(int s, bool visitedV(), stack &Stack); void DFS(int s, bool visitedV()); public: Graph(int V); void addEdge(int s, int d); void printSCC(); Graph transpose(); ); Graph::Graph(int V) ( this->V = V; adj = new list(V); ) // DFS void Graph::DFS(int s, bool visitedV()) ( visitedV(s) = true; cout << s << " "; list::iterator i; for (i = adj(s).begin(); i != adj(s).end(); ++i) if (!visitedV(*i)) DFS(*i, visitedV); ) // Transpose Graph Graph::transpose() ( Graph g(V); for (int s = 0; s < V; s++) ( list::iterator i; for (i = adj(s).begin(); i != adj(s).end(); ++i) ( g.adj(*i).push_back(s); ) ) return g; ) // Add edge into the graph void Graph::addEdge(int s, int d) ( adj(s).push_back(d); ) void Graph::fillOrder(int s, bool visitedV(), stack &Stack) ( visitedV(s) = true; list::iterator i; for (i = adj(s).begin(); i != adj(s).end(); ++i) if (!visitedV(*i)) fillOrder(*i, visitedV, Stack); Stack.push(s); ) // Print strongly connected component void Graph::printSCC() ( stack Stack; bool *visitedV = new bool(V); for (int i = 0; i < V; i++) visitedV(i) = false; for (int i = 0; i < V; i++) if (visitedV(i) == false) fillOrder(i, visitedV, Stack); Graph gr = transpose(); for (int i = 0; i < V; i++) visitedV(i) = false; while (Stack.empty() == false) ( int s = Stack.top(); Stack.pop(); if (visitedV(s) == false) ( gr.DFS(s, visitedV); cout << endl; ) ) ) int main() ( Graph g(8); g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(2, 3); g.addEdge(2, 4); g.addEdge(3, 0); g.addEdge(4, 5); g.addEdge(5, 6); g.addEdge(6, 4); g.addEdge(6, 7); cout << "Strongly Connected Components:"; g.printSCC(); )