그래프 (3) - 서로소 집합(Union-find), 사이클 판정, MST

서로소 집합

서로소 집합(Disjoint set)은 Union-find 알고리즘으로도 많이 불리는데, 서로 겹치는 원소가 없으면서 전체 원소를 포괄하는 집합들의 처리와 관련된 알고리즘이다. 즉 서로소 집합에서 모든 원소는 각각 정확히 1개의 집합에 속하게 된다. 서로소 집합이 지원하는 연산은 2가지이다.

​

$find(x)$: 원소 x가 속한 집합을 출력한다.

$union(a, b)$: 원소 a가 속한 집합과, b가 속한 집합을 합친다.

​

두 연산을 구현하기에 최적화된 자료구조는 트리이다. 트리를 이용하면 루트 노드를 집합명으로 사용하여 다음과 같이 이해할 수 있다.

​

$find(x)$: x가 속한 트리의 루트 노드를 출력한다.

$union(a, b)$: a와 b가 속한 트리의 루트 노드를 각각 구하여, 둘 중 하나를 다른 하나의 부모 노드로 삼는다.

​

각 노드의 parent를 담는 배열을 만들어서, 아래와 같이 간단히 구현 가능하다.

parent = [i for i in range(N+1)]
def find(x):
    if parent[x] == x: return x
    return find(parent[x])

def union(a, b):
    ra = find(a)
    rb = find(b)
    if ra == rb: return False

    parent[ra] = rb
    return True

 

 

서로소 집합의 최적화

위의 코드에서, $union(1,2), union(1,3), \cdots , union(1,n)$과 같은 연산이 주어져 skewed tree가 되는 경우를 생각해 보자. 이때 $find(1)$을 실행하면 루트 노드까지 돌아가는 데 $O(n)$이 소요되므로 좋지 않다. 따라서 트리가 편향되지 않도록 최적화할 필요가 있다.

​

최적화의 방법은 크게 두 가지이다.

1. path compression: find 시 루트 노드를 찾고, 찾은 루트 노드를 노드의 parent로 설정해 준다. 따라서 한번 find 호출 시 거쳐간 노드들은 모두 루트 노드에 바로 연결되게 한다.
2. union-by-rank: union 시 트리가 편향되는 것을 방지하기 위해, 트리의 높이(rank)를 별도 배열로 저장해 두고 rank가 더 큰 트리를 작은 트리 쪽으로 합친다. rank의 계산은 union 시 두 트리의 rank가 똑같았다면 합친 트리의 rank를 +1 하는 것으로 간단하게 할 수 있다. 추가로 트리의 원소 개수를 기준으로 판단하는 union-by-size도 있다. (이것은 '작은 집합에서 큰 집합으로 합치는 테크닉(smaller to larger)'의 기초 예시로도 볼 수 있다)

​

최적화를 적용해서 다시 알고리즘을 짜보자.

parent = [i for i in range(N+1)]
rank = [0]*(N+1)
def find(x):
    if parent[x] == x: return x
    parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    ra = find(a)
    rb = find(b)
    if ra == rb: return False

    if rank[ra] > rank[rb]: parent[rb] = ra
    else:
        parent[ra] = rb
        if rank[ra] == rank[rb]: rank[rb] += 1
    return True

 

최적화를 적용한 Disjoint set의 시간복잡도는 역아커만 함수로 나타나는데, 사실상 $O(1)$으로 봐도 무방하다.

 

 

사이클 판정

1. 무방향 그래프의 사이클 판정

앞서 설명한 disjoint set을 사이클 판정에 이용할 수 있다. 간선이 연결하는 두 정점을 union하게 되면, 연결된 정점끼리는 모두 같은 루트 노드 값을 갖게 된다. 이때 아직 살펴보지 않은 새로운 간선을 갖고 union하려는데 이미 두 정점의 루트 노드가 같다면 사이클이 발생한 것으로 볼 수 있다. 즉 위 코드에서 union함수의 반환값이 False인 경우 사이클이 발생했다고 판정 가능하다.

다른 방법으로, DFS하여 직전의 부모 노드가 아니면서 방문했던 노드를 재방문한 경우를 체크하여 판정할 수도 있다.

 

2. 방향 그래프의 사이클 판정

방향 그래프의 사이클 판정 역시 두 가지 방법이 잘 알려져 있다.

