[Greedy] Prim's Algorithm

프림 알고리즘

 

최소 비용 신장트리를 찾는알고리즘 중 하나로

 

특정 시작점부터 { 연결될 수 있는 노드들중 최소비용 노드를 연결 } 을 반복합니다.

연결시 이미 만난 노드라면 연결하지 않습니다.

 

단점 : 연결되지 않은 두개의 트리가 있을 시에는 최소신장을 찾을 수 없습니다.

 

ex)

Start A

    (5, 13)  -> 5 D 연결

A, D

    (7, 9, 13) -> 7 C 연결

A, D, C

    (5, 9, 13, 20) -> 5 E 연결

A, D, C, E

    (9, 13, 15, 20) -> 9 중복 -> 13 B 연결

A, D, C, E, B

    (8, 15, 20) -> 8 F 연결

A, D, C, E, B, F