3 Inseok Kong Schedule

Algorithms 10: Depth-First Search

깊이 우선 탐색으로 단일 출발점 도달 가능성을 풀고, Full-DFS로 연결 요소를 구하며, 종료 순서의 역순이 DAG의 위상 정렬이 됨을 증명하고 사이클을 탐지하는 방법을 정리한다.

복습

지난 강의에서는 그래프의 정의(방향/무방향, 단순 그래프, 이웃, 차수), 정점을 인접 리스트로 대응시키는 그래프 표현, 경로와 단순 경로, 경로 길이, 거리, 최단 경로를 정리했다. 그래프 경로 문제는 다음과 같다.

  • Single_Pair_Reachability(G, s, t)
  • Single_Source_Reachability(G, s)
  • Single_Pair_Shortest_Path(G, s, t)
  • Single_Source_Shortest_Paths(G, s) (SSSP)

너비 우선 탐색(BFS)은 SSSP를 푸는 알고리즘이며, 적절한 자료구조를 쓰면 입력 크기에 선형인 \(O(\lvert V \rvert + \lvert E \rvert)\)에 동작한다.

이 강의의 예제 그래프는 두 개다. 정점은 모두 \(a, b, c, d, e, f\)다.

  • \(G_1\) (무방향): \(\{a, b\}\), \(\{a, d\}\), \(\{a, e\}\), \(\{b, e\}\), \(\{d, e\}\), \(\{c, e\}\). \(f\)는 고립 정점이다.
  • \(G_2\) (방향): \((a, b)\), \((a, d)\), \((b, e)\), \((e, a)\), \((e, d)\), \((c, e)\), \((c, f)\).

Undirected example graph G1 with vertices a to f 강의 노트의 무방향 예제 그래프 \(G_1\). 정점 \(e\)가 \(a, b, c, d\) 네 정점과 연결된 중심이고, \(f\)는 간선이 없는 고립 정점이다. 출처: MIT 6.006 Lecture 10 notes (CC BY-NC-SA 4.0).

그림에서 간선을 세면 위 목록의 여섯 개와 같다. 이 그래프에는 사이클이 여러 개 있다. 예를 들어 \(a - b - e - a\)와 \(a - d - e - a\)는 각각 길이 3인 사이클이다. 사이클이 있으면 같은 정점에 도달하는 경로가 여러 개 생기므로, DFS가 “이미 방문한 정점은 다시 방문하지 않는다”는 규칙을 지켜야 무한히 돌지 않는다. 또 \(f\)는 어느 정점과도 연결되어 있지 않으므로 \(a\)에서 시작한 DFS로는 방문되지 않는다. 이 점이 뒤에서 Full-DFS와 연결 요소를 다루는 동기가 된다.

깊이 우선 탐색 (DFS)

깊이 우선 탐색(depth-first search, DFS) 은 BFS처럼 정점 \(s\)에서 그래프를 탐색한다.

  • SSSP가 아니라 단일 출발점 도달 가능성(Single Source Reachability) 을 푼다. 뒤에서 보듯 다른 문제를 푸는 데도 유용하다.
  • \(s\)로 돌아가는 부모 포인터의 트리를 반환하지만, 이 트리가 최단 경로를 나타내지는 않는다.

아이디어. 나가는 이웃을 재귀적으로 방문하되, 이미 방문한 정점은 다시 방문하지 않는다. 즉 막힐 때까지 아무 경로나 따라가고, 탐색하지 않은 경로가 나올 때까지 되돌아간다(backtrack).

\(P(s) = \text{None}\)으로 두고 visit(s)를 실행한다. visit(u)는 다음과 같다.

  • \(P\)에 없는 모든 \(v \in \text{Adj}(u)\)에 대해 \(P(v) = u\)로 두고 visit(v)를 재귀 호출한다.
  • 그 후 \(u\)의 방문을 마친다(finish). 이 시점은 뒤에서 쓰인다.

Recitation의 구현은 다음과 같다. 방문을 마친 순서도 함께 기록한다.

