डायरेक्टेड ग्राफ में कनेक्टिविटी

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

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

इस मामले में, ट्रैवर्सल एल्गोरिदम रिकर्सिव 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 
  mark u as visited 
  for all vertex v, if it is adjacent with u, do 
    if v is not visited, then 
      traverse(v, visited) 
  done 
End

isConnected(graph)

इनपुट: ग्राफ

आउटपुट: True यदि ग्राफ कनेक्टेड है

Begin 
  define visited array 
  for all vertices u in the graph, do 
    make all nodes unvisited 
    traverse(u, visited) 
    if any unvisited node is still remaining, then 
      return false 
  done 
  return true 
End

उदाहरण

#include #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; //mark v as visited for(int v = 0; v

आउटपुट
The Graph is connected.