신장 트리(Spanning Tree) |
신장 트리는 그래프의 최소 연결 부분 그래프이다.
원래의 그래프에서 최소한의 간선만 사용해서 모든 노드를 연결한 트리이다.
간선의 수를 최소한으로 사용하기 때문에 정점의 갯수가 N개라면 신장트리의 간선수는 언제나 N-1개이다.
또한 사이클이 존재하지 않는다.
N개의 정점을 N - 1개의 간선으로 연결하면 반드시 트리형태가 되기때문에 신장 그래프가 아니라 신장 트리라고 부른다.
DFS, BFS를 사용해서 그래프에서 신장트리를 찾을 수 있고 하나의 그래프에 여러개의 신장트리가 있을 수 있다.
통신 네트워크를 구축한다고 생각하면 이해가 빠르다.
회사 내에서 모든 전화기를 연결하되 가장 적은 수의 케이블을 사용하고 싶은 경우에 사용한다.
정리하면 신장트리는
1) 모든 정점이 연결되어 있어야 한다.
2) 간선을 최소한의 갯수로 사용해야 한다.
정점이 N개라면 N - 1개의 간선을 사용한다.
사이클이 존재하지 않는다.
최소 신장 트리(Minimum Spanning Tree) |
신장트리 중 간선의 가중치 합이 최소인 신장 트리
즉 가장 적은 비용으로 모든 노드를 연결하는 트리
최소 신장 트리는 영문을 줄여서 MST라고 자주 부른다.
신장트리는 갯수가 최소였는데 MST는 갯수도 최소이면서 가중치의 합도 최소이다.
정리하면 MST는
1) 모든 정점이 연결되어 있어야 한다.
2) 간선을 최소한의 갯수로 사용해야 한다.
정점이 N개라면 N - 1개의 간선을 사용한다.
사이클이 존재하지 않는다.
3) 간선의 가중치의 합이 최소여야 한다.
MST 알고리즘 |
모두 연결하되 최소 비용으로 연결해야 한다면 MST를 떠올리면 된다.
MST는 크루스칼 알고리즘이나 프림 알고리즘으로 만들 수 있다.
크루스칼 알고리즘
- 간선을 선택하며 진행한다.
그래서 간선이 적은 그래프를 MST로 만들때 적합하다.
간선으로 이어지는 두 노드를 유니온 파인드로 합쳐나가면서 진행한다.
- 사이클 검사가 필요하다.
간선을 선택하므로 트리가 여러개 생길 수 있고 사이클이 생기지 않도록 그 중에서 선택해야 한다.
프림 알고리즘
- 정점을 선택하며 진행한다.
그래서 간선이 많은 그래프를 MST로 만들때 적합하다.
- 시작 정점을 정해두고 시작하며 사이클 검사가 필요하지 않다.
인접한 정점들 중에 선택해 나가는 방식이므로 최종적으로 하나의 트리가 생성된다.
알고리즘 설명은 알고리즘탭에 해뒀으니 링크만 남겨둠
https://smallpants.tistory.com/285
MST 알고리즘(크루스칼, 프림)
smallpants.tistory.com
※ 참고 문헌