최소 신장 트리

최소 신장 트리(Minimum Spanning Tree: MST)

주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리
EX )
크러스컬 알고리즘
가중치가 가장 작은 선분이 사이클을 만들지 않을 때에만 ‘욕심내어’ 그 선분을 추가시킨다.
KruskalMST(G)(입력: 가중치 그래프 G=(V,E), |V|=n , |E|=m , 출력: 최소 신장 트리 T)

• 가중치의 오름차순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자.
  
• T=∅ // 트리 T를 초기화시킨다.
  
• while ( T의 선분 수 < n-1 ) {
  
• L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거한다.
  
• if (선분 e가 T에 추가되어 사이클을 만들지 않으면)
  
• e를 T에 추가시킨다.
  
• else // e가 T에 추가되어 사이클이 만들어지는 경우
  
• e를 버린다.
  }
  
• return 트리 T // T는 최소 신장 트리이다.
  시간복잡도 = O(mlogm)
  
  프림 알고리즘
  주어진 가중치 그래프에서 임의의 점 하나를 선택한 후, (n-1)개의 선분을 하나씩 추가시켜 트리를 만든다.
  추가되는 선분은 현재까지 만들어진 트리에 연결시킬 때 ‘욕심을 내어서’ 항상 최소의 가중치로 연결되는 선분이다.
  PrimMST(G)(입력: 가중치 그래프 G=(V,E), |V|=n, |E|=m, 출력: 최소 신장 트리 T )
  
• 그래프 G에서 임의의 점 p를 시작점으로 선택하고, D[p]=0으로 놓는다.
  // 배열 D[v]는 T에 있는 점 u와 v를 연결하는 선분의 최소 가중치를 저장하기 위한 원소이다.
  
• for (점 p가 아닌 각 점 v에 대하여) { // 배열 D의 초기화
  
• if ( 선분 (p,v)가 그래프에 있으면 )
  
• D[v] = 선분 (p,v)의 가중치
  
• else
  
• D[v]=∞
  }
  
• T= {p} // 초기에 트리 T는 점 p만을 가진다.
  
• while (T에 있는 점의 수 < n) {
  T에 속하지 않은 각 점 v에 대하여, D[v]가 최소인 점 vmin과 연결된 선분 (u,vmin)을 T에 추가한다.
  단, u는 T에 속한 점이고, 점 vmin도 T에 추가된다.
  
• for (T에 속하지 않은 각 점 w에 대해서) {
  
• if (선분 (vmin,w)의 가중치 < D[w])
  D[w] = 선분 (vmin,w)의 가중치 // D[w]를 갱신
  }
  }
  
• return T // T는 최소 신장 트리이다.
  시간복잡도 = O(n^2)
  
  다익스트라 알고리즘
  프림 알고리즘과 차이점
  
  1. 프림 알고리즘은 임의의 점에서 시작하나, 다익스트라 알고리즘은 주어진 출발점에서 시작한다.
     
  2. 프림 알고리즘은 트리에 하나의 점 (선분)을 추가시킬 때 현재 상태의 트리에서 가장 가까운 점을 추가시키지만,
     다익스트라의 알고리즘은 출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정한다.
     ShortestPath(G, s)(입력: 가중치 그래프 G=(V,E), |V|=n , |E|=m, 출력: 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D)
     
• 배열 D를 ∞로 초기화시킨다. 단, D[s]=0으로 초기화한다.
  // 배열 D[v]에는 출발점 s로부터 점 v까지의 거리가 저장된다.
  
• while (s로부터의 최단 거리가 확정되지 않은 점이 있으면) {
  
• 현재까지 s로부터 최단 거리가 확정되지 않은 각 점 v에 대해서 최소의 D[v]의
  값을 가진 점 vmin을 선택하고,
  출발점 s로부터 점 vmin까지의 최단 거리 D[vmin]을 확정시킨다.
  
• s로부터 현재보다 짧은 거리로 점 vmin을 통해 우회 가능한 각 점 w에 대해서
  D[w]를 갱신한다.
  }
  
• return D
  시간복잡도 = O(n^2)