ग्राफ की कनेक्टिविटी जांचने के लिए, हम किसी भी ट्रैवर्सल एल्गोरिदम का उपयोग करके सभी नोड्स को पार करने का प्रयास करेंगे। ट्रैवर्सल पूरा होने के बाद, यदि कोई नोड है, जिसे विज़िट नहीं किया गया है, तो ग्राफ जुड़ा हुआ नहीं है।

निर्देशित ग्राफ के लिए, हम कनेक्टिविटी जांचने के लिए सभी नोड्स से ट्रैवर्स करना शुरू करेंगे। कभी-कभी एक एज में केवल जावक एज हो सकती है लेकिन कोई आवक एज नहीं, इसलिए वह नोड किसी अन्य प्रारंभिक नोड से अविज़िटेड रहेगा।
इस मामले में ट्रैवर्सल एल्गोरिदम पुनरावर्ती 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 और विज़िट किए गए नोड को चिह्नित करने के लिए कि कौन सा नोड विज़िट किया गया है।
आउटपुट: सभी जुड़े हुए वर्टेक्स को पार करें।
शुरुआत u को विज़िट के रूप में चिह्नित करें सभी वर्टेक्स v के लिए, यदि यह u के साथ आसन्न है, तो करें यदि v विज़िट नहीं किया गया है, तो traverse(v, visited) हो गया अंत
isConnected(graph)
इनपुट: ग्राफ।
आउटपुट: सच यदि ग्राफ जुड़ा हुआ है।
शुरुआत विज़िट किए गए सरणी को परिभाषित करें ग्राफ में सभी वर्टेक्स u के लिए, करें सभी नोड्स को अविज़िटेड बनाएं traverse(u, visited) यदि कोई अविज़िटेड नोड अभी भी शेष है, तो गलत वापस करें हो गया सच वापस करें अंत
उदाहरण कोड
#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; 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 << "ग्राफ जुड़ा हुआ है."; else cout << "ग्राफ जुड़ा हुआ नहीं है."; }
आउटपुट
ग्राफ जुड़ा हुआ है.