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

 

 

Kruskal Algorithm

• 네트워크(간선에 가중치가 부여된 그래프)의 모든 edge를 최소 비용으로 연결하는 방법을 Greedy하게 찾는 알고리즘.
• MST(최소 비용 신장 트리)의 특성을 이용하여 각 단계에서 MST를 구성해나감.
  • 신장 트리 : 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
  • 최소 신장 트리 : 간선 비용이 최소가 되는 신장트리

 

 

 

동작 방법

1. 간선을 비용을 기준으로 오름차순으로 정렬
2. 모든 간선을 순서대로 하나씩 추가 (사이클을 만드는 간선은 포함하지 않음)

 

 

 

union-find 알고리즘을 활용한 사이클 판별

• 서로소 집합은 무방향 그래프 내의 사이클 존재 여부 판별에 이용됨 (유방향 그래프는 dfs를 활용해 판별)

1. 모든 간선 정보에 대해 find 연산으로 각 노드의 부모를 찾는다
2. 부모 노드가 같다면 사이클이 존재
3. 같지 않다면 union 연산

 

 

 

파이썬으로 구현

# find
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

# union
def union(parent, a, b):
    def union(parent, a, b):
        a, b = find(parent, a), find(parent, b)
        if a > b:
            parent[a] = b
        else:
            parent[b] = a


# kruskal
edges = [[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]]
v, e = 4, len(edges)

parent = [i for i in range(v + 1)]
edges.sort(key=lambda x : x[2])


for i in range(e):
    a, b, cost = edges[i]
    if find(parent, a) != find(parent, b):
        union(parent, a, b)

 

 

 

 

참조
 - heejeong Kwon 님의 블로그 - 1
 - heejeong Kwon 님의 블로그 - 2
 - YounghunJo 님의 블로그 - 1
 - YounghunJo 님의 블로그 - 2