이 문제에서는 무방향 그래프가 주어지며, 그래프 안에서 형성되는 모든 사이클을 찾아 출력해야 합니다.
무방향 그래프(Undirected Graph)란 정점들이 간선으로 서로 연결되어 있고, 모든 간선이 양방향으로 통하는 그래프를 말합니다. 흔히 '무방향 네트워크'라고도 불립니다.
사이클(Cycle)은 그래프 자료구조에서 어떤 정점에서 출발해 간선을 따라 이동한 뒤, 다시 그 정점으로 돌아올 수 있는 순환 경로를 의미합니다.
예시를 통해 문제를 좀 더 구체적으로 살펴보겠습니다.
그래프 -
출력 -
Cycle 1: 2 3 4 5 Cycle 2: 6 7 8
이 문제를 해결하려면 그래프의 몇 가지 성질을 활용해야 합니다. 먼저 그래프 색칠(graph coloring) 기법을 사용하여 사이클에 포함된 모든 정점에 색을 칠합니다. 탐색 도중 부분적으로만 방문된 정점(탐색이 진행 중인 상태)을 다시 만나게 되면, 그 지점부터 사이클이 존재한다는 뜻입니다. 따라서 해당 정점부터 같은 정점에 다시 도달할 때까지 경로상의 모든 정점에 사이클 번호를 표시합니다.
알고리즘
1단계: 정점을 색칠하며 그래프를 탐색하는 DFS 순회를 호출합니다. 2단계: 부분 방문 상태인 정점을 다시 만나면, 해당 정점에 도달할 때까지 역추적하면서 경로상의 모든 정점에 사이클 번호를 표시합니다. 3단계: 탐색이 완료되면 사이클에 속한 정점들을 모아 별도의 인접 리스트에 저장합니다. 4단계: 인접 리스트를 이용해 사이클을 번호순으로 출력합니다.
예제 코드
#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
복잡도 분석
위 알고리즘은 각 정점과 간선을 최대 한 번씩만 방문하므로 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수를 의미합니다. 공간 복잡도 역시 색칠 배열, 부모 배열, 마킹 배열 등을 저장해야 하므로 O(V)입니다.