첫 번째 방법은 별도의 스택이나 visited 배열을 활용해 DFS의 종료 여부를 관리하고, 이미 방문하였으나 DFS가 종료되지는 않은 노드를 재방문하게 되면 이를 backward edge라 보고 사이클이라고 판정한다. 이 아이디어는 SCC, low-link value 등 후속 개념에서도 다시 등장하므로 기억해 두면 좋다.

다른 방법으로는 방향 그래프의 경우 DAG만이 위상 정렬이 가능함을 이용해, Kahn's Algorithm으로 위상 정렬하면서 처리한 노드 수가 전체 노드 수와 다르면 사이클이 있다고 파악할 수도 있다.

 

아래는 DFS의 종료 여부를 바탕으로 방향 그래프의 사이클을 판정하는 코드이다.

# 0: 방문X, 1: 방문했으나 종료X, 2: 종료
visited = [0]*(N+1)
def dfs(u):
    visited[u] = 1
    for v in adj[u]:
        if visited[v] == 1:
            visited[u] = 2
            return True
        if visited[v] == 0:
            if dfs(v): return True
    visited[u] = 2
    return False

for u in range(1, N+1):
    if visited[u] == 0: dfs(u)

 

사이클을 구성하는 노드를 구해야 하는 경우가 있다. 사이클이 얽혀 있지 않음이 보장되는 경우(모든 정점에서 out_degree=1인 경우 등), 방문한 순서대로 스택에 넣거나 id를 매겨 주는 식으로 구할 수 있다. 그러나 일반적인 그래프에서는 사이클이 얽혀 있을 수 있으므로, SCC를 직접 구해야 한다.

 

 

MST

최소 신장 트리(Minimum Spanning Tree) 알고리즘에 대해 알아보자. 신장 트리(스패닝 트리)란 그래프의 모든 노드를 최소의 간선으로 연결하는 부분 그래프이다. $N$개의 노드를 연결하기 위해 필요한 $N-1$개의 간선만을 남겨 놓으며, 사이클은 존재하지 않아야 한다. MST는 여러 신장 트리 중 가중치의 합이 최소가 되는 그래프이다.

​

MST를 구하기 위해 고전적으로 2가지의 방법이 있다.

 

1. Kruskal's Algorithm

Greedy한 접근 방법으로 간선에 초점을 맞춘다. 간선들을 모두 힙에 넣어 놓고, 가중치가 최소인 간선부터 하나씩 pop하면서 두 정점을 union한다. 이때 사이클이 검출되면, 해당 간선은 MST에 포함될 수 없으므로 넘어간다. 총 $N-1$개의 간선을 포함하게 되면 종료한다.

edge = []
for _ in range(E):
    a, b, c = map(int, input().split())
    heapq.heappush(edge, (c, a, b))

def kruskal(edge):
    weight = 0
    e = 0
    while e < V-1:
        w, u, v = heapq.heappop(edge)
        if union(u, v):
            e += 1
            weight += w
    return weight

print(kruskal(edge))

 

2. Prim's Algorithm

이것도 그리디인데 정점을 이동하면서 탐색한다. 아무 정점에서 시작해 해당 정점의 간선들을 힙에 넣는다. 가중치가 최소인 간선부터 pop한다. 해당 간선과 연결된 정점을 아직 방문하지 않았다면, 방문 처리하고 새로 방문한 정점의 간선들을 힙에 넣는다. 힙이 빌 때까지 반복한다.

여담으로 다음에 다룰 다익스트라와 매우 유사한 알고리즘이다. 평가 함수를 단일 가중치에서 경로의 가중치 합으로 바꾸면 다익스트라가 된다.

def prim():
    weight = 0
    visited = set([1])
    q = []
    for w, v in graph[1]:
        heapq.heappush(q, (w, v))

    while q:
        w, u = heapq.heappop(queue)
        if u in visited: continue
        visited.add(u)
        weight += w
        for w_v, v in adj[u]:
            if v not in visited:
                heapq.heappush(q, (w_v, v))
    return weight

 

크루스칼 알고리즘은 $O(E\log E)$의 시간복잡도를 갖고, 프림 알고리즘은 우선순위 큐(힙)를 이용해 구현할 경우 $O((V+E)\log V)=O(E\log V)$의 시간복잡도를 갖는다.