Cho đồ thị vô hướng, in tất cả chu trình trong đồ thị.
Đồ thị vô hướng có cạnh hai chiều. Chu trình là đường đi bắt đầu và kết thúc tại cùng đỉnh.
Ví dụ:
Cycle 1: 2 3 4 5 Cycle 2: 6 7 8
Giải pháp: Dùng DFS tô màu đỉnh. Nếu gặp đỉnh đang thăm (màu 1) -> tìm thấy chu trình. Backtrack đánh dấu các đỉnh trong chu trình.
Thuật toán
B1: Gọi DFS tô màu đỉnh. B2: Nếu gặp đỉnh đang thăm, backtrack đến đỉnh đó, đánh dấu số thứ tự chu trình. B3: Sau DFS, gom các đỉnh theo số chu trình vào danh sách kề riêng. B4: In các chu trình theo số thứ tự.
Chương trình minh họa
#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], par[N], mark[N];
int cyclenumber = 0;
cout << "Các chu trình trong đồ thị:\n";
int edges = 13;
DFSCycle(1, 0, color, mark, par, cyclenumber);
printCycles(edges, mark, cyclenumber);
return 0;
}
Kết quả
Cycle 1: 2 3 4 5 Cycle 2: 6 7 8