[algorithm] MST(최소신장트리), Prim 알고리즘

Graph algorithm에서 나오는 용어들이다

MST란 Minimum Spanning Tree(최소 신장 트리)인데, 모든 Vertex가 연결되어있고 Edge의 갯수가 Minimum인 Tree이다

Prim's 알고리즘이란 Graph에서 MST를 찾기 위한 알고리즘 중 하나이다

Time complexity는 Graph의 implementation에 따라 바뀌는데, prim's algorithm wikipedia를 인용하면

AdjMatrix일 경우 V^2

BinHeap + AdjList일 경우 O(ElogV) (= O((V+E)logV) )

등이 된다

시간 계산법은 기회가 되면 나중에 추가하도록 하겠다

https://en.wikipedia.org/wiki/Prim%27s_algorithm