ในปัญหานี้ เราได้รับกราฟแบบไม่บอกทิศทาง และเราต้องพิมพ์วงจรทั้งหมดที่เกิดขึ้นในกราฟ
กราฟไม่มีทิศทาง เป็นกราฟที่เชื่อมเข้าด้วยกัน ขอบทั้งหมดของกราฟทิศทางเดียวเป็นแบบสองทิศทาง เป็นที่รู้จักกันว่าเครือข่ายที่ไม่มีทิศทาง
รอบ ในโครงสร้างข้อมูลกราฟเป็นกราฟที่จุดยอดทั้งหมดก่อตัวเป็นวงจร
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากันดีกว่า −
กราฟ-
ผลลัพธ์-
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& 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