이 4가지 알고리즘이 자꾸만 헷갈려서 심플하게 정리해 둔다.
- Prim과 Kruskal : MST (Minimumm Spanning Tree) 를 만드는 알고리즘
Prim 은 시작 정점부터 시작해서 가까이에 있는 정점으로 가는 패스 중 가장 최소값을 찾아서 연결해 나가는 방식이다. Greedy 적인 요소가 다분하다. 또한 Shortest Path를 찾는 알고리즘인 Dijkstra와 아주아주아주아주 유사하다.
반면 Kruskal은 Heap과 Union-Find 자료구조를 이용해서 MST를 만드는데 전체에서 가장 작은 Path들을 찾아서 서로서로 연결시켜 나가면서 MST를 만든다. Kruskal도 Greedy 적이다.
- Shortest Path 를 찾는 알고리즘 : Dijkstra 와 Floyd
Dijkstra는 시작점에서 가장 가까운 정점들 중 가장 최소값을 가진 Path를 따라간다. Prim과 매우 유사하다.
Floyd는 DP(Dynamic Programming) 방식으로 전체를 모두 스캔해 가면서 개선한다... 코드가 아주 짧은 것이 특징!
정리 종료!!
