[TIL] 최소 신장 트리(MST) 1 - 크루스칼(kruskal) 알고리즘

최소 신장 트리(MST : Minimum Spanning Tree)

• 가능한 신장 트리 중에서 간선의 가중치 합이 최소인 신장 트리
• 최소 신장 트리를 찾을 수 있는 알고리즘은 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있음.
• 두 알고리즘 모두 탐욕 알고리즘을 기반으로 한다.

신장 트리란?
- 그래프의 모든 노드를 포함하면서 모든 노드가 서로 연결 되어 있고 트리의 속성을 만족시키는 트리 (사이클 x)

 

 

크루스칼 알고리즘(Kruskal's algorithm)

• 모든 정점을 독립적인 집합으로 만든다.
• 모든 간선을 가중치를 기준으로 정렬하고, 가중치가 가장 작은 간선부터 양 끝의 두 정점을 비교한다.
• 두 정점의 최상위 정점(루트 노드)을 확인하고 서로 다르다면 연결한다. (같을 경우 사이클이 생기므로 x)
• Union-Find 알고리즘 사용

          - union의 순서에 따라 최악의 경우 연결 리스트가 될 수 있으며 시간복잡도 O(N)이므로 

            union-by-rank, path compression 기법을 같이 사용한다.

Union-Find란?
- 그래프 알고리즘의 하나로 상호 배타적 집합(Disjoint Set)을 표현할 때 사용하는 알고리즘
- 노드들 중 연결된 노드를 찾거나(Find) 노드들을 서로 연결할 때(Union) 사용

Disjoint Set?
- 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
- 공통 원소가 없는 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조 (서로소)

 

 

크루스칼 알고리즘 구현

 1. 그래프 구현

graph = {
    'vt' : ['A', 'B', 'C', 'D', 'E'],
    'eg' : [
    	(3, 'A', 'B'),
        (7, 'A', 'C'),
        (5, 'A', 'D'),
        (3, 'B', 'A'),
        (8, 'B', 'C'),
        (6, 'B', 'E'),
        (7, 'C', 'A'),
        (8, 'C', 'B'),
        (3, 'C', 'D'),
        (5, 'D', 'A'),
        (3, 'D', 'C'),
        (9, 'D', 'E'),
        (6, 'E', 'B'),
        (6, 'E', 'C'),
        (9, 'E', 'D'),
    ]
}

 

2. kruskal main 함수 구현

def kruskal(graph):
    mst = list()
    
    for node in graph['vt']:
    	make_set(node)		# 각 정점을 독립적인 집합으로 초기화
        
    edges = graph['ed']
    edges.sort()			# 간선을 가중치 기준으로 정렬

    
    for edge in edges:
    	w, v, u = edge
        
        if find(v) != find(u):		# 두 정점의 부모 노드가 다르다면 합치고 mst에 추가
            union(v,u)
            mst.append(edge)
	return mst
    
    
# union-find 함수 필요
# make-set 함수 필요

 

3. union-find 함수 구현

parent = dict()		# path compression을 사용하기 위한 딕셔너리
rank= dict()		# union-by-rank를 사용하기 위한 딕셔너리

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

def union(v,u):
    root1 = find(v)
    root2 = find(u)

    if rank[root1] > rank[root2]:
    	parent[root2] = root1
	else:
		parent[root1] = root2
        if rank[root1] == rank[root2]:
        	rank[root2] +=1

 

4. make-set 함수 구현

def make_set(node):
    parent[node] = node
    rank[node] = 0

 

5. 실행 결과

kruskal(graph)

#[(3, 'A', 'B'), (3, 'C', 'D'), (5, 'A', 'D'), (6, 'B', 'E')]

 

 

크루스칼 알고리즘의 시간복잡도?
- O(E log E)