저번 포스팅에서 연결그래프의 MST(Minimum Spanning Tree) 를 구하는 방법인 Prim 알고리즘에 대해 소개하고 그 정확성을 증명해보았습니다. https://matt1235.tistory.com/51 Prim 알고리즘 - 1 이번 포스팅에서는 Prim Algorithm을 소개하고, 그 정확성을 증명해보고자 한다. 다음 그림을 보자. 정점이 다섯 개가 있고 간선(edge)이 총 10개 있는 연결 그래프이다. 각 간선의 숫자는 노드에서 노 matt1235.tistory.com 이번 포스팅에서는 Prim을 구현해보겠다. => 우선순위 큐를 이용해 구현 우선순위 큐 (Priority Queue) 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 방식..

이번 포스팅에서는 Prim Algorithm을 소개하고, 그 정확성을 증명해보고자 한다. 다음 그림을 보자. 정점이 다섯 개가 있고 간선(edge)이 총 10개 있는 연결 그래프이다. 각 간선의 숫자는 노드에서 노드까지의 거리를 나타낸다. 위 그래프에서 MST(최소 비용 신장 트리)를 구하라. 용어 신장트리(Spanning Tree) 그래프 내 모든 정점을 포함하는 트리를 의미. 모든 정점이 연결되어 있어야 하고, 사이클을 포함해서는 안된다. 따라서 신장트리는 노드가 n개라면 정확히 (n-1) 개의 간선을 갖는다. 신장트리의 예시로는 다음이 있다. 이처럼 모든 노드가 연결되어 있고, 사이클을 만들지 않으면 Spanning Tree 완성이다. 간선의 수는 자연스레 (노드수 - 1) 이 된다. 우리가 위 문..