Minimum spanning tree (Prim's, Kruskal's algorithms)
Minimum spanning tree n 개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다. cycle 이 포함되어서는 안된다. 간선의 가중치의 합이 최소여야 한다. Prim - Minimum Spanning Tree 1: start vertex를 고른다 여기서 E B 가 3이니 가장 싼 값이라고 연결해버리면 ? Cycle이 생긴다. 1 ~ 3 트리를 초기화 시키고 제일 먼저 선택한 vertex 외의 길은 전부 무한으로 둔다 vertex는 자신에서 자신으로 가는 길이라 0 으로 초기화한다 . 4 모든 노드를 방문하는 길을 찾지 않았다면 반복하라 5~8 이웃의 길(그림에서 노란색으로 칠해지던 길) 에 대해 가장 적고 이미 포함되지 않은 vertex 로 가는 길을 찾는다 9 m..
