Kruskal 알고리즘 (Greedy)

Shortest Path 를 찾는 알고리즘으로 Prim 알고리즘을 살펴보았다. prim 은 그리디 알고리즘으로, MST(최소 신장 트리)를 만들기 위해 힙, 즉 우선순위큐를 사용했다. 두 정점 사이의 edge 거리가 작은 것 우선순위가 높도록 정했다. 이번 포스팅에서 다룰 Kruskal 알고리즘도 Shortest path를 찾는 문제다. 연결 그래프가 주어지고 MST를 구하면 되는 문제이다. Prim 알고리즘과 목적이 같지만, 구현 방법에 약간의 차이가 있다. Prim 알고리즘 포스팅: https://matt1235.tistory.com/51 문제) 다음과 같은 연결그래프가 있다. 모든 정점을 연결하는 Minimum Spanning Tree를 구하라. Prim 알고리즘은 T라는 해집합을 점차 늘려나가는 ..

2022.09.24