MST 구하는 알고리즘으로 크루스칼(Kruskal)이랑 프림(Prim) 두 개가 있잖아요. 둘 다 최소 신장 트리 만드는 건 똑같은데 접근 방식이 다르다는 건 알겠는데, 실제로 문제 풀 때 어느 걸 골라야 하는지 기준이 애매합니다.
제가 이해한 건 이래요.
// 크루스칼: 간선을 가중치 순으로 정렬하고
// 사이클 안 생기면(union-find로 체크) 하나씩 채택
// 프림: 한 정점에서 시작해서
// 지금 트리에 붙일 수 있는 가장 싼 간선을 계속 추가
그러니까 크루스칼은 간선 중심이고 프림은 정점 중심이다, 이 정도로 정리하고 있는데요. 크루스칼은 유니온 파인드가 핵심이고 프림은 다익스트라처럼 우선순위 큐 쓰는 거고요.
궁금한 건, 간선이 적은 희소 그래프(sparse)면 크루스칼이 유리하고 간선이 빽빽한 밀집 그래프(dense)면 프림이 낫다 이런 얘기를 봤는데 왜 그런 건가요? 정렬 비용 때문인 건지요. 그리고 코테에서는 그냥 둘 중 하나 손에 익은 걸로 밀어도 되는 건지, 아니면 상황 봐서 갈아타야 유리한 케이스가 실제로 있는지 궁금합니다.