그래프 탐색 - DFS
DFS
그래프의 모든 정점을 특정한 순서에 따라 방문하는 알고리즘을 그래프의 탐색 알고리즘이라 한다. 대표적인 알고리즘으로 DFS(depth-first search)와 BFS(breadth-first search)가 있다.
DFS는 그래프를 더 나아갈 길이 없을 때까지 깊이 들어가 탐색하며 더 나아갈 수 없다면 되돌아가는 방식이다. 즉 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가고 더 이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다.
아래는 인접 행렬을 탐색하는 DFS 코드이다.
static void DFS(int v, int[][] graph, boolean visit[]) {
System.out.println(v);
visit[v] = true;
for(int i=0; i<graph.length; i++) {
if(graph[v][i] == 1 && !visit[i]) {
DFS(i, graph, visit);
}
}
}
static void dfsAll(int[][] graph, boolean visit[]) {
for(int i=0; i<visit.length; i++)
if(!visit[i]) DFS(i,graph,visit);
}DFS의 시간 복잡도
DFS는 정확히 정점의 개수(V) 만큼 호출된다. DFS의 성능은 인접 간선을 검사하는 for문에 의해 지배되므로 인접 리스트에서의 DFS 시간 복잡도는 O(V + E)가 되며 인접 행렬에서의 DFS 시간 복잡도는 O(V²)가 된다.
위상 정렬
DFS의 활용 예로 위상 정렬이 있다. 위상 정렬은 상호 의존 관계에 있는 작업들간의 수행 순서를 정해준다. 다음은 위상 정렬의 동작 과정이다.
- 작업들 간의 의존 관계를 그래프로 표현한다. 작업 v가 u에 의존한다면 그래프는 간선 (v, u)를 포함한다. 모순이 없다면 그래프는 DAG 형태가 된다.
- 작업들간의 수행 순서를 알기 위해서 DAG의 각 정점을 일렬로 나열한다. 이때 모든 정점의 의존성이 만족하도록 모든 간선이 왼쪽에서 오른쪽으로 가도록 정점을 나열한다. 정점 나열 순서가 위상 정렬의 결과가 된다.
DFS로 위상 정렬을 간단히 구현할 수 있다. DFS는 진출 차수가 0인 막힌 노드까지 깊이 탐색한다. 이 막힌 노드부터 DFS 방문 역순으로 출력하면 가장 늦게 할 작업부터 순서대로 출력이 되고 이 순서를 역순으로 바꾸면 위상 정렬 결과가 된다. 따라서 아래와 같이 구현할 수 있다.
- DAG에 위의 dfsAll()을 수행하며 dfs()가 종료될 때마다 현재 정점의 번호를 기록한다. dfsAll()이 종료한 뒤 기록된 순서를 뒤집으면 위상 정렬 결과를 얻을 수 있다.
오일러 서킷
오일러 서킷 문제란 그래프의 모든 간선을 정확히 한번만 지나서 시작점으로 돌아오는 경로를 찾는 문제이다. 무향 그래프와 방향 그래프에서 모두 해결할 수 있다. 무향 그래프에서 오일러 서킷이 존재하려면 아래의 조건을 만족해야한다.
- 그래프의 모든 간선이 한 컴포넌트에 있어야 한다.
- 시작점에서 시작하여 시작점으로 돌아와야하므로 시작점의 차수(인접 간선의 개수)는 짝수이어야 한다.
- 끝나는 점은 무조건 시작점이어야 하므로 그 외 모든 정점의 차수는 짝수이어야 한다.
즉 그래프에 차수가 홀수인 정점이 존재하면 오일러 서킷은 존재하지 않는다. 그러면 역도 성립할까? 모든 정점의 차수가 짝수라면 오일러 서킷이 존재할까? 모든 간선이 한 컴포넌트에 있고 모든 정점의 차수가 짝수인 그래프에서 오일러 서킷을 찾는 알고리즘을 구현한다면 역도 성립하는 걸 증명할 수 있다. DFS를 응용하면 오일러 서킷을 구하는 알고리즘을 쉽게 작성할 수 있다. DFS가 더 나아갈 길이 없을 때까지 탐색하고 더 나아갈 길이 없으면 되돌아가는 방식임을 기억하자. DFS로 시작점부터 탐색하고 더 이상 갈 수 있는 간선이 없을 때까지 탐색한다면 하나의 오일러 서킷이 나온다. 그 후 되돌아가면서 아직 가지 않은 간선이 있는 V 정점을 만나면 V 정점을 시작으로 DFS가 수행될테고 그러면 V 정점을 시작점으로 한 오일러 서킷이 원래의 오일러 서킷에 추가된다.
아래는 위 그래프에서 오일러 서킷을 구하는 코드이다. findRandomCircuit 함수가 종료될 때마다 정점을 리스트에 넣고 결과물인 서킷을 뒤집는 것에 유의하자.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int[][] graph = new int[8][8];
boolean[] visit = new boolean[8];
ArrayList<Integer> result = new ArrayList<>();
InitGraph(graph);
findRandomCircuit(0, result, graph);
Collections.reverse(result);
for(Integer v : result) {
System.out.print(v);
System.out.print(" ");
}
}
static void InitGraph(int[][] graph) {
graph[0][1] = 1; graph[1][0] = 1;
graph[1][2] = 1; graph[2][1] = 1;
graph[2][3] = 1; graph[3][2] = 1;
graph[3][7] = 1; graph[7][3] = 1;
graph[7][0] = 1; graph[0][7] = 1;
graph[3][4] = 1; graph[4][3] = 1;
graph[4][5] = 1; graph[5][4] = 1;
graph[5][6] = 1; graph[6][5] = 1;
graph[6][3] = 1; graph[3][6] = 1;
}
static void findRandomCircuit(int v, ArrayList<Integer> result, int[][] graph) {
for(int i=0; i<graph.length; i++) {
if(graph[v][i] > 0) {
//양쪽 간선을 모두 지운다.
graph[v][i]--;
graph[i][v]--;
findRandomCircuit(i, result, graph);
}
}
result.add(v);
}
}오일러 트레일
오일러 서킷처럼 모든 간선을 정확히 한 번씩 지나지만, 시작점과 끝점이 다른 경로를 오일러 트레일이라 한다. 무향 그래프에서 오일러 트레일이 존재하려면 시작점과 끝점의 차수가 홀수이고 나머지 정점의 차수는 짝수이어야 한다. 오일러 트레일 또한 DFS를 응용하여 쉽게 구할 수 있다.
간선의 분류
간선을 분류하면 그래프 구조를 더 파악할 수 있으며 그래프 알고리즘 작성에 유용하다. DFS로 그래프를 탐색해 탐색이 따라가는 간선들을 모아 보면 트리 형태를 띠게 된다. 이러한 트리를 DFS 스패닝 트리(DFS Spanning Tree)라고 부른다. DFS 스패닝 트리를 생성할 때 그래프의 모든 간선을 네 가지 중 하나로 분류할 수 있다.
- 트리 간선(tree edge) : 스패닝 트리에 속한 간선을 의미한다. 위 그림에서 굵은 선으로 표시된 간선이 모두 트리 간선이다.
- 순방향 간선(forward edge) : 스패닝 트리의 선조에서 자손으로 연결된 간선을 의미한다. (0,6) 간선이 순방향 간선에 속한다.
- 역방향 간선(back edge) : 스패닝 트리의 자손에서 선조로 연결된 간선을 의미한다. (2,0) 간선이 역방향 간선에 속한다.
- 교차 간선(cross edge) : 이 세가지 분류를 제외한 나머지 간선들을 의미한다. 즉 선조와 자손 관계가 아닌 정점들 간에 연결된 간선을 의미한다. (4, 2) 간선과 (6, 3) 간선이 교차 간선에 속한다.
방향 그래프에서는 위 4가지 간선으로 분류할 수 있지만 무향 그래프에서는 트리 간선과 트리 간선이 아닌 간선으로 밖에 분류할 수 없다. 교차 간선 (u, v)가 존재하려면 dfs(v)가 종료된 후 dfs(u)가 수행되어야 하는데 무방향 그래프에는 그럴 수 없다. 또한 역방향 간선과 순방향 간선의 구별도 할 수 없다.
그럼 간선을 어떻게 구분할까? dfs(u)를 수행해 간선 (u,v)를 발견했다고 가정했을 때 간선을 아래와 같이 분류 할 수 있다.
- 간선 (u,v)는 트리 간선 → v는 아직 방문되지 않음
- 간선 (u,v)는 순방향 간선 → u는 v의 선조, u는 v보다 먼저 방문됨
- 간선 (u,v)는 역방향 간선 → u는 v의 후손, u는 v보다 늦게 방문됨
- 간선 (u,v)는 교차 간선 → dfs(v)가 종료된 후 dfs(u)가 수행됨, u는 v보다 늦게 방문됨
import java.util.*;
import java.lang.*;
public class Main {
static int count = 0;
public static void main(String[] args) {
int[][] graph = new int[7][7];
int[] discovered = new int[7];
boolean[] finished = new boolean[7];
Arrays.fill(discovered, -1);
MakeGraph(graph);
dfs(0, graph, discovered, finished);
}
static void MakeGraph(int[][] graph) {
graph[0][1] = 1;
graph[0][4] = 1;
graph[0][5] = 1;
graph[0][6] = 1;
graph[1][2] = 1;
graph[2][0] = 1;
graph[4][2] = 1;
graph[5][3] = 1;
graph[5][6] = 1;
graph[6][3] = 1;
}
static void dfs(int v, int[][] graph, int[] discovered, boolean[] finished) {
discovered[v] = count;
count++;
for(int i=0; i<graph.length; i++) {
if(graph[v][i] == 1) {
System.out.print("(" + Integer.toString(v) + ", " + Integer.toString(i) + ") is a ");
if(discovered[i] == -1) {
System.out.println("트리 간선");
dfs(i, graph, discovered, finished);
}
else if(discovered[v] < discovered[i]) {
System.out.println("순방향 간선");
}
else {
if(finished[i]) System.out.println("교차 간선");
else System.out.println("역방향 간선");
}
}
}
finished[v] = true;
}
}