크루스칼 알고리즘(Kruskal Algorithm)

 크루스칼 알고리즘에 대해 이해하기 위해서는 먼저 신장 트리(Spanning Tree)에 대해 이해할 필요가 있습니다.

---

신장 트리(Spanning Tree)

신장 트리는 하나의 그래프가 있을 때 모든 노드를 포함하는 부분 그래프를 의미합니다.

출처: 위키피디아

 위의 그림이 직관적으로 신장 트리를 이해하는 데 도움이 되는 것 같습니다. 실제 그래프 관계는 훨씬 복잡하지만, 굵은 실선만 이어도 모든 노드에 대해서 연결할 수 있다는 것이 특징입니다.

 

---

크루스칼 알고리즘(Kruskal Algorithm)

 

 크루스칼 알고리즘은 가능한 최소 비용의 신장 트리를 찾아주는 알고리즘입니다. 다음과 같은 순서로 처리됩니다.

---

1. 모든 간선에 대해 비용순으로 정렬을 수행합니다.

2. 거리가 짧은 간선부터 집합에 포함시킵니다.

3. 단, 사이클이 발생하는 간선은 포함하지 않습니다.

---

 크루스칼 알고리즘의 시간 복잡도는 O(ElogE)입니다. 이는 파이썬 기본 정렬 라이브러리의 시간 복잡도와 같은데, 과정 1단계의 정렬으로 인한 시간 소요가 가장 영향을 많이 미친다는 의미입니다. 코드는 다음과 같이 작성할 수 있습니다.

input1 = '''7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25'''

def solution(input1):
    def find_parent(parent, x):
        if parent[x] != x:
            parent[x] = find_parent(parent, parent[x])
        return parent[x]

    def union_parent(parent, a, b):
        a = find_parent(parent, a)
        b = find_parent(parent, b)
        if a < b:
            parent[b] = a
        else:
            parent[a] = b

    v, e = list(map(int, input1.split('\n')[0].split()))
    array = [tuple(map(int, row.split())) for row in input1.split('\n')[1:]]
    parent = [0] * (v + 1)

    edges = []
    result = 0

    for i in range(v + 1):
        parent[i] = i

    for i in range(e):
        a, b, cost = array[i]
        edges.append((cost, a, b))
    
    # 간선을 비용 기준 오름차순 정렬
    edges.sort()
    # 간선을 신장 트리에 추가
    for edge in edges:
        cost, a, b = edge
        # 단, 사이클이 발생하지 않는 경우 
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            result += cost
            
    print(result)
    
solution(input1)

 

 이전에 보았던 서로소 집합을 이용한 무향 그래프의 사이클 판별 코드와 매우 유사한 것을 알 수 있습니다. 편의상 링크를 걸어두겠습니다.

 

링크: https://jcy1996.tistory.com/34?category=960192 

서로소 집합 알고리즘

 

 즉 이전과 유사하게 진행하되, 최소 신장 트리는 사이클이 발생하면 안되므로 사이클이 발생하지 않는 노드에 대해서만 고려하는 겁니다. 가장 비용이 낮은 간선부터 그리디하게 추가해나가면 최소 비용의 신장 트리를 구성할 수 있으며, 위의 코드에서 result 변수가 최소의 비용을 의미합니다.