신장 트리(Spanning Tree)
모든 정점이 n개인 무방향 그래프 G에서 정점이 n개이고 간선이 n-1개인 트리 형태의 부분 그래프를 신장 트리라고 함
사이클이 없는 부분 그래프
- 그래프에서 순회를 하면 n-1개의 간선을 이동하면서 n개의 모든 정점을 방문하게 되므로 순회 경로는 신장 트리가 됨
- 깊이 우선 신장 트리 : 깊이 우선 탐색을 이용하여 생성된 신장 트리
- 너비 우선 신장 트리 : 너비 우선 탐색을 이용하여 생성된 신장 트리
결국, 신장 트리는 간선을 최소로 이용하여 모든 정점을 연결한 그래프
최소 비용 신장 트리(Minimum Spanning Tree, MST)
가중치 그래프에서 간선에 주어진 가중치는 비용, 거리, 시간을 의미하는 값이 될 수 있음
무방향 가중치 그래프에서 신장 트리 비용은 신장 트리를 구성하는 간선 n-1개의 가중치를 합한 값이 됨
이때 가중치 합이 최소인 신장 트리를 최소 비용 신장 트리라고 함
알고리즘
크루스칼 알고리즘 1(Kruskal Algorithm)
가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 알고리즘
크루스칼 알고리즘 2(Kruskal Algorithm)
가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 알고리즘
- 유니온 파인드로 구현
프림 알고리즘(Prim Algorithm)
크루스칼 알고리즘처럼 미리 간선을 정렬하지 않고, 하나의 정점에서 시작하여 트리를 확장해 나가는 방법
- 우선순위 큐로 구현
