निर्देशित ग्राफ में घटकों को दृढ़ता से जुड़ा हुआ कहा जाता है, जब एक घटक में वर्टेक्स के प्रत्येक जोड़े के बीच एक पथ होता है।
इस एल्गोरिदम को हल करने के लिए, पहले, प्रत्येक वर्टेक्स का फिनिश टाइम प्राप्त करने के लिए 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 तकनीक का उपयोग करके प्रत्येक नोड से गुजरें और नोड्स प्रदर्शित करें।
शुरुआत शुरुआत को विज़िट के रूप में चिह्नित करें शुरुआत से जुड़े सभी वर्टेक्स 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<NODE; i++) for(int j = 0; j<NODE; j++) transGraph[i][j] = graph[j][i]; } void traverse(int g[NODE][NODE], int u, bool visited[]) { visited[u] = true; //v को विज़िट के रूप में चिह्नित करें cout << u << " "; for(int v = 0; v<NODE; v++) { if(g[u][v]) { if(!visited[v]) traverse(g, v, visited); } } } void topoSort(int u, bool visited[], stack<int> &stk) { visited[u] = true; //नोड v को विज़िट के रूप में सेट करें for(int v = 0; v<NODE; v++) { if(graph[u][v]) { //u से आसन्न सभी वर्टेक्स v के लिए if(!visited[v]) topoSort(v, visited, stk); } } stk.push(u); //प्रारंभिक वर्टेक्स को स्टैक में पुश करें } void getStrongConComponents() { stack<int> stk; bool vis[NODE]; for(int i = 0; i<NODE; i++) vis[i] = false; //प्रारंभ में सभी नोड्स अविज़िटेड हैं for(int i = 0; i<NODE; i++) if(!vis[i]) //जब नोड विज़िट नहीं किया गया है topoSort(i, vis, stk); for(int i = 0; i<NODE; i++) vis[i] = false; //पार करने के लिए सभी नोड्स को अविज़िटेड बनाएं transpose(); //उल्टा ग्राफ बनाएं while(!stk.empty()) { //जब स्टैक में तत्व हो, टोपोलॉजिकल क्रम में प्रक्रिया करें int v = stk.top(); stk.pop(); if(!vis[v]) { traverse(transGraph, v, vis); cout << endl; } } } int main() { cout << "दिए गए ग्राफ में दृढ़ता से जुड़े घटक निम्नलिखित हैं: "<<endl; getStrongConComponents(); }
आउटपुट
दिए गए ग्राफ में दृढ़ता से जुड़े घटक निम्नलिखित हैं: 0 1 2 3 4
