SOO-MST-Prim

Prim 알고리즘 리뷰

신장트리 : 모든 정점이 나머지 다른 정점과의 유일한 경로 모두 존재
최소신장트리 : N개 정점을 가진 그래프에서 N개 정점을 모두 연결하기 위해 N-1개(최소 간선수) 간선(무향)을 선택하여 만든 최소 비용의 트리
크루스칼 : uninon - Find
크루스칼과 프림 모두 “GREEDY”

정점 중심 : Prim(인접행렬, 인접리스트), Dijkstra
간선 중심 : Kruskal, Bellman-Ford

하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식

임의 정점을 하나 선택해서 시작
선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
모든 정점이 선택될 때까지 1, 2과정을 반복

서로소인 2개의 집합(2 disjoint-sets) 정보를 유지

트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들
비트리 정점들(non-tree vertices) - 선택 되지 않은 정점들

PrimTest.java

인접리스트 : $O( V^2 + E )$ 간선의 개수가 적으면 인접행렬을 사용했을 때와 차이가 많이 나게 된다.
인접행렬 : $O( 2V^2 )$ ; $V \le 1000$
크루스칼 : $O( E log E + V-1)$

Prim with Priority Queue

알고리즘

MST-PRIM(G, r) // G: 그래프, r: 시작 정점, minEdge[]: 각 정점기준으로 타 정점과의 최소 간선 비용
  result <- 0, cnt <- // result: MST 비용, cnt: 처리한 정점수, visited[]: MST에 포함된 정점여부
  FOR u in G.V
    minEdge[u] <- INF
  minEdge[r] <- 0 // 시작 정점 r의 최소비용 0 처리
  WHILE true
    u <- Extract-MIN() // 방문하지 않은(MST에 포함되지 않은 정점) 최소비용 정점 찾기
    ...
  return result
end MST-PRIM

PrimTest2_PQ.java

Priority Queue + 인접리스트 : $O( (V+E)logV )$