[DFS] 그래프 간선의 분류 / 사이클(Cycle) 찾기

 

 

  1. 깊이 우선 탐색(DFS)과 그래프 간선의 분류

어떤 방향 그래프를 깊이 우선 탐색(DFS)했을 때, 탐색이 따라간 간선들을 모으면 트리 형태를 가진다. 이때, 생성된 트리를 DFS 스패닝 트리 (DFS Spanning Tree)라고 부른다.

DFS 스패닝 트리를 구성하고 나면 기존 그래프에서의 간선들을 네 종류로 나눌 수 있다.

 

1. 트리 간선 (Tree Edge)

 - DFS 스패닝 트리에 포함된 간선

 

2. 순방향 간선 (Forward Edge)

 - DFS 스패닝 트리의 선조(ancestor)에서 자손(descendant)으로 가는 간선이면서, 트리에 포함되지 않은 간선

 

3. 역방향 간선 (Back Edge)

 - DFS 스패닝 트리의 자손에서 선조로 가는 간선이면서, 트리에 포함되지 않은 간선

 

4. 교차 간선(Cross Edge)

 - 위의 세 분류에 포함되지 않은 간선. 즉, 트리의 선조와 자손의 관계가 아니면서 트리에 포함되지 않은 간선

 

그림을 통해서 이해해보자.

 

다음과 같은 그래프가 있다고 가정하자. 1번 정점부터 DFS(깊이 우선 탐색)을 진행하면 아래와 같이 DFS 스패닝 트리가 생성된다. 

 

• 트리 간선 (Tree Edge) : 굵은 실선으로 표시된 간선들이 DFS 스패닝 트리를 구성하기 때문에 트리 간선이다.
• 순방향 간선 (Forward Edge) : 트리에서 1이 7의 선조이므로, 1 → 7 로 가는 점선으로 된 간선이 순방향 간선이다.
• 역방향 간선 (Back Edge) : 트리에서 5가 1의 자손이고, 6이 3의 자손이므로 5 → 1, 6 → 3으로 가는 점선으로 된 간선이 역방향 간선이다. 
• 교차 간선 (Cross Edge) : 4와 6은 트리에서 자손 관계가 성립하지 않으므로 6 → 4로 가는 점선으로 된 간선이 교차 간선이다. 

물론 DFS 과정에서 정점을 어떤 순서로 방문할지에 따라서 트리의 구조나 간선의 분류가 달라질 수 있다.

 

무방향 그래프에서는 모든 간선이 양방향으로 통행이 가능하기 때문에 교차 간선은 생길 수 없다. 그리고 순방향과 역방향의 구분또한 없다. 따라서 트리에 포함되거나, 포함되지 않는 간선 두 가지로 나뉘게 된다. 

 

---

그렇다면, 실제로 그래프가 주어졌을 때, 간선들을 어떻게 분류할 수 있을까?

 

우선, 트리 간선은 간단하게 확인할 수 있다. dfs(u) 내에서 간선 (u, v)를 확인할 때, v가 아직 방문하지 않은 정점이라면 (u, v)는 트리를 구성하게 된다.

반면, v가 이미 방문한 정점이라면 v가 u의 부모인지 자손인지 둘 다 아닌지 판별하기가 어렵다. 따라서 이를 판별하기 위해서 'dfs 정점 방문 순서'를 기록해둔다. 

 

1. (u, v)가 순방향 간선

 - v가 u의 자손이어야 한다. 따라서 v는 u보다 더 늦게 방문했어야 한다. 

 

2. (u, v)가 역방향 간선

 - v가 u의 선조이어야 한다. 따라서 v는 u보다 더 먼저 방문했어야 한다.

 

3. (u, v)가 교차 간선

 - dfs(v)가 dfs(u)보다 먼저 종료되어야 하므로 v가 u보다 더 먼저 방문했어야 한다. 

 

 

 

따라서, u를 먼저 방문했다면 (u, v)는 순방향 간선이고, v를 먼저 방문했고, dfs(v)가 아직 종료되지 않았다면 역방향 간선, v를 먼저 방문했고 dfs(v)가 종료되었다면 교차 간선이다. 

 

 

[소스 코드]

 

vector<vector<int>>adj;
vector<int> dfs_n; //dfs_n : 방문 순서
vector<int> finished; //dfs 종료 여부
vector<pii> tree, front, back, cross; //간선들 모음
int cnt;
void dfs(int u) {
	dfs_n[u] = cnt++;
	for (int v : adj[u]) {
		if (dfs_n[v] == -1) {
			tree.push_back({ u, v });
			dfs(v);
		}
		else if (dfs_n[u] < dfs_n[v]) front.push_back({ u, v });
		else if (finished[v] == 0) back.push_back({ u, v });
		else cross.push_back({ u, v });
	}
	finished[u] = 1; //dfs(u) 종료
}

 

 

 

  2. 그래프에서 사이클 존재 여부 확인

 

방향 그래프가 주어질 때, 그래프 내에 사이클이 존재하는지 판단해야 하는 경우가 종종 있다. 

이는, 역방향 간선의 존재 여부와 동치이다. 

 

예를 들어서 사이클이 존재한다고 하고, DFS 탐색 과정에서 제일 처음 만나는 사이클의 한 정점을 u라고 하자. 

u가 사이클에 속해있기 때문에 u로 향하는 정점 v가 있고, 이 v는 dfs(u)가 종료되기 이전에 방문하게 된다. 따라서 (v, u)는 항상 역방향 간선이 된다. 

 

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

 

사이클을 이루는 정점들의 개수를 구하는 문제이다. 

현재 간선 (u, v)가 역방향 간선인 경우는 v ~ u까지가 사이클을 이룬다는 의미이므로 여기에 포함된 정점의 수를 구해준다. 

 

[소스 코드]

 

#include<bits/stdc++.h>
#define ini(x, y) memset(x, y, sizeof(x));
using namespace std;

bool visited[100001];
bool finished[100001];
int P[100001];
int ans;
vector<vector<int>>adj;
void dfs(int u) {
	visited[u] = true;
	for (int v : adj[u]) {
		if (!visited[v]) {
			P[u] = v;
			dfs(v);
		}
		else if (!finished[v]) {
			for (int i = v; i != u; i = P[i]) {
				ans++;
			}
			ans++;
		}
	}
	finished[u] = true;
}

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		ans = 0;
		adj.assign(n + 1, vector<int>());
		ini(visited, false);
		ini(finished, false);
		ini(P, 0);
		for (int i = 1; i <= n; i++) {
			int a; cin >> a;
			adj[i].push_back(a);
		}
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) dfs(i);
		}
		cout << n-ans<<'\n';
	}
}

 

알고리즘 문제해결전략 (종만북) 참고하였습니다.

 

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^