def dfs(Adj, s, parent=None, order=None):   # Adj: 인접 리스트, s: 시작 정점
    if parent is None:                       # 부모 배열 초기화
        parent = [None for v in Adj]         # O(V) (이름이 없으면 해시 사용)
        parent[s] = s                        # 뿌리
        order = []                           # 종료 순서
    for v in Adj[s]:                         # O(Adj[s]) 이웃 순회
        if parent[v] is None:                # 아직 부모가 없으면
            parent[v] = s                    # 부모 지정
            dfs(Adj, v, parent, order)       # 재귀 호출
    order.append(s)                          # s의 방문을 마침
    return parent, order

Recursive dfs code from recitation with cost comments Recitation의 재귀 DFS 원본 코드. 오른쪽 주석이 각 줄의 비용을 적고 있으며, 첫 호출에서만 부모 배열과 종료 순서 리스트를 초기화한다. 출처: MIT 6.006 Recitation 10 notes (CC BY-NC-SA 4.0).

코드는 BFS 코드와 거의 같은 재료로 이루어져 있지만 순서가 다르다. BFS는 한 레벨의 모든 정점을 처리한 뒤 다음 레벨로 넘어가는 반면, DFS는 이웃 \(v\) 하나를 발견하자마자 dfs(Adj, v, parent, order)로 그 아래를 끝까지 탐색하고 나서야 \(s\)의 다음 이웃으로 돌아온다. 이 “발견 즉시 재귀”가 깊이 우선이라는 이름의 이유다.

주석을 따라 비용을 더하면, 각 정점은 parent[v] is None일 때 한 번만 재귀 호출되므로 for v in Adj[s] 반복은 정점마다 한 번, 총 \(\sum_u \deg(u) = O(\lvert E \rvert)\)번 돈다. 마지막 줄 order.append(s)는 \(s\)의 모든 이웃을 다 처리한 뒤에 실행되므로, order에는 정점이 방문을 마친 순서, 즉 종료 순서가 쌓인다. 이 리스트가 뒤의 위상 정렬에서 그대로 쓰인다.

예제

\(G_1\)에서 \(a\)부터 DFS를 실행하자(이웃은 알파벳 순서로 처리한다). \(a \to b \to e \to c\)로 내려가고, \(c\)에서 막혀 \(e\)로 돌아온 뒤 \(e \to d\)로 간다. 부모는 \(P(b) = a\), \(P(e) = b\), \(P(c) = e\), \(P(d) = e\)다. \(\delta(a, e) = 1\)이지만 트리의 경로는 \(a \to b \to e\)로 길이가 2이므로, DFS 트리는 최단 경로 트리가 아니다.

정확성

주장. DFS는 \(s\)에서 도달 가능한 모든 정점 \(v\)를 방문하고 \(P(v)\)를 올바르게 설정한다.

증명. \(s\)로부터 거리 \(k\) 이내의 정점에 대한 주장으로 바꿔 \(k\)에 대한 귀납법을 쓴다.

  • 기저(\(k = 0\)): \(s\)에 대해 \(P(s)\)가 올바르게 설정되고 \(s\)는 방문된다.
  • 귀납: \(\delta(s, v) = k' + 1\)인 정점 \(v\)를 생각한다. \(s\)에서 \(v\)로 가는 어떤 최단 경로에서 끝에서 두 번째 정점을 \(u\)라 하자. \(\delta(s, u) = k'\)이므로 귀납 가정에 의해 DFS는 \(u\)를 방문하고 \(P(u)\)를 올바르게 설정한다. \(u\)를 방문하는 동안 DFS는 \(v \in \text{Adj}(u)\)를 고려한다. \(v\)가 이미 \(P\)에 있으면 이미 방문된 것이고, 아니면 \(u\)를 방문하는 동안 방문된다. 어느 경우든 \(v\)는 방문되고 \(P\)에 올바르게 추가된다.

실행 시간

각 정점 \(u\)는 많아야 한 번 방문되고, 각 \(v \in \text{Adj}(u)\)마다 \(O(1)\) 시간이 든다. 따라서 작업량은 \(O(1) \times \sum_{u \in V} \deg(u) = O(\lvert E \rvert)\)이다. BFS와 달리 모든 정점의 거리를 반환하지 않으므로, DFS는 \(O(\lvert E \rvert)\) 시간에 동작한다. (Recitation 코드처럼 길이 \(\lvert V \rvert\)인 부모 배열을 초기화하면 \(O(\lvert V \rvert + \lvert E \rvert)\)이다.)

