अनिर्देशित ग्राफ में चक्र का पता लगाएं

यह पता लगाने के लिए कि अनिर्देशित ग्राफ में कोई चक्र है या नहीं, हम दिए गए ग्राफ के लिए DFS ट्रैवर्सल का उपयोग करेंगे। प्रत्येक देखे गए शीर्ष v के लिए, जब हमें कोई आसन्न शीर्ष u मिलता है, जैसे कि u पहले से देखा गया है, और u शीर्ष v का पैरेंट नहीं है। तब एक चक्र का पता चलता है।

हम मान लेंगे कि किन्हीं दो शीर्षों के लिए कोई समानांतर किनारे नहीं हैं।

इनपुट और आउटपुट: आसन्नता मैट्रिक्स      0 1 0 0 0      1 0 1 1 0      0 1 0 0 1      0 1 0 0 1      0 0 1 1 0 आउटपुट: ग्राफ में चक्र है।

एल्गोरिदम

dfs(vertex, visited, parent)
 
इनपुट: प्रारंभ शीर्ष, देखा गया समुच्चय, और शीर्ष का पैरेंट नोड।
आउटपुट: चक्र मिलने पर सच।शुरू     शीर्ष को देखे गए समुच्चय में जोड़ें     शीर्ष के साथ आसन्न सभी शीर्ष v के लिए, करें       यदि v = पैरेंट, तो         वापस करें सच       यदि v देखे गए समुच्चय में नहीं है, तो         वापस करें सच       यदि dfs(v, visited, vertex) सच है, तो         वापस करें सच     किया     वापस करें गलत अंत hasCycle(graph) इनपुट: दिया गया ग्राफ। आउटपुट: जब चक्र मिला तो सच।शुरू     ग्राफ में सभी शीर्ष v के लिए, करें       यदि v देखे गए समुच्चय में नहीं है, तो         अगले पुनरावृत्ति के लिए जाएं       यदि dfs(v, visited, ∅) सच है, तो         //v का पैरेंट null है         वापस करें सच         वापस करें गलत     किया अंत

उदाहरण

#include<iostream> #include<set> #define NODE 5 using namespace std; int graph[NODE][NODE] = {     {0, 1, 0, 0, 0},     {1, 0, 1, 1, 0},     {0, 1, 0, 0, 1},     {0, 1, 0, 0, 1},     {0, 0, 1, 1, 0} }; bool dfs(int vertex, set<int>&visited, int parent) {     visited.insert(vertex);     for(int v = 0; v
आउटपुट
The graph has cycle.