자료구조와 알고리즘 - 최소 신장트리(MST, Minimum Spanning Tree)와 크루스칼 알고리즘(Kruskal Algorithm)

 

 

---

 

1. 신장 트리와 최소 신장트리

 

1.1 신장 트리

그래프

 신장 트리는 위와 같은 무방향 그래프에서 모든 정점을 포함하면서, 사이클이 없는 연결된 부분 그래프를 말합니다.

 

즉, 신장 트리는 그래프의 모든 정점을 포함하며, 간선의 수는 정확히 V - 1개입니다(여기서 V는 정점의 수). 이는 트리가 가지는 기본적인 성질로, 사이클이 없으면서 모든 정점을 연결하는 구조를 의미합니다. 신장트리는 아래와 같이 여러개를 가질 수 있습니다.

 

신장트리

 

1.2 최소 신장 트리

 

최소 신장 트리는 신장 트리 중에서 간선의 가중치 합이 최소인 트리입니다. 예를 들어, 위의 경우 가중치 합이 11인 신장 트리가 최소 신장 트리입니다 (2+2+3+1+3=11). 이때 최소 신장 트리를 구하는 알고리즘 중의 하나가 크루스칼 알고리즘입니다.

 

 

2. 크루스칼 알고리즘

크루스칼 알고리즘(Kruskal's Algorithm)은 최소 신장 트리(MST, Minimum Spanning Tree)를 구하는 알고리즘 중 하나입니다. 그래프 내 모든 정점을 연결하면서 간선의 가중치 합이 최소가 되는 트리를 찾는 것이 목표입니다. 크루스칼 알고리즘은 그리디(탐욕적) 방식을 사용하여 매번 가중치가 가장 작은 간선을 선택합니다.

 

2.1 알고리즘 동작 과정

1. 간선 정렬: 그래프의 모든 간선을 가중치의 오름차순으로 정렬합니다.
2. 간선 선택: 가중치가 작은 간선부터 하나씩 선택하면서, 현재 간선이 선택되었을 때 사이클이 생기지 않으면 해당 간선을 신장 트리에 추가합니다.
   • 사이클이 생기는지 확인하기 위해 유니온-파인드(Union-Find) 알고리즘을 사용합니다.
3. 종료 조건: 간선의 수가 V - 1개(여기서 V는 정점의 수)가 될 때까지 위의 과정을 반복합니다. 이때 최소 신장 트리가 완성됩니다.

 

-코드

def initialize(n):
    parent = [i for i in range(n)]
    rank = [0] * n
    return parent, rank

def find(x, parent):
    if x != parent[x]:
        parent[x] = find(parent[x], parent)
    return parent[x]
    
def union(x, y, parent, rank):
    xroot = find(x, parent)
    yroot = find(y, parent)

    if xroot == yroot:
        return

    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1


#A:0, B:1, C:2, D:3, E:4, F:5
g = [
[0,6,2,2,0,0],
[6,0,0,0,0,3],
[2,0,0,0,2,0],
[2,0,0,0,1,1],
[0,0,2,1,0,0],
[0,3,0,1,0,0]
]

n = 6
parent, rank = initialize(n)
seen = [[0]*n for _ in range(n)]
arr = []
for i in range(n):
    for j in range(n):
        if g[i][j] and not seen[i][j] and not seen[j][i]:
            arr.append((i, j, g[i][j]))
            seen[i][j] = 1
            seen[j][i] = 1

arr.sort(key=lambda x: -x[2])
edge = 0
result = []
while edge < n-1:
    i, j, num = arr.pop()
    
    # 싸이클 여부 확인
    root_i = find(i, parent)
    root_j = find(j, parent)
    if root_i == root_j:
        continue
    
    union(i, j, parent, rank)
    result.append((i, j, num))
    edge += 1
    
print(result)
#결과(정점1, 점정2, 가중치)
#[(3, 5, 1), (3, 4, 1), (2, 4, 2), (0, 3, 2), (1, 5, 3)]

 

2.2 크루스칼 알고리즘의 특징

 

1. 간선 중심: 정점이 아닌 간선을 기준으로 최소 신장 트리를 구성합니다.

 

2. 사이클 확인: 선택한 간선의 양 끝 정점이 이미 연결되어 있는지를 확인하여 사이클을 방지합니다. 이를 위해 유니온-파인드(Union-Find) 자료구조를 사용합니다.

 

3. 시간 복잡도

• 크루스칼 알고리즘의 시간 복잡도는 O(E log E)로 표현됩니다. 이는 두 가지 주요 요소로 구성됩니다:
  1. 간선 정렬:
     • 그래프의 모든 간선을 가중치의 오름차순으로 정렬하는 데 O(E log E) 시간이 소요됩니다. 여기서 E는 간선의 수입니다.
  2. 유니온-파인드 연산:
     • 사이클을 확인하고 집합을 관리하기 위해 사용되는 유니온-파인드 자료구조는 최적화된 방식(경로 압축 및 유니온 by 랭크)을 사용하여 Find와 Union 연산을 거의 상수 시간인 O(α(N))에 수행할 수 있습니다. 따라서 유니온-파인드 연산 자체는 전체 시간 복잡도에 큰 영향을 미치지 않습니다.
  결과적으로 크루스칼 알고리즘의 전체 시간 복잡도는 주로 간선 정렬에 의한 O(E log E)입니다.

4. 장점

• 희소 그래프에서 효율적: 간선 수가 적은 경우에 빠르게 동작합니다.
• 간선 정보가 미리 주어진 경우 유리: 간선이 미리 제공되어 있는 상황에서 효과적으로 사용할 수 있습니다.

5. 단점

• 간선이 많은 경우 비효율적: 간선 수가 많을 때 간선 정렬에 소요되는 시간이 많아질 수 있습니다.