Full-BFS와 Full-DFS

한 정점에서 도달 가능한 정점뿐 아니라 그래프 전체를 탐색하고 싶다고 하자.

아이디어. 방문하지 않은 정점에서 그래프 탐색 알고리즘 \(A\)를 반복한다. 모든 정점이 방문될 때까지 다음을 반복한다.

  • 방문하지 않은 임의의 정점 \(s\)를 고르고, \(A\)로 \(s\)에서 도달 가능한 모든 정점을 탐색한다.

이 알고리즘을 Full-\(A\)라 부르며, \(A\)가 BFS나 DFS면 각각 Full-BFS, Full-DFS다. 모든 정점을 한 번씩 방문하므로 둘 다 \(O(\lvert V \rvert + \lvert E \rvert)\)에 동작한다. 개념적으로는 모든 정점으로 나가는 간선을 가진 보조 정점을 하나 추가하고 그 정점에서 탐색하는 것과 같다.

def full_dfs(Adj):                   # Adj: 인접 리스트
    parent = [None for v in Adj]     # O(V) (이름이 없으면 해시 사용)
    order = []                       # 종료 순서
    for v in range(len(Adj)):        # O(V) 정점 순회
        if parent[v] is None:        # 아직 방문하지 않았으면
            parent[v] = v            # 자기 자신을 부모로 (새 뿌리)
            dfs(Adj, v, parent, order)   # v에서 DFS (BFS도 가능)
    return parent, order

역사적 이유(특히 위상 정렬과의 관계) 때문에 “깊이 우선 탐색”은 한 정점에서의 탐색과 그래프 전체의 탐색을 모두 가리키는 말로 흔히 쓰인다.

그래프 연결성

  • 무방향 그래프에서 모든 정점 쌍을 잇는 경로가 있으면 그래프가 연결(connected) 되어 있다고 한다.
  • 방향 그래프에서는 \(v\)에서 \(u\)에 도달할 수 있어도 \(u\)에서 \(v\)에 도달하지 못할 수 있다. 방향 그래프의 연결성은 더 복잡하며 이 수업에서는 다루지 않는다.
  • Connectivity(G): 무방향 그래프 \(G\)가 연결되어 있는가?
  • Connected_Components(G): 무방향 그래프 \(G = (V, E)\)가 주어지면 \(V\)를 부분집합 \(V_i \subseteq V\)(연결 요소, connected component)로 분할해 반환한다. 각 \(V_i\)는 \(G\)에서 연결되어 있고, 서로 다른 연결 요소의 정점 사이에는 간선이 없다.

주장. 단일 출발점 도달 가능성을 푸는 그래프 알고리즘 \(A\)로 연결 요소 문제를 풀 수 있다.

증명. Full-\(A\)를 실행한다. \(A\)의 각 실행에서 방문한 정점들을 하나의 연결 요소로 묶는다.

예를 들어 \(G_1\)에서 Full-DFS를 실행하면 연결 요소는 \(\{a, b, c, d, e\}\)와 \(\{f\}\)다.

DFS 간선 분류

DFS에 관한 성질을 증명할 때는 그래프의 간선을 DFS 트리 기준으로 분류하면 편리하다(Recitation). 간선 \((u, v)\)에 대해 다음과 같다.

  • 트리 간선(tree edge): DFS 트리에 속한다. 즉 parent[v] = u다.
  • 역방향 간선(back edge): \(u\)가 \(v\)의 자손이다.
  • 순방향 간선(forward edge): \(v\)가 \(u\)의 자손이다.
  • 교차 간선(cross edge): 둘 다 서로의 자손이 아니다.

무방향 그래프에서 DFS를 실행하면 순방향 간선과 교차 간선은 생기지 않는다. 역방향 간선은 탐색 중에 각 정점의 조상 집합을 (직접 접근 배열이나 해시 테이블로) 유지하면 찾을 수 있다. \(s\)의 이웃 \(v\)를 처리할 때 \(v\)가 \(s\)의 조상이면 \((s, v)\)는 역방향 간선이고, 이는 사이클이 있다는 증거다.

