프림 알고리즘
최소 비용 신장트리를 찾는알고리즘 중 하나로
특정 시작점부터 { 연결될 수 있는 노드들중 최소비용 노드를 연결 } 을 반복합니다.
연결시 이미 만난 노드라면 연결하지 않습니다.
단점 : 연결되지 않은 두개의 트리가 있을 시에는 최소신장을 찾을 수 없습니다.
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
'IT > Algorithm' 카테고리의 다른 글
[Greedy] Floyd Algorithm (0) | 2021.10.13 |
---|---|
[Greedy] Dijkstra Algorithm (0) | 2021.10.13 |
[Greedy] Kruskal Algorithm (0) | 2021.10.12 |
Sort Algorithm (0) | 2021.10.12 |