พิมพ์รอบทั้งหมดในกราฟไม่มีทิศทางใน C++

ในปัญหานี้ เราได้รับกราฟแบบไม่บอกทิศทาง และเราต้องพิมพ์วงจรทั้งหมดที่เกิดขึ้นในกราฟ

กราฟไม่มีทิศทาง เป็นกราฟที่เชื่อมเข้าด้วยกัน ขอบทั้งหมดของกราฟทิศทางเดียวเป็นแบบสองทิศทาง เป็นที่รู้จักกันว่าเครือข่ายที่ไม่มีทิศทาง

รอบ ในโครงสร้างข้อมูลกราฟเป็นกราฟที่จุดยอดทั้งหมดก่อตัวเป็นวงจร

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากันดีกว่า −

กราฟ-

ผลลัพธ์-

Cycle 1: 2 3 4 5
Cycle 2: 6 7 8

สำหรับสิ่งนี้ เราจะใช้คุณสมบัติบางอย่างของกราฟ คุณต้องใช้วิธีการระบายสีกราฟและระบายสีจุดยอดทั้งหมดที่เกิดขึ้นในกราฟวงกลม นอกจากนี้ หากมีการเข้าไปที่จุดยอดเพียงบางส่วน ก็จะทำให้เกิดกราฟวงกลม ดังนั้น เราจะระบายสีจุดยอดนี้และจุดยอดถัดไปทั้งหมดจนกว่าจะถึงจุดเดียวกันอีกครั้ง

อัลกอริทึม

Step 1: call DFS traversal for the graph which can color the vertices.
Step 2: If a partially visited vertex is found, backtrack till the vertex is
reached again and mark all vertices in the path with a counter which is cycle number.
Step 3: After completion of traversal, iterate for cyclic edge and push them
into a separate adjacency list.
Step 4: Print the cycles number wise from the adjacency list.

ตัวอย่าง

#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&amp; 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&amp; 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