빽 투더 기본기 [알고&자구 6편]. 크루스칼 알고리즘

그래프에서 최소 신장 트리를 만드는 알고리즘 중, 가장 유명한 크루스칼(Kruskal) 알고리즘을 잠깐 정리해볼까 한다.

글 대부분의 내용은 heejeong Kwon님의 블로그 와 나동빈님의 유튜브를 참고하였다.

 

그래프에서 최소 신장 트리 만들기

크루스칼 알고리즘은, 어떤 그래프가 주어져있을 때, 이 그래프에서 최소 신장 트리 (Minimum Spanning Tree) 를 만드는 알고리즘이다.

최소 신장 트리란, 어떤 그래프에서 각 정점간 간선을 1개씩만 선택하여, 결과적으로 모든 정점을 잇는 하나의 그래프(트리) 를 말한다. 정점이 n개 있다고 할 때, 간선은 n-1개가 된다.

그럼 이걸 왜하느냐? 대표적인 예로, 여러 도시가 있고, 각 도시간 도로를 깔 수 있는 경로와 비용이 이미 파악되어있다고 하자. 우리는 이를 그래프 상황으로 생각할 수 있는데, 이 때 모든 도시를 잇는 도로를 깐다고 생각해보자. 도로를 까는 건 돈이 드는 비용이므로, 우리는 최소비용으로 도로를 깔고싶을 것이다. 이와 같은 상황이, 최소 비용으로 모든 도로를 잇는 문제, 즉 최소 신장 트리문제와 동일하다는 것이다.

크루스칼 알고리즘을 위해서는, 역시 먼저 그래프가 주어져야 한다. 그리고 이 그래프에서, 우리는 각 간선에 대한 정보가 입력으로 주어져야 한다.

 

Union - Find

본격 알고리즘에 들어가기 전에, Union, Find 에 대해서 먼저 알아야 하는데, 이는 특정 알고리즘이라기 보다는 구현상의 아이디어라고 볼 수 있겠다.

우리는 새로운 그래프 (최소 신장 트리) 를 만든다고 했다. 초기에, 우리는 모든 정점은 존재하되, 어떤 정점도 연결되지 않은 상태를 생각한다. 즉, 그냥 말그대로 그래프의 정점만 존재하는 상태라고 생각하면 된다. 즉 각 노드는 각각의 그래프라고 생각할 수 있다.

크루스칼 알고리즘은, 여기에 간선을 하나씩 더해나가는 알고리즘이다. 이 때 더한다는 말은 Union 이라는 말과 같다. 두 정점사이에 간선을 둔다는 말은, 두 그래프 사이에 간선을 둔다는 말, 즉 두 그래프를 합치는(Union) 이라는 뜻이다.
그러나 무작정 간선을 둘 수 있는건 아니다. 두 정점 사이에 간선을 둘 때, 두 정점을 이음으로써 합쳐지는 그래프가 싸이클이 생기는지 확인(Find)해야 한다. 싸이클이 생기면, 최소신장트리가 아니므로, 싸이클이 생기지 않는 경우에만 간선을 두어야 한다.

이러한 아이디어를 구현하기 위해, 우리는 어떤 배열(parents)을 하나 둔다. 이 배열의 인덱스는 각 정점의 번호 혹은 인덱스를 나타내고, 해당 인덱스의 배열 값은 이 정점의 부모 정점을 나타낸다.
예를 들어, 다음의 경우.

정점	1	2	3	4	5
parent[i]	1	1	1	4	5

1, 2, 3번 정점은 1번을 부모 노드로 하는, 하나의 그래프(트리) 를 이루고 있고, 4, 5번은 각각 자기 자신이 부모 노드인 그래프를 이루고 있음을 알 수 있다. 즉 parents 라는 배열 하나로, 현재 그래프의 상황을 알 수 있다.

이에 union 과 find 는 다음과 같이 구현할 수 있다.

def find(v, parents):
    if parents[v] == v:
        return v
    else:
        return find(parents[v], parents)

def union(v1, v2, parents):
    p1, p2 = find(v1, parents), find(v2, parents)
    if p1 < p2:
        parents[v2] = p1
    else:
        parents[v1] = p2

