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