Goal
- 가중치 그래프에 대한 이해
- 가중치 그래프를 표현(또는 구현)할 수 있다
- 최소 신장 트리에 대한 이해
- 최소 비용 신장 트리를 구할 수 있다
사전 관련 지식 : 그래프
가중치 그래프(Weighted Graph)
그래프의 간선에 가중치가 있는 그래프
가중치 그래프는 다음과 같이 표현된다.
G = (V,E, w)
- V(G) : 그래프 G의 정점 집합
- E(G) : 그래프 G의 간선 집합
- w(e) : 간선 e의 가중치
(간선의 가중치(weight) 또는 비용(cost) 모두 같은 의미이다.)
가중치 그래치 그래프의 응용 분야는 매우 다양한데, 그 중에서 네트워크를 표현하는데 많이 사용되기 때문에 가중치 그래프를 네트워크라고도 한다.
가중치 그래프는 최소 환승, 최단 경로, 최소 비용 등과 같은 것들을 계산할 때 중요하게 활용될 수 있다.
총 비용 = 경로상 존재하는 간선의 가중치의 총합
가중치 그래프의 표현은 그래프와 마찬가지로 인접 행렬, 인접 리스트로 표현될 수 있다.
최소 신장 트리(MST)
신장 트리 중 가장 적은 비용의 간선으로 연결된 신장 트리
최소 신장 트리(MST : Minimu Spanning Tree) (또는 최소 비용 신장 트리)는 단어 의미상 다음과 같은 성질을 갖는다.
- 신장 그래프이다. 즉, 그래프의 모든 정점을 포함하는 부분 그래프이다.
- 트리이다. 즉, 싸이클이 없는 연결 그래프이다. (모든 노드간에 유일 경로가 존재한다)
- 그래프의 신장 트리 중 노드간 연결된 간선의 가중치가 최소이다.
네트워크 분야에서는 (1)모든 정점을 (2)가장 적은 수의 간선과 (3)가장 적은 비용으로 연결하는 것이 좋다.
이때, 최소 신장 트리(MST)가 사용될 수 있다.
최소 신장 트리를 구하는 방법
BFS, DFS를 통해 신장 트리를 얻을 순 있지만 최소 비용이라는 조건 만족시키지 못한다. 그래서 최소 신장 트리를 구하기 위해서는 최소 비용 신장 트리를 구하는 알고리즘을 사용해서 구해야 한다.
MST를 찾아내는 대표적인 기법으로 크루스칼 알고리즘(Kruskal’s algorithm)과 프림 알고리즘(Prim’s algorithm)이 있다.
최소 신장 그래프(MST)를 구하려면 다음과 같은 조건을 반드시 만족 해야한다.
최소 신장 트리의 조건
- 반드시 (n-1)개의 간선만 사용해야 한다.
- 사이클을 포함해서는 안된다.
- 간선 가중치 합이 최소이어야 한다.
최소 신장 트리를 구하는 알고리즘
> 크루스칼 알고리즘(Kruskal’s algorithm)
Kruskal's algorithm vs Prim's algorithm
Kruskal 알고리즘
- 간선을 기준으로 트리를 확장해 나간다.
- 시간 복잡도 O($E\log_2{E}$)
- 희소 그래프(Sparse Graph)에 적합한 알고리즘
Prim 알고리즘
- 정점을 기반으로 트리를 확장해 나간다.
- 시간 복잡도
- 인접행렬 : O($V^2$)
- 이진 힙과 인접 리스트 : O(ElogV)
- 피보나치 힙과 인접 리스트 : O(E+VlogV)
- 밀집 그래프(Dense Graph)에 적합한 알고리즘
참고)
https://ratsgo.github.io/data%20structure&algorithm/2017/11/12/disjointset/
bowbowbow.tistory.com/26#union-find-%EB%9E%80
https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html
https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
