MST와 DIJKSTRA를 구분하는 방법

MST는 무조건 양방향 그래프다.

양방향 그래프가 주어지면 MST로 풀 수 있는가를 의심하면 된다.

간적크간많프

개인적으로 PQ를 직접 구현할 수 있는 수준이면 prim을,

DisjointSet을 구분하는 로직을 잘 짜면 Kruskal을 추천하신다고 하셨다.

 

DIJKSTRA의 경우에는 상황에 따라 양방향/단방향으로 주어지는데

대부분의 시험 문제는 단방향으로 주어지는 경우가 많다.