선택 심화: 단절점·low·이중 연결 성분

통신망에서 어느 장비 하나가 고장 나면 망이 둘로 갈라지는지, 도로망에서 어느 교차로가 막히면 오갈 수 없는 지역이 생기는지 알고 싶다고 해 봅시다. 그래프로 말하면, 지웠을 때 연결이 끊어지는 정점을 찾는 문제입니다. 정점을 하나씩 지워 보고 DFS로 연결을 확인해도 되지만, 그러면 DFS를 정점 수만큼 해야 합니다. 1973년 John Hopcroft와 Robert Tarjan은 DFS를 한 번만 하면서 각 정점에 두 가지 번호를 매겨, 이런 정점을 모두 O(V + E)에 찾는 방법을 발표했습니다. 이 글에서는 그 방법을 단순 무방향 그래프에서 구현하고, 같은 과정으로 그래프를 단단하게 이어진 덩어리들로 나누는 방법도 봅니다.

단절점과 이중 연결 성분

무방향 그래프에서 어떤 정점과 그 정점에 붙은 간선을 지웠을 때 연결 성분의 개수가 늘어나면, 그 정점을 단절점(articulation point, cut vertex)이라고 합니다. 삼각형 A, B, C에 꼬리 C—D가 붙은 그래프에서 C를 지우면 D가 떨어져 나가므로 C는 단절점이고, A나 B를 지워도 나머지는 이어져 있으므로 단절점이 아닙니다.

두 정점 사이에 길이 두 개 있다고 해서 정점 하나의 고장을 견딜 수 있는 것은 아닙니다. 두 길이 중간에 같은 정점을 지난다면 그 정점 하나가 막혔을 때 두 길이 모두 끊기기 때문입니다. 정점 하나를 지워도 끊어지지 않으려면, 두 길이 양 끝을 빼고는 정점을 하나도 함께 쓰지 않아야 합니다. 단절점이 없도록 단단하게 이어진 부분 가운데 더 키울 수 없는 것을 이중 연결 성분(biconnected component) 또는 블록(block)이라고 합니다. 앞의 그래프는 삼각형 A, B, C가 한 블록이고, 간선 C—D 하나가 또 한 블록입니다. 지우면 그래프가 끊어지는 C—D 같은 간선을 다리(bridge)라고 하는데, 다리는 그 간선 하나만으로 블록을 이룹니다. 간선을 지우는 경우를 기준으로 하는 이중 연결은 이와 다른 개념이라 여기서는 다루지 않습니다.

하나씩 지워 보는 방법

정의를 그대로 따르면, 정점마다 그 정점을 지운 그래프에서 연결 성분을 세어 원래보다 늘었는지 보면 됩니다. 느리지만 확실하므로, 뒤에서 만들 빠른 방법의 결과를 확인하는 기준으로 쓰겠습니다.

def count_components(graph, removed=None):
    seen, count = set(), 0
    for start in graph:
        if start == removed or start in seen:
            continue
        count += 1
        stack = [start]
        while stack:
            vertex = stack.pop()
            if vertex in seen:
                continue
            seen.add(vertex)
            stack.extend(n for n in graph[vertex] if n != removed)
    return count


def cut_vertices_slow(graph):
    base = count_components(graph)
    return sorted(v for v in graph if count_components(graph, v) > base)


graph = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B", "D"], "D": ["C"]}
print(cut_vertices_slow(graph))

['C']

count_components는 removed로 준 정점을 없는 것처럼 건너뛰며 연결 성분을 셉니다. 정점마다 DFS를 한 번씩 하므로 전체 시간은 O(V(V + E))입니다. 정점이 10만 개인 그래프라면 DFS를 10만 번 해야 합니다.

DFS 트리와 역방향 간선

빠른 방법은 무방향 그래프의 DFS가 가진 성질 하나에 기대고 있습니다. DFS를 하면 처음 방문할 때 지나간 간선들이 시작 정점을 루트로 하는 나무 모양을 이루는데, 이것을 DFS 트리라 하고 그 간선들을 트리 간선이라고 합니다. 트리 간선이 아닌 나머지 간선은 모두 어떤 정점과 그 정점의 조상, 곧 루트 쪽으로 거슬러 올라간 정점을 잇습니다. 이런 간선을 역방향 간선(back edge)이라고 합니다. 무방향 그래프에서는 서로 조상도 자손도 아닌 두 정점을 잇는 간선이 생기지 않습니다. DFS가 한 정점에 들어가면 그 정점에서 닿을 수 있는 미방문 정점을 모두 그 아래에서 방문한 뒤에야 돌아오기 때문입니다.

