Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: DFS का उपयोग करके निर्देशित ग्राफ की कनेक्टिविटी जांचना


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

C++ प्रोग्राम: DFS का उपयोग करके निर्देशित ग्राफ की कनेक्टिविटी जांचना

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

इस मामले में ट्रैवर्सल एल्गोरिदम पुनरावर्ती DFS ट्रैवर्सल है।

इनपुट: ग्राफ का आसन्नता मैट्रिक्स

01000
00100
00011
10000
01000

आउटपुट: ग्राफ जुड़ा हुआ है।

एल्गोरिदम

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 << "ग्राफ जुड़ा हुआ नहीं है."; }

आउटपुट

ग्राफ जुड़ा हुआ है.

  1. C++ प्रोग्राम: BFS का उपयोग करके डायरेक्टेड ग्राफ की कनेक्टिविटी जांचना C++ प्रोग्राम: BFS का उपयोग करके डायरेक्टेड ग्राफ की कनेक्टिविटी जांचना

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

  1. C++ प्रोग्राम: BFS का उपयोग करके अनडायरेक्टेड ग्राफ की कनेक्टिविटी जांचना C++ प्रोग्राम: BFS का उपयोग करके अनडायरेक्टेड ग्राफ की कनेक्टिविटी जांचना

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

  1. C++ प्रोग्राम: जांचें कि क्या एक निर्देशित ग्राफ में यूलरियन चक्र है C++ प्रोग्राम: जांचें कि क्या एक निर्देशित ग्राफ में यूलरियन चक्र है

    यूलर चक्र/सर्किट एक पथ है; जिसके द्वारा हम प्रत्येक एज को ठीक एक बार देख सकते हैं। हम एक ही वर्टेक्स का कई बार उपयोग कर सकते हैं। यूलर सर्किट यूलर पथ का एक विशेष प्रकार है। जब यूलर पथ का प्रारंभिक वर्टेक्स उस पथ के अंतिम वर्टेक्स से भी जुड़ा होता है, तो इसे यूलर सर्किट कहा जाता है। यह जांचने के लि