Algorithm. 그래프 - 크루스칼 알고리즘

1. 크루스칼 알고리즘

• 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘
  • 정점이 n개인 그래프에서 n-1개의 간선을 선택하는 방식

• 초기 상태는 n개의 정점들이 하나의 트리가 된다.
  
  • 하나의 정점을 포함하는 n개의 상호 배타 집합이 존재
  • 간선을 선택하면 간선의 두 정점이 속한 트리가 연결되고 하나의 집합으로 합쳐진다.
• 사이클이 생기면 안된다.
  • 두 정점이 같은 집합의 원소인지 검사해야한다.
• 동작과정
  1. 최초, 모든 간선을 가중치에 따라 오름차순 정렬
  2. 최소 가중치 간선부터 선택하면서 트리 증가
     • 사이클이 존재하면 다음 가중치 낮은 간선 선택
  3. n-1개의 간선이 선택될 때 까지 (2) 반복

소스코드

# G : 그래프

def mst_kruskal(G):
    mst = [] # 선택된 간선 집합, 공집합으로 초기화
    
    for i in range(N):
    	Make_Set(i) # 각 정점을 집합으로 생성
    
    G.sort(key=lambda t : t[2]) # 가중치 기준으로 정렬
    mst_cost = 0 # MST 가중치
    
    while len(mst) < N-1:
    	u, v, val = G.pop(0) # 최소 가중치 간선 가져오기
        if Find_Set(u) != Find_Set(v): # 두 정점이 같은 집합이 아닐 경우
            Union(u, v) # 연결
            mst.append((u, v)) # 트리에 (u, v) 간선 추가
            mst_cost += val

 

---

크루스칼 알고리즘은 간선 선택 과정에서 생성되는 트리를 관리하기 위해 상호 배타 집합을 사용한다.

---

• 트리에 속한 정점들은 자신을 루트로 하는 서브트리의 높이를 rank라는 이름으로 저장
• 선택한 간선으로 두 개의 트리가 한개의 트리로 합친다.
• 이때, 각 트리에 해당하는 상호 배타 집합을 union 연산으로 합친다.
• rank값이 작은 트리를 rank값이 큰 트리의 서브트리로 포함시킬 때는 트리의 정점들의 rank값 수정 불필요