이 성질 덕분에, 어떤 정점 w와 그 아래의 자손들, 곧 w의 서브트리가 바깥과 이어지는 길은 두 가지뿐입니다. w와 그 부모 v를 잇는 트리 간선, 그리고 서브트리 안의 정점에서 v나 그보다 위의 조상으로 올라가는 역방향 간선입니다. 그래서 서브트리에서 v보다 위로 올라가는 역방향 간선이 하나도 없다면, v를 지우는 순간 w의 서브트리는 위쪽과 끊어집니다.

발견 번호와 low 값

이것을 계산하려고 정점마다 두 수를 기록합니다. 발견 번호 discovery[v]는 DFS가 v를 처음 방문한 순서로, 0부터 매깁니다. 조상은 자손보다 먼저 발견되므로 발견 번호가 작을수록 루트에 가깝습니다. low[v]는 v의 서브트리 안에서 출발해 역방향 간선을 많아야 하나 타고 닿을 수 있는 정점의 발견 번호 가운데 가장 작은 값으로, v 자신의 발견 번호도 후보에 넣습니다. 서브트리가 역방향 간선으로 얼마나 높이 올라갈 수 있는지를 나타내는 값입니다.

low 값은 DFS가 돌아오면서 계산할 수 있습니다. 처음에는 자기 발견 번호로 두고, 역방향 간선으로 이미 발견한 조상 u를 만나면 discovery[u]와 비교하고, 자식 w의 방문이 끝나 돌아오면 low[w]와 비교해 더 작은 값으로 고칩니다. 부모로 돌아가는 트리 간선은 역방향 간선이 아니므로 빼야 합니다. 이 간선까지 넣으면 루트가 아닌 모든 정점의 low가 부모의 발견 번호 이하가 되어 low가 위에서 정한 뜻과 달라지고, 아래 코드에서는 같은 간선이 반대 방향으로 간선 스택에 한 번 더 쌓여 블록에 두 번 들어갑니다.

단절점 판정

루트가 아닌 정점 v에 자식 w가 있고 low[w] >= discovery[v]라면 v는 단절점입니다. w의 서브트리가 역방향 간선으로 올라갈 수 있는 가장 높은 곳이 v이거나 그보다 아래라서, v를 지우면 서브트리가 v의 위쪽과 끊어지기 때문입니다. 등호인 경우, 곧 역방향 간선이 정확히 v까지 올라오는 경우도 v를 지우면 그 간선도 함께 사라지므로 끊어집니다.

루트는 위쪽이 없으므로 이 판정을 그대로 쓸 수 없습니다. 루트의 자식 w는 늘 low[w] >= discovery[루트]이기 때문입니다. 루트는 자기 DFS 트리에서 가장 먼저 발견되므로, 트리 안의 어떤 정점도 루트보다 작은 발견 번호를 갖지 않습니다. 대신 루트는 DFS 트리에서 자식이 둘 이상일 때만 단절점입니다. 서로 다른 자식의 서브트리 사이에는 간선이 없으므로, 자식이 둘 이상이면 루트를 지웠을 때 서브트리들이 서로 끊어집니다. 자식이 하나뿐이면 루트를 지워도 그 서브트리 하나가 남아 이어져 있습니다. 여기서 자식 수는 이웃 수가 아니라 DFS 트리의 자식 수라는 점에 주의해야 합니다. 삼각형에서 루트 A는 이웃이 B와 C로 둘이지만, B에서 C를 먼저 방문하므로 DFS 자식은 B 하나이고 단절점이 아닙니다. 반대로 간선 A—B와 A—C만 있는 그래프에서는 A의 DFS 자식이 B와 C로 둘이라 A가 단절점입니다.

간선 스택으로 블록 묶기

블록도 같은 DFS로 찾습니다. 간선을 처음 지날 때마다 간선 스택에 쌓아 두다가, 정점 v에서 자식 w의 방문을 마치고 low[w] >= discovery[v]를 확인한 순간, 스택에서 트리 간선 (v, w)가 나올 때까지 간선을 꺼냅니다. 꺼낸 간선들이 하나의 블록입니다. w의 서브트리 안에서 아직 다른 블록으로 꺼내지 않은 간선들은 v 위로 올라가지 못하고 v에서 막히므로, v와 함께 하나의 단단한 덩어리를 이룹니다.

삼각형 A, B, C와 꼬리 C—D에서 이웃 목록의 순서대로 따라가 보겠습니다. 간선 스택의 AB는 A에서 B로 지나간 간선 (A, B)를 짧게 적은 것이고, 왼쪽이 바닥, 오른쪽이 맨 위입니다.

