ग्राफ़ की कनेक्टिविटी जांचने के लिए, हम किसी भी ट्रैवर्सल एल्गोरिदम का उपयोग करके सभी नोड्स को ट्रैवर्स करने का प्रयास करेंगे। ट्रैवर्सल पूरा होने के बाद, यदि कोई नोड ऐसा है जिसे विज़िट नहीं किया गया है, तो ग्राफ़ कनेक्टेड नहीं है।
डायरेक्टेड ग्राफ़ के लिए, हम सभी नोड्स से ट्रैवर्सल शुरू करके कनेक्टिविटी जांचेंगे। कभी-कभी एक एज का केवल आउटवर्ड एज हो सकता है लेकिन इनवर्ड एज नहीं, इसलिए वह नोड किसी अन्य शुरुआती नोड से अनविज़िटेड रहेगा।
इस केस में ट्रैवर्सल एल्गोरिदम रिकर्सिव DFS ट्रैवर्सल है।
इनपुट - ग्राफ़ का एडजेंसी मैट्रिक्स
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
आउटपुट - ग्राफ़ कनेक्टेड है।
एल्गोरिदम
traverse(u, visited) इनपुट: स्टार्ट नोड u और विज़िटेड नोड जिससे पता चले कि कौन सा नोड विज़िट हुआ है। आउटपुट: सभी कनेक्टेड वर्टेक्स ट्रैवर्स करें। Begin u को विज़िटेड मार्क करें सभी वर्टेक्स v के लिए, यदि u के साथ एडजेसेंट है, तो यदि v विज़िटेड नहीं है, तो traverse(v, visited) done End isConnected(graph) इनपुट: ग्राफ़। आउटपुट: यदि ग्राफ़ कनेक्टेड है तो True। Begin विज़िटेड ऐरे डिफाइन करें ग्राफ़ में सभी वर्टेक्स u के लिए, करें सभी नोड्स को अनविज़िटेड बनाएं traverse(u, visited) यदि कोई अनविज़िटेड नोड अभी भी शेष है, तो return false done return true End
उदाहरण
#include<iostream> #define NODE 5 using namespace std; int graph[NODE][NODE] = {{0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 1}, {1, 0, 0, 0, 0}, {0, 1, 0, 0, 0} }; void traverse(int u, bool visited[]){ visited[u] = true; //v को विज़िटेड मार्क करें for(int v = 0; v<NODE; v++){ if(graph[u][v]){ if(!visited[v]) traverse(v, visited); } } } bool isConnected(){ bool *vis = new bool[NODE]; //सभी वर्टेक्स u को स्टार्ट पॉइंट मानकर जांचें कि सभी नोड्स विज़िबल हैं या नहीं for(int u = 0; u < NODE; u++){ for(int i = 0; i<NODE; i++) vis[i] = false; //इनिशियलाइज़ करें कि कोई नोड विज़िटेड नहीं है traverse(u, vis); for(int i = 0; i<NODE; i++){ if(!vis[i]) //यदि कोई नोड ट्रैवर्सल द्वारा विज़िट नहीं हुआ, तो ग्राफ़ कनेक्टेड नहीं है return false; } } return true; } int main(){ if(isConnected()) cout << "The Graph is connected."; else cout << "The Graph is not connected."; }आउटपुट
The Graph is connected.
