एक निर्देशित ग्राफ को दृढ़ता से जुड़ा हुआ कहा जाता है, जब एक घटक में शीर्षों के प्रत्येक जोड़े के बीच एक पथ होता है।
इस एल्गोरिदम को हल करने के लिए, पहले, प्रत्येक शीर्ष का समाप्ति समय प्राप्त करने के लिए DFS एल्गोरिदम का उपयोग किया जाता है, अब परिवर्तित ग्राफ का समाप्ति समय ढूंढें, फिर शीर्षों को टोपोलॉजिकल सॉर्ट द्वारा अवरोही क्रम में क्रमबद्ध किया जाता है।
इनपुट और आउटपुट
इनपुट: ग्राफ का आसन्नता मैट्रिक्स। 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 आउटपुट: दिए गए ग्राफ में दृढ़ता से जुड़े घटक निम्नलिखित हैं: 0 1 2 3 4
एल्गोरिदम
traverse(graph, start, visited)
इनपुट: वह ग्राफ जिसे पार किया जाएगा, प्रारंभिक शीर्ष, और देखे गए नोड्स के फ्लैग।
आउटपुट: DFS तकनीक में प्रत्येक नोड से गुजरें और नोड्स प्रदर्शित करें।
शुरू start को देखा गया चिह्नित करें start के साथ जुड़े सभी शीर्ष v के लिए, करें यदि v नहीं देखा गया है, तो traverse(graph, v, visited) किया अंत
topoSort(u, visited, stack)
इनपुट: प्रारंभ नोड, देखे गए शीर्षों के लिए फ्लैग, स्टैक।
आउटपुट: ग्राफ को क्रमबद्ध करते हुए स्टैक भरें।
शुरू u को देखा गया चिह्नित करें u के साथ जुड़े सभी नोड v के लिए, करें यदि v नहीं देखा गया है, तो topoSort(v, visited, stack) किया u को स्टैक में पुश करें अंत
getStrongConComponents(graph)
इनपुट: दिया गया ग्राफ।
आउटपुट: सभी दृढ़ता से जुड़े घटक।
शुरू प्रारंभ में सभी नोड्स अनदेखे हैं ग्राफ में सभी शीर्ष i के लिए, करें यदि i नहीं देखा गया है, तो topoSort(i, vis, stack) किया सभी नोड्स को फिर से अनदेखा करें transGraph := दिए गए ग्राफ का परिवर्तित रूप जब तक स्टैक खाली नहीं है, करें स्टैक से नोड पॉप करें और v में लें यदि v नहीं देखा गया है, तो traverse(transGraph, v, visited) किया अंत
उदाहरण
#include <iostream> #include <stack> #define NODE 5 using namespace std; int graph[NODE][NODE] = { {0, 0, 1, 1, 0}, {1, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 0, 0} }; int transGraph[NODE][NODE]; void transpose() { //ग्राफ को परिवर्तित करें और transGraph में संग्रहीत करें for(int i = 0; i
आउटपुट
Following are strongly connected components in given graph: 0 1 2 3 4
