그래프 탐색 - 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의 활용 예로 위상 정렬이 있다. 위상 정렬은 상호 의존 관계에 있는 작업들간의 수행 순서를 정해준다. 다음은 위상 정렬의 동작 과정이다.

1. 작업들 간의 의존 관계를 그래프로 표현한다. 작업 v가 u에 의존한다면 그래프는 간선 (v, u)를 포함한다. 모순이 없다면 그래프는 DAG 형태가 된다.
2. 작업들간의 수행 순서를 알기 위해서 DAG의 각 정점을 일렬로 나열한다. 이때 모든 정점의 의존성이 만족하도록 모든 간선이 왼쪽에서 오른쪽으로 가도록 정점을 나열한다. 정점 나열 순서가 위상 정렬의 결과가 된다.

DFS로 위상 정렬을 간단히 구현할 수 있다. DFS는 진출 차수가 0인 막힌 노드까지 깊이 탐색한다. 이 막힌 노드부터 DFS 방문 역순으로 출력하면 가장 늦게 할 작업부터 순서대로 출력이 되고 이 순서를 역순으로 바꾸면 위상 정렬 결과가 된다. 따라서 아래와 같이 구현할 수 있다.

• DAG에 위의 dfsAll()을 수행하며 dfs()가 종료될 때마다 현재 정점의 번호를 기록한다. dfsAll()이 종료한 뒤 기록된 순서를 뒤집으면 위상 정렬 결과를 얻을 수 있다.

오일러 서킷

오일러 서킷 문제란 그래프의 모든 간선을 정확히 한번만 지나서 시작점으로 돌아오는 경로를 찾는 문제이다. 무향 그래프와 방향 그래프에서 모두 해결할 수 있다. 무향 그래프에서 오일러 서킷이 존재하려면 아래의 조건을 만족해야한다.

• 그래프의 모든 간선이 한 컴포넌트에 있어야 한다.
• 시작점에서 시작하여 시작점으로 돌아와야하므로 시작점의 차수(인접 간선의 개수)는 짝수이어야 한다.
• 끝나는 점은 무조건 시작점이어야 하므로 그 외 모든 정점의 차수는 짝수이어야 한다.

즉 그래프에 차수가 홀수인 정점이 존재하면 오일러 서킷은 존재하지 않는다. 그러면 역도 성립할까? 모든 정점의 차수가 짝수라면 오일러 서킷이 존재할까? 모든 간선이 한 컴포넌트에 있고 모든 정점의 차수가 짝수인 그래프에서 오일러 서킷을  찾는 알고리즘을 구현한다면 역도 성립하는 걸 증명할 수 있다. DFS를 응용하면 오일러 서킷을 구하는 알고리즘을 쉽게 작성할 수 있다. DFS가 더 나아갈 길이 없을 때까지 탐색하고 더 나아갈 길이 없으면 되돌아가는 방식임을 기억하자. DFS로 시작점부터 탐색하고 더 이상 갈 수 있는 간선이 없을 때까지 탐색한다면 하나의 오일러 서킷이 나온다. 그 후 되돌아가면서 아직 가지 않은 간선이 있는 V 정점을 만나면 V 정점을 시작으로 DFS가 수행될테고 그러면 V 정점을 시작점으로 한 오일러 서킷이 원래의 오일러 서킷에 추가된다.

DFS를 응용해 오일러 서킷 구하기

 

아래는 위 그래프에서 오일러 서킷을 구하는 코드이다. 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 스패닝 트리를 생성할 때 그래프의 모든 간선을 네 가지 중 하나로 분류할 수 있다.

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;
    }
}