D의 low가 3으로 남은 것은 D에서 위로 올라가는 역방향 간선이 없기 때문이고, 그래서 C가 단절점이 됩니다. C에서 B로 돌아올 때 간선 스택을 비우지 않은 것도 중요합니다. CA와 BC가 B에서 A로 돌아올 때까지 남아 있어야 AB와 함께 삼각형 하나의 블록이 됩니다. 마지막 줄에서 A가 C를 다시 보는 것은 C—A 간선의 반대쪽인데, C는 A보다 늦게 발견된 자손이므로 역방향 간선으로 다시 쌓지 않습니다.

코드로 옮기기

visit은 biconnected_components 안에서 정의한 중첩 함수(nested function)입니다. 바깥 함수의 discovery, low, parent, edge_stack, blocks, cuts를 그대로 읽고 고치며, 재귀로 불리는 모든 visit이 이 자료들을 함께 씁니다. 딕셔너리의 항목을 바꾸거나 리스트에 값을 붙이는 것은 변수 이름에 새 값을 대입하는 것이 아니므로, 따로 선언하지 않아도 바깥 변수를 고칠 수 있습니다. 반면 children은 visit이 불릴 때마다 0에서 새로 시작하는 지역 변수라서, 그 호출에서 처음 방문한 이웃의 수, 곧 DFS 자식 수를 셉니다. 재귀 호출이 쌓이는 호출 스택과, 아직 블록으로 꺼내지 않은 간선이 쌓이는 간선 스택은 서로 다른 것입니다.

def biconnected_components(graph):
    for vertex, neighbors in graph.items():
        if len(set(neighbors)) != len(neighbors) or vertex in neighbors:
            raise ValueError("같은 간선이 두 번 있거나 자기 자신으로 가는 간선이 있습니다")
        for neighbor in neighbors:
            if vertex not in graph.get(neighbor, []):
                raise ValueError("무방향 그래프는 양쪽 이웃 목록에 모두 적어야 합니다")
    discovery, low, parent, edge_stack = {}, {}, {}, []
    blocks, cuts = [], set()

    def visit(vertex):
        discovery[vertex] = low[vertex] = len(discovery)
        children = 0
        for neighbor in graph[vertex]:
            if neighbor not in discovery:
                parent[neighbor] = vertex
                children += 1
                edge_stack.append((vertex, neighbor))
                visit(neighbor)
                low[vertex] = min(low[vertex], low[neighbor])
                if low[neighbor] >= discovery[vertex]:
                    if vertex in parent or children > 1:
                        cuts.add(vertex)
                    block = []
                    while edge_stack:
                        edge = edge_stack.pop()
                        block.append(edge)
                        if edge == (vertex, neighbor):
                            break
                    blocks.append(block)
            elif neighbor != parent.get(vertex) and discovery[neighbor] < discovery[vertex]:
                edge_stack.append((vertex, neighbor))
                low[vertex] = min(low[vertex], discovery[neighbor])

    for vertex in graph:
        if vertex not in discovery:
            visit(vertex)
    return blocks, cuts


graph = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B", "D"], "D": ["C"]}
blocks, cuts = biconnected_components(graph)
print(sorted(sorted(tuple(sorted(edge)) for edge in block) for block in blocks))
print(sorted(cuts))
star = {"A": ["B", "C"], "B": ["A"], "C": ["A"]}
print(sorted(biconnected_components(star)[1]))

[[('A', 'B'), ('A', 'C'), ('B', 'C')], [('C', 'D')]]
['C']
['A']

처음 반복은 입력이 단순 무방향 그래프인지 확인합니다. 같은 이웃이 두 번 있거나 자기 자신이 이웃이면 거절하고, A의 목록에 B가 있는데 B의 목록에 A가 없으면 거절합니다. vertex in parent는 vertex에 부모가 있는지, 곧 루트가 아닌지를 묻고, parent.get(vertex)는 루트처럼 부모가 없으면 오류 대신 None을 돌려줍니다. 역방향 간선은 지금 정점보다 먼저 발견된 조상으로 갈 때만 쌓습니다. 같은 간선을 반대쪽에서 다시 볼 때 두 번 쌓지 않기 위해서입니다. 출력할 때 tuple(sorted(edge))로 간선의 두 끝을 정렬한 것은 AB와 BA를 같은 모양으로 보이려는 것일 뿐, 탐색 순서와는 상관이 없습니다. 마지막 예는 루트의 자식이 둘이라 루트가 단절점인 경우입니다.

