TIL : Kruskal(크루스칼) 알고리즘 (9)

💻 알고리즘

 📌 크루스칼 알고리즘

프림 알고리즘과 같이 대표적인 최소 신장 트리(MST)를 찾는 알고리즘이다.

이 알고리즘의 특징과 동작 원리는 다음과 같다.

 

✔️ 특징

• 확인하는 그래프가 무방향 그래프이고 가중치가 존재한다.
• 가장 비용이 작은 것부터 확인하기 때문에 그리디 알고리즘의 일종이다.
• 순환(Cycle)이 있는지 확인하기 위해서 Union-Find 알고리즘을 사용한다.

✔️ 동작 원리

• 입력받은 간선들을 cost을 기준으로 정렬한다.
• 가장 작은 비용을 가진 간선을 확인한다.
• 사이클이 안 만들어지면 추가하고 만들어지면 다음 간선을 확인한다.
• 간선의 개수가 정점 - 1 개가 될 때까지 반복한다.

# find function
def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]
    
# union function
def union(x,y):
    x = find(x)
    y = find(y)
    parent[y] = x
    
# kruskal algorithm
def kruskal(vertex, edges):
    MST = []
  	
    while True:
        if len(MST) == vertex - 1:
            break
        edge = edges.pop(0) # startNode, endNode, cost
        if find(edge[0]) != find(edge[1]):
            union(edge[0], edge[1])
            MST.append((edge[0], edge[1]))
            
    return MST