union 에서 두 그래프를 합칠 때, 합쳐진 노드의 부모 노드는 두 그래프의 부모 노드에서 순번이 더 적은쪽의 값으로 채워진다.

 

크루스칼 (Kruskal) 알고리즘

알고리즘

알고리즘을 간단하게 정리하면 다음과 같다.

1. 각 간선을 담는 배열을 만든다. 간선은 (비용, 간선을 잇는 정점1, 정점2) 을 담는다.
2. 간선 배열을 오름차순 정렬한다. 즉, 비용이 낮은 순으로 앞으로 온다.
3. 각 간선을 하나씩 탐색하며, 이 간선을 새로운 그래프에 추가할 때, 사이클이 생기는지 확인한다. (find)
4. 사이클이 안생기면 새로운 그래프에 추가한다. (union)
5. 완성된 새로운 그래프가 최소 신장 트리가 된다.

이해가 안되면… 위에 링크한 나동빈님의 유튜브를 보면 8분만에 이해할 수 있다.

아무튼 이 알고리즘을 한마디로 표현하면,

크루스칼 알고리즘은 간선을 작은 순으로 하나씩 탐색하며, 사이클이 생기지 않을 시, 최소 신장트리에 추가하는, 일종의 그리디 알고리즘이다.

 

코드

먼저 그래프가 주어져야 한다고 했다.
아래와 같은 그래프 상황이고, 정점과 인접행렬이 주어졌다고 하자.

출처 : 허민석님 유튜브

v = list("ABCDEF")
adjacent = {
    "A": {
        "B": 3,
        "C": 2,
        "D": 4,
    },
    "B": {
        "A": 3,
        "D": 2,
        "F": 5
    },
    "C": {
        "A": 2,
        "E": 1
    },
    "D": {
        "A": 4,
        "B": 2,
        "E": 1,
        "F": 3
    },
    "E": {
        "C": 1,
        "D": 1,
        "F": 2,
    },
    "F": {
        "B": 5,
        "D": 3,
        "E": 2
    }
}

우리는, 그래프에서 간선에 대한 정보가 입력으로 주어져야 한다고 했으니, 위 인접 행렬의 정보를 가지고, 간선에 대한 정보를 edges 라는 변수에 담아보자.

# 그래프의 간선 정보를 담는 배열을 만든다.
edges = [(weight, (v1, v2)) for v1, adj in adjacent.items() for v2, weight in adj.items()]
print(edges)

# output
[(3, ('A', 'B')),
 (2, ('A', 'C')),
 (4, ('A', 'D')),
 (3, ('B', 'A')),
 (2, ('B', 'D')),
 (5, ('B', 'F')),
 (2, ('C', 'A')),
 (1, ('C', 'E')),
 (4, ('D', 'A')),
 (2, ('D', 'B')),
 (1, ('D', 'E')),
 (3, ('D', 'F')),
 (1, ('E', 'C')),
 (1, ('E', 'D')),
 (2, ('E', 'F')),
 (5, ('F', 'B')),
 (3, ('F', 'D')),
 (2, ('F', 'E'))]

이제 위 알고리즘 대로 코딩을 하면,

min_cost = 0
min_edges = []

# 간선 배열을 오름차순으로 정렬한다.
edges = sorted(edges)
for edge in edges:
    weight, (v1, v2) = edge

    # 사이클을 만드는지 확인하고,
    if find(v1, parents) != find(v2, parents):

        # 사이클이 안생기면, 새로운 그래프에 추가한다.
        union(v1, v2, parents)
        min_cost += weight
        min_edges.append(edge)

이를 출력하면 다음과 같이 최소 비용과 최소 신장 트리에 대한 정보를 알 수 있다.

print(min_cost)
print(min_edges)

# output
8
[(1, ('C', 'E')),
 (1, ('D', 'E')),
 (2, ('A', 'C')),
 (2, ('B', 'D')),
 (2, ('E', 'F'))]

크루스칼 알고리즘의 시간복잡도를 생각하면,

1. 정렬하는데 시간 O(e log e)
2. 간선을 탐색하는 시간 O(e)
3. 탐색하는 와중에, union-find 시간 O(log V). 왜냐하면 트리구조로 그래프를 만들기 때문.

따라서, 결과적으로 시간복잡도는 O(e log e) 라고 생각할 수 있다.