ग्राफ की कनेक्टिविटी जांचने के लिए, हम किसी भी ट्रैवर्सल एल्गोरिदम का उपयोग करके सभी नोड्स को ट्रैवर्स करने का प्रयास करेंगे। ट्रैवर्सल पूरा होने के बाद, यदि कोई नोड है, जो विजिट नहीं हुआ है, तो ग्राफ कनेक्टेड नहीं है।
अनडायरेक्टेड ग्राफ के लिए, हम एक नोड चुनेंगे और उससे ट्रैवर्स करेंगे।
इस मामले में ट्रैवर्सल एल्गोरिदम रिकर्सिव DFS ट्रैवर्सल है।
इनपुट - ग्राफ का एडजेसेंसी मैट्रिक्स
| 0 |
1 |
1 |
0 |
0 |
| 1 |
0 |
1 |
1 |
0 |
| 1 |
1 |
0 |
1 |
1 |
| 0 |
1 |
1 |
0 |
1 |
| 0 |
0 |
1 |
1 |
0 |
आउटपुट - ग्राफ कनेक्टेड है।
एल्गोरिदम
traverse(u, visited)
इनपुट - स्टार्ट नोड u और विजिटेड नोड यह मार्क करने के लिए कि कौन सा नोड विजिट हुआ है।
आउटपुट: सभी कनेक्टेड वर्टेक्स को ट्रैवर्स करें।
Begin
u को विजिटेड मार्क करें
सभी वर्टेक्स v के लिए, यदि यह u के साथ एडजेसेंट है, तो करें
यदि v विजिटेड नहीं है, तो
traverse(v, visited)
किया
End
isConnected(graph)
इनपुट - ग्राफ।
आउटपुट - यदि ग्राफ कनेक्टेड है तो True।
Begin
विजिटेड ऐरे परिभाषित करें
ग्राफ में सभी वर्टेक्स u के लिए, करें
सभी नोड्स को अनविजिटेड बनाएं
traverse(u, visited)
यदि कोई अनविजिटेड नोड अभी भी शेष है, तो
false लौटाएं
किया
true लौटाएं
End
उदाहरण कोड
#include <iostream>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {{0, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 1, 1},
{0, 1, 1, 0, 1},
{0, 0, 1, 1, 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.
