MST

그래프를 구성하는 간선들에 비용이 있는 그래프 G가 존재할 때, 비용의 가중치(합)를 최소로 하여 사이클이 없이 모든 정점들을 연결하는 트리

• 프림 (Prim)
  1. 그래프의 임의의 정점을 시작점으로 선정
  2. 고른 정점에서 다른 정점으로 가는 간선들 중 비용이 가장 작은 간선을 이어 하나의 서브 트리를 구성한다.
  3. 구성된 신장 트리에서 다른 정점으로 가는 간선들 중 비용이 가장 작은 간선을 서브 트리에 추가
  4. 모든 정점들이 이어질 때까지 3번 과정을 반복한다. (단, 사이클이 형성되지 않게 해야 한다.)
     • 프림 알고리즘은 시작 정점에서부터 간선을 하나 씩 이어가며 최소 신장 트리를 구성하기 때문에 그래프 순회 알고리즘과 비슷하게 이미 방문한 정점임을 표시해 두면 사이클의 유무를 알 수 있다.
• 크루스칼 (Kruskal)
  1. 그래프의 모든 간선들을 비용을 기준으로 힙에 저장한다. (혹은 간선들을 비용을 기준으로 정렬)
  2. 힙에 모든 간선들이 저장되어 있기 때문에 매 순간 비용이 가장 작은 간선들을 쉽게 구할 수 있다.
  3. 최소 비용을 갖는 간선들을 사이클이 형성되지 않게 서로 이어주다 보면 최소 신장 트리가 완성된다.
     • 이 때, 그래프의 사이클 생성 여부는 서로소 집합을 저장하는 Union-find에 따라 판별될 수 있다.
     • 현재 선택된 간선으로 이어지는 두 정점의 root(부모 노드)가 같다면 두 정점은 같은 집합에 속해 있기 때문에 (이미 스패닝 트리로 구성되어 있는 정점임을 의미한다.) 간선을 추가하게 되면 사이클이 생긴다.