इस समस्या में, हमें एक अप्रत्यक्ष ग्राफ दिया गया है और हमें ग्राफ में बने सभी चक्रों को प्रिंट करना है।
अप्रत्यक्ष ग्राफ एक ग्राफ है जो एक साथ जुड़ा हुआ है। अप्रत्यक्ष ग्राफ के सभी किनारे द्विदिशात्मक हैं। इसे अप्रत्यक्ष नेटवर्क के रूप में भी जाना जाता है।
चक्र ग्राफ डेटा संरचना में एक ग्राफ है जिसमें सभी शीर्ष एक चक्र बनाते हैं।
समस्या को बेहतर ढंग से समझने के लिए एक उदाहरण देखते हैं -
ग्राफ-
आउटपुट-
चक्र 1: 2 3 4 5 चक्र 2: 6 7 8
इसके लिए, हम ग्राफ के कुछ गुणों का उपयोग करेंगे। आपको ग्राफ कलरिंग विधि का उपयोग करना होगा और उन सभी शीर्षों को रंगना होगा जो एक चक्रीय ग्राफ में होते हैं। साथ ही, यदि एक शीर्ष आंशिक रूप से देखा गया है, तो यह एक चक्रीय ग्राफ को जन्म देगा। इसलिए, हम इस शीर्ष और अगले सभी शीर्षों को एक काउंटर के साथ चिह्नित करेंगे जो चक्र संख्या है जब तक कि वही शीर्ष फिर से नहीं पहुंच जाता।
एल्गोरिदम
चरण 1: ग्राफ के लिए DFS ट्रैवर्सल कॉल करें जो शीर्षों को रंग सकता है। चरण 2: यदि आंशिक रूप से देखा गया शीर्ष मिलता है, तो तब तक बैकट्रैक करें जब तक शीर्ष फिर से नहीं पहुंच जाता और पथ में सभी शीर्षों को एक काउंटर के साथ चिह्नित करें जो चक्र संख्या है। चरण 3: ट्रैवर्सल पूरा होने पर, चक्रीय किनारे के लिए पुनरावृति करें और उन्हें एक अलग आसन्न सूची में डालें। चरण 4: आसन्न सूची से चक्र संख्या के अनुसार प्रिंट करें।
उदाहरण
#include <bits/stdc++.h> using namespace std; const int N = 100000; vector<int> graph[N]; vector<int> cycles[N]; void DFSCycle(int u, int p, int color[], int mark[], int par[], int& cyclenumber){ if (color[u] == 2) { return; } if (color[u] == 1) { cyclenumber++; int cur = p; mark[cur] = cyclenumber; while (cur != u) { cur = par[cur]; mark[cur] = cyclenumber; } return; } par[u] = p; color[u] = 1; for (int v : graph[u]) { if (v == par[u]) { continue; } DFSCycle(v, u, color, mark, par, cyclenumber); } color[u] = 2; } void insert(int u, int v){ graph[u].push_back(v); graph[v].push_back(u); } void printCycles(int edges, int mark[], int& cyclenumber){ for (int i = 1; i <= edges; i++) { if (mark[i] != 0) cycles[mark[i]].push_back(i); } for (int i = 1; i <= cyclenumber; i++) { cout << "Cycle " << i << ": "; for (int x : cycles[i]) cout << x << " "; cout << endl; } } int main(){ insert(1, 2); insert(2, 3); insert(3, 4); insert(4, 5); insert(5, 2); insert(5, 6); insert(6, 7); insert(7, 8); insert(6, 8); int color[N]; int par[N]; int mark[N]; int cyclenumber = 0; cout<<"Cycles in the Graph are :\n"; int edges = 13; DFSCycle(1, 0, color, mark, par, cyclenumber); printCycles(edges, mark, cyclenumber); } आउटपुट
ग्राफ में चक्र हैं -
Cycle 1: 2 3 4 5 Cycle 2: 6 7 8
