พิมพ์ Cycles ทั้งหมดใน Undirected Graph ใน C++

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

Undirected Graph คือ graph ที่เชื่อมต่อกัน ทุก edges ของ undirected graph เป็น bidirectional เรียกอีกอย่างว่า undirected network

Cycle ในโครงสร้างข้อมูล graph คือ graph ที่ vertices ทั้งหมดสร้างเป็น cycle

ตัวอย่างเพื่อความเข้าใจ

Graph-

Output-

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

สำหรับเรื่องนี้ เราจะใช้คุณสมบัติบางอย่างของ graph ต้องใช้ graph coloring method และสี vertices ที่เกิดใน cyclic graph นอกจากนี้ ถ้า vertex ถูกเยี่ยมชมบางส่วน จะเกิด cyclic graph ขึ้น ดังนั้นเราจะสี vertex นี้และ vertex ถัดไปทั้งหมดจนถึง vertex เดียวกันอีกครั้ง

อัลกอริทึม

ขั้นตอนที่ 1: เรียก DFS traversal สำหรับ graph ซึ่งสามารถสี vertices ได้
ขั้นตอนที่ 2: ถ้าพบ partially visited vertex ให้ backtrack จนถึง vertex เดียวกันอีกครั้ง และ mark vertices ทั้งหมดใน path ด้วย counter ซึ่งเป็น cycle number
ขั้นตอนที่ 3: หลังจบ traversal ให้วนลูป cyclic edge และ push ลง adjacency list แยก
ขั้นตอนที่ 4: พิมพ์ cycles ตามหมายเลขจาก 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);
}

ผลลัพธ์

Cycles in the Graph are -

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