최소비용신장트리 - 프림, 크루스칼

최소비용으로 고속도로 만들기

 

프림 알고리즘

프림 알고리즘 - 위키백과  

시작 : D (아무데서나 시작해도 결과는 같음.)

1) D - A (5 cost)
2) D - F (6 cost)
3) A - B (7 cost)
4) B - E (7 cost)
5) E - C (5 cost)
6) E - G (9 cost)

구현 : 우선순위 큐

   

크루스칼 알고리즘

크루스칼 알고리즘 - 위키백과

1) A - D (5 cost)
2) C - E (5 cost)
3) D - F (6 cost)
4) A - B (7 cost)
5) B - E (7 cost)
6) E - G (9 cost)

구현 : Disjoint Set (유니온-파인드)