(그리디) 크루스칼 알고리즘

1. 최소 신장을 찾는 크루스칼 알고리즘

신장트리란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 즉, 모든 노드들 간에 서로 연결은 되어 있되 사이클이 존재하지 않는 "부분"그래프를 의미한다. 예를 들어 다음과 같은 그래프G가 있을 때, 이때 그래프에서 가능한 신장 트리는 다음과 같다.

즉, A, B, C 노드들 간에 서로 연결은 되어 있되, 자기 자신으로 돌아오는 산선이 있는 사이클이 존재해서는 안된다. 이럴때 우리는 신장 트리라 한다. 신장 트리들은 원본 그래프 G의 '부분' 그래프임을 잊지 말자.

2. 왜 최소 신장을 찾을때 크루스칼 알고리즘을 사용할까?

아래와 같이 있다고 가정해 보자

위 그림을 보면 원본 그래프에서 나올 수 있는 신장 트리는 2가지 이다. 파란색, 빨간색 점으로 이루어진 그래프이다.

이 때 추가적으로 주어져 있는 정보가 있는데 그것은 노드들간의 간선(edge)의 비용이 있어야 한다.  여기서 원본 그래프에서 신장트리를 만들 수 있는 수 중주에 최소 간선 비용을 들여서 만들 수 있는 신장트리를 최소 신장이라고 한다. 그리고 이것을 효율적으로 찾을 수 있는 것이 크루스칼 알고리즘이다.

3. 크루스칼 알고리즘의 동작 과정

1.  주어진 모든 간선 정보에 대해 간선 비용이 낮은 순서(오름차순)으로 정렬을 수행
2. 정렬된 간선 정보를 하나씩 확인하면서 현재의 간선이 노드들 간의 사이클을 발생시키는지 확인
3. 만약 사이클이 발생하지 않는 경우, 최소 신장 트리에 포함 시키고 사이클이 발생하는 경우, 최소 신장 트리에 포함시키지 않음
4. 1번~3번의 과정을 모든 간선 정보에 대해 반복 수행

크루스칼 알고리즘은 서로소 집합 알고리즘을 사용하여 구현하므로 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하면서 사이클을 판변할 수 있다.

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

edges = [[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]]
v,e = 7,9

parent = list(range(v+1))
result = 0
edges.sort(key =lambda x:x[2])

for e in edges:
    a,b,cost = e
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost

print(result) # 159