빠른 방법을 만들었으면 느린 방법과 결과를 비교해 두는 것이 좋습니다. 정점이 1개에서 9개이고 간선이 무작위로 놓인 그래프 300개를 만들어, 이웃 목록의 순서까지 섞은 뒤 두 방법의 단절점을 비교하면 모두 같습니다.

왜 맞는가

루트가 아닌 정점 v를 생각합니다. v의 자식 w 가운데 low[w] >= discovery[v]인 것이 있다면, w의 서브트리에서 바깥으로 나가는 간선은 v로 가는 트리 간선과 v 이하로 가는 역방향 간선뿐입니다. 무방향 DFS에는 다른 가지로 가는 간선이 없기 때문입니다. 그래서 v를 지우면 w의 서브트리는 v의 조상들과 끊어지고, v는 단절점입니다. 반대로 모든 자식 w가 low[w] < discovery[v]라면, 모든 자식의 서브트리가 v를 거치지 않고 v의 조상에 닿을 수 있으므로 v를 지워도 모두 이어져 있고, v는 단절점이 아닙니다. 루트는 위쪽이 없으므로 자식 서브트리끼리 이어지는지가 문제인데, 서로 다른 서브트리 사이에는 간선이 없으므로 자식이 둘 이상일 때만 끊어집니다.

DFS는 각 정점을 한 번 발견하고 각 간선을 양쪽에서 한 번씩 보며, 간선 스택에 넣은 간선은 한 번만 꺼내므로 탐색이 끝나면 모든 간선이 어느 블록엔가 들어갑니다. 고립점은 간선이 없으므로 어느 블록에도 들어가지 않습니다.

비용

입력 확인은 이웃 목록을 한 번씩 훑지만, vertex not in graph.get(neighbor, [])가 리스트를 검색하므로 이웃이 아주 많은 정점에서는 느려질 수 있습니다. 큰 그래프에서는 이웃 목록을 집합으로 바꾸어 두고 확인하면 됩니다. DFS 자체는 정점과 간선을 한 번씩 처리하므로 O(V + E)이고, 발견 번호와 low 값과 간선 스택이 O(V + E)의 공간을 씁니다. 다만 이 코드는 재귀로 DFS를 하므로 깊이가 O(V)까지 커질 수 있고, 정점이 1000개 넘게 한 줄로 이어진 그래프에서는 재귀 깊이 한도에 걸립니다. 큰 그래프에서는 스택으로 만든 DFS처럼 반복문으로 바꾸어야 합니다.

정리

• 단절점은 지웠을 때 연결 성분의 개수가 늘어나는 정점이고, 이중 연결 성분은 단절점 없이 단단하게 이어진, 더 키울 수 없는 부분입니다. 다리는 간선 하나로 이루어진 블록입니다.
• 무방향 DFS에서 트리 간선이 아닌 간선은 모두 정점과 그 조상을 잇는 역방향 간선이므로, 서브트리가 바깥과 이어지는 길은 부모로 가는 간선과 조상으로 올라가는 역방향 간선뿐입니다.
• low[v]는 v의 서브트리에서 역방향 간선을 많아야 하나 타고 닿는 가장 작은 발견 번호이며, 돌아오면서 자식의 low와 역방향 간선으로 계산합니다.
• 루트가 아닌 v는 어떤 자식 w가 low[w] >= discovery[v]이면 단절점이고, 루트는 DFS 자식이 둘 이상일 때만 단절점입니다.
• 같은 판정에서 간선 스택을 트리 간선 (v, w)까지 꺼내면 블록이 하나씩 나오며, 전체 시간은 O(V + E)입니다.

연습 문제

1. 일직선 그래프의 단절점

간선이 A—B, B—C뿐인 그래프에서 단절점은 어느 정점인가요? A에서 DFS를 시작했을 때 판정 과정으로도 설명하세요.

2. 루트를 따로 판정하는 이유

삼각형 A, B, C에서 A를 루트로 DFS를 하면 A의 DFS 자식은 B 하나입니다. 이때 A에 루트가 아닌 정점의 판정을 그대로 쓰면 어떻게 될까요?

3. 사각형에 꼬리를 붙이면

사각형 A—B—C—D—A에는 단절점이 있나요? 여기에 간선 D—E를 더하면 단절점과 블록은 어떻게 바뀌나요?

다음 글 선택 심화: 세 파일 polyphase 병합의 분배와 역할 교대에서는 외부 정렬로 돌아가, 파일 세 개만으로 런을 번갈아 병합하는 방법을 다룹니다. 핵심 내용을 복습하려면 종합: 지도 요구에서 경로와 검사까지로 넘어가도 됩니다.