다익스트라 vs 크루스칼 비교 (java)

	다익스트라	크루스칼
구현 방법	우선순위 큐 + dist(점화식)	우선순위 큐 + Union-Find
중심	정점 중심	간선 중심
시작점	출발점이 정해져 있는 경우	간선의 가중치가 가장 작은 것부터 시작한다
큐에 넣는 시점	dist가 갱신 될 때에만 그 점에서 출발하는 간선을 우선순위 큐에 넣어준다.	모든 정점을 우선순위 큐에 넣고 시작한다
용도	점과 점 사이의 거리를 구할 경우	최소 신장 트리를 그릴 때
끝	점과 점 사이의 최단 거리를 찾고 나면, 더이상 탐색하지 않는다. 목적에 따라 끝까지 그릴 수도 있다.	최소 신장 트리가 만들어 질 때까지(모든 점들이 다 이어질 때 까지) 탐색한다.
두 덩이일 경우	한 덩이만 그려지고 다른 한덩이는 그려지지 않는다(이어져 있지 않기 때문에)	간선 중심이므로 끝까지 가면 결국 두 덩이 다 그려진다.
모든 선이 다 이어지는가	정점 중심이므로 모든 정점이 다 이어지지 않을 수도 있다.	모든 정점이 다 이어진다.
최소?	임의의 두 점 간의 최소 거리를 구할 때 사용	최소의 비용으로 모든 점을 다 이을 때 사용. 모든 점을 다 이은 경우에는 최소의 비용이라 말 할 수 있다. 그렇지만 임의의 두 점 간의 거리가 최소라는 보장은 할 수 없다.

 

다익스트라는

1. 시작점의 dist를 0으로 해놓고, 시작점과 연결된 정점을 모두 우선순위 큐에 넣어준다

2. 그리고 우선순위 큐에서 간선을 꺼내 와서 그 간선을 썼을 때 최소 dist를 갱신할 수 있는지 보고

3. 갱신 가능하면 갱신한 후

4. 그 점과 이어진 간선을 지금까지 가중치 + 그 간선의 가중치 해서 우선순위 큐에 다시 넣어준다.

다익스트라를 끝까지 돌린다고 MST가 나오는건 아니다!

 

 

 

크루스칼은

1. 우선순위 큐에 모든 간선을 다 넣는다

2. 우선순위 큐에서 가중치가 작은 순서로 간선을 꺼내온 뒤, 그 간선을 추가했을 때 사이클이 생기는지를 union-find로 판단한다.

3. 사이클이 생기지 않는 경우, 간선을 그려주고 그 가중치를 더해간다.

4. pq를 다 돌고 나면(이것도 맞지만) 또는  union이 true인 횟수가 v-1번째가 되면(이게 더 효율적!) MST가 완성된다.

(parents[i] < 0 인 개수가 하나인 경우도 MST가 완성됐다고 볼 수 있지만, 이거 보려고 매번 다 도는건 시간낭비다. 이 방식으로 했다가 백준 1647.도시분할계획 시간초과 뜸)