알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm)

알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm)

jina-developer.tistory.com/114

 

자료구조 - 최소 신장 트리 (MST, Minimum Spanning Tree)

1. 크루스칼 알고리즘(Kruskal's Algorithm)

1) 순서

1. 모든 간선들의 가중치를 오름차 순으로 정렬
2. 가중치가 가장 작은 간선을 선택
3. 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
4. 이 과정을 반복

2) 시간복잡도

O(eloge)

 

 

2. 프림 알고리즘 (Prim's Algorithm)

1) 순서

1. 임의의 간선을 선택
2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택
3. 모든 정점이 선택될 때까지 반복

2) 시간복잡도

O(n^2)