[알고리즘] Prim's Algorithm (프림 알고리즘)
프림 알고리즘 weight가 있는 undirected graph 에서 MST를 찾는 알고리즘 크루스칼 알고리즘 (krustal algorithm) 과 같은 용도. 상황에 따라 더 효율적인 알고리즘을 선택 작동 방식 임의의 vertex를 선택하여 Tree 생성 (현재 노드가 1개) T에 있는 노드와 T에 없는 노드 사이의 edge 중 weight가 최소인 edge를 찾는다 해당 edge가 연결하는 노드중, Tree에 없던 노드를 Tree에 추가 모든 노드가 Tree에 포함될 때까지 2-3을 반복 코드 구현 from math import inf graph = [ [inf, 10, inf, 5, inf, inf, inf], [10, inf, 2, 7, 12, inf, inf], [inf, 2, inf, inf..