위상 정렬

  • 방향 비순환 그래프(directed acyclic graph, DAG) 는 방향 사이클이 없는 방향 그래프다.
  • 그래프 \(G = (V, E)\)의 위상 순서(topological order) 는 모든 간선 \((u, v) \in E\)가 \(f(u) < f(v)\)를 만족하는 정점의 순서 \(f\)다.
  • 연습: 방향 그래프가 위상 순서를 가질 필요충분조건은 DAG인 것이다.

위상 순서는 어떻게 찾을까? Full-DFS가 각 정점의 방문을 마치는 순서를 종료 순서(finishing order) 라 한다.

주장. \(G = (V, E)\)가 DAG이면 종료 순서의 역순은 위상 순서다.

증명. 모든 간선 \((u, v) \in E\)에 대해 \(u\)가 \(v\)보다 앞에 온다는 것, 즉 \(v\)의 방문이 \(u\)의 방문보다 먼저 끝난다는 것을 보이면 된다. 두 경우가 있다.

  • \(u\)를 \(v\)보다 먼저 방문한 경우: \(u\)의 방문이 끝나기 전에 (\((u, v)\)를 통해서든 다른 경로로든) \(v\)를 방문한다. 따라서 \(v\)의 방문이 \(u\)보다 먼저 끝난다.
  • \(v\)를 \(u\)보다 먼저 방문한 경우: 그래프가 비순환이므로 \(v\)에서 \(u\)에 도달할 수 없다. 따라서 \(u\)를 방문하기 전에 \(v\)의 방문이 끝난다.

사이클 탐지

  • Full-DFS는 그래프 \(G = (V, E)\)가 비순환이면 위상 순서를 찾는다.
  • 따라서 Full-DFS의 종료 순서의 역순이 위상 순서가 아니면 \(G\)에는 사이클이 있다.
  • \(G\)가 비순환인지 확인하려면 각 간선 \((u, v)\)에 대해 역종료 순서에서 \(v\)가 \(u\)보다 앞에 오는지 확인한다. 해시 테이블이나 직접 접근 배열로 \(O(\lvert E \rvert)\)에 할 수 있다.
  • 사이클 자체를 반환하려면 Full-DFS에서 \(s\)까지 거슬러 올라가는 경로의 조상 집합을 유지한다.

주장. \(G\)에 사이클이 있으면 Full-DFS는 어떤 정점 \(v\)에서 \(v\)의 조상으로 가는 간선을 지난다.

증명. \(G\)의 사이클 \((v_0, v_1, \dots, v_k, v_0)\)를 생각한다.

  • 일반성을 잃지 않고 \(v_0\)를 Full-DFS가 이 사이클에서 처음 방문하는 정점이라 하자.
  • 각 \(v_i\)에 대해, \(v_i\)의 방문이 끝나기 전에 \(v_{i+1}\)을 방문하고 마친다. 간선 \((v_i, v_{i+1})\)를 고려할 때 \(v_{i+1}\)을 아직 방문하지 않았다면 지금 방문하기 때문이다.
  • 따라서 \(v_0\)의 방문이 끝나기 전에 (\(v_0\)에 대한 가정에 의해 처음으로) \(v_k\)를 방문한다.
  • 그러므로 \(v_k\)의 방문이 끝나기 전에 간선 \((v_k, v_0)\)를 고려하는데, \(v_0\)는 \(v_k\)의 조상이다.

조상 집합을 유지하며 역방향 간선을 찾는 DFS는 다음처럼 쓸 수 있다. 역방향 간선 \((s, v)\)를 찾으면 \(s\)에서 부모 포인터를 따라 \(v\)까지 올라가 사이클을 얻는다.

def dfs_find_back_edge(Adj, s, parent, order, active):
    active[s] = True                 # s가 현재 재귀 경로(조상 집합)에 들어감
    for v in Adj[s]:
        if active[v]:                # v가 s의 조상: 역방향 간선
            return (s, v)
        if parent[v] is None:
            parent[v] = s
            e = dfs_find_back_edge(Adj, v, parent, order, active)
            if e is not None:
                return e
    active[s] = False                # s의 방문을 마침
    order.append(s)
    return None

예제

Directed example graph G2 with the cycle a, b, e 강의 노트의 방향 예제 그래프 \(G_2\). 화살표 \(a \to b \to e \to a\)가 방향 사이클을 이루며, \(c\)는 들어오는 간선이 없는 정점이다. 출처: MIT 6.006 Lecture 10 notes (CC BY-NC-SA 4.0).

그림에서 사이클을 먼저 찾아 두면 아래 실행 과정을 따라가기 쉽다. \(a\)에서 \(b\)로, \(b\)에서 \(e\)로, 그리고 \(e\)에서 다시 \(a\)로 돌아오는 화살표가 있다. 이 세 정점 중 어느 것을 위상 순서의 맨 앞에 두어도 사이클의 마지막 간선이 거꾸로 가게 되므로, \(G_2\)에는 위상 순서가 없다. 나머지 간선 \((a, d)\), \((e, d)\), \((c, e)\), \((c, f)\)는 사이클에 속하지 않는다. 특히 \(c\)는 들어오는 간선이 없어 \(a\)에서 시작한 DFS로는 방문되지 않으므로 Full-DFS의 두 번째 뿌리가 된다.

\(G_2\)에서 알파벳 순서로 Full-DFS를 실행하자. \(a\)에서 시작해 \(a \to b \to e\)로 간다. \(e\)에서 간선 \((e, a)\)를 보는데 \(a\)는 \(e\)의 조상이므로 역방향 간선이며, 사이클 \((a, b, e, a)\)가 있다. 계속하면 \(e \to d\)를 방문하고 \(d, e, b, a\) 순으로 마친다. 다음으로 \(c\)에서 시작해 \(f\)를 방문하고 \(f, c\) 순으로 마친다.

종료 순서는 \(d, e, b, a, f, c\)이고 역순은 \(c, f, a, b, e, d\)다. 간선 \((e, a)\)에서 \(a\)가 \(e\)보다 앞에 오므로 위상 순서가 아니며, 이로써 사이클이 있음을 알 수 있다. 간선 \((e, a)\)를 지우면 \(G_2\)는 DAG가 되고, 같은 역순 \(c, f, a, b, e, d\)는 실제로 위상 순서다.

Recitation 연습: 졸업장 수여 순서

문제. 고등학교에는 여러 학생 조직이 있고 각 조직은 위계 구조를 가진다. 교장은 어떤 조직에서든 \(a\)가 \(b\)를 감독하면 \(a\)에게 \(b\)보다 먼저 졸업장을 주려 한다. 이런 순서를 찾거나, 없음을 보여야 한다.

풀이. 학생마다 정점을 두고, \(a\)가 \(b\)를 감독하면 방향 간선 \((a, b)\)를 둔다. 그래프 전체에 DFS를 실행해 \(O(\lvert V \rvert + \lvert E \rvert)\)에 종료 순서를 얻는다. 그동안 조상 집합을 유지하며 역방향 간선이 있는지 본다. 역방향 간선 \((u, v)\)를 찾으면 \(u\)에서 \(v\)까지 부모 포인터를 따라 방향 사이클을 얻어, 그런 순서가 없음을 보인다. 사이클이 없으면 종료 순서의 역순이 원하는 위상 순서다.

정리

  • DFS는 막힐 때까지 경로를 따라가고 되돌아오며, 방문하지 않은 이웃만 재귀적으로 방문한다. 단일 출발점 도달 가능성을 \(O(\lvert E \rvert)\)에 풀지만, DFS 트리는 최단 경로 트리가 아니다.
  • Full-BFS와 Full-DFS는 방문하지 않은 정점에서 탐색을 반복해 그래프 전체를 \(O(\lvert V \rvert + \lvert E \rvert)\)에 탐색하며, 각 실행이 무방향 그래프의 연결 요소 하나를 이룬다.
  • DFS 트리를 기준으로 간선을 트리, 역방향, 순방향, 교차 간선으로 분류할 수 있다.
  • DAG에서 Full-DFS의 종료 순서를 뒤집으면 위상 순서가 된다.
  • 역종료 순서가 위상 순서가 아니면 사이클이 있으며, 조상으로 가는 역방향 간선을 찾아 사이클을 반환할 수 있다.