[자료구조] 최소 스패닝 트리

[자료구조] 최소 스패닝 트리

신장 트리(spanning tree)란

• n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 이루어진 트리
• 깊이 우선 신장 트리 : 깊이 우선 탐색을 이용하여 생성된 신장트리
• 너비 우선 신장 트리 : 너비 우선 탐색을 이용하여 생성된 신장트리

최소 비용 신장 트리(minimum cost spanning tree)란

• 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리
• 최소 비용 신장 트리를 만드는 알고리즘 : 크루스칼,프림 알고리즘 등

크루스칼 알고리즘 1

• 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 방법
  1. 그래프 G의 모든 간선을 가중치에 따라 내림차순으로 정렬한다.
  2. 그래프 G에서 가중치가 가장 높은 간선을 제거한다. 이때 정점을 그래프에서 분리시키는 간선은 제거할 수 없으므로 이런 경우에는 그 다음으로 가중치가 높은 간선을 제거한다.
  3. 그래프 G에 간선이 n-1개만 남을 때까지 2를 반복한다
  4. 그래프에 간선이 n-1개만 남으면 최소 비용 신장트리가 완성

크루스칼 알고리즘 2

• 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 방법
  1. 그래프 G의 모든 간선을 가중치에 따라 오름차순으로 정리한다.
  2. 그래프 G의 가중치가 가장 낮은 간선을 삽입한다. 이때 사이클을 형성하는 간선은 삽입할 수 없으므로 그 다음으로 가중치가 낮은 간선을 삽입한다.
  3. 그래프 G의 간선이 n-1개 삽입될 때까지 2를 반복한다
  4. 그래프 G의 간선이 n-1개가 되면 최소 비용 신장 트리가 완성.
• 이때 사이클이 형성되었는지 확인하는 방법으로 dfs나 유니온 파인드 적용

프림 알고리즘

• 간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해 나가는 방법.
  1. 그래프 G에서 시작 정점을 선택
  2. 선택한 정점에 부속된 모든 간선 중에서 가중치가 가장 낮은 간선을 연결하여 트리를 확장한다.
  3. 이전에 선택한 정점과 새로 확장된 정점에 부속된 모든 간선 중에서 가중치가 가장 낮은 간선을 삽입한다. 단 사이클을 형성하는 간선은 삽입할 수 없으므로 이런 경우엔 그 다음으로 가중치가 낮은 간선을 선택한다.
  4. 그래프 G의 간선이 n-1개 삽입될 때까지 3을 반복한다.
  5. 그래프 G의 간선이 n-1개가 되면 최소 비용 신장 트리가 완성
• 가중치가 가장 높거나 낮은 간선을 선택하는 방법으로는 우선순위 큐 사용을 추천