[DS] Graph MST & Shortest path

- 이전 글: [DS] Graph 개념과 탐색방법

 

3. MST (Minimum Spanning Tree)

 

최소 신장 트리 (MST)는 그래프의 최소 연결 트리를 의미한다. 최소 연결 트리란 edge의 weight가 최소인 spanning tree를 말한다. spanning tree는 그래프의 모든 정점을 cycle 없이 연결한 형태를 말한다.

 

최소 신장 트리는 N개의 정점과 N-1개의 간선으로 연결되어 있으며 가중치의 합이 신장 트리 중에 최소인 값이 되어야 하기 때문에 단순히 가장 적은 간선을 사용한다고 해서 최소 비용을 얻을 수 없다. MST를 찾는 대표적인 방법으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다.

 

1) Kruskal algorithm

 

greedy 한 방법으로 간선을 선택하여서 MST를 구하는 방법이다. 최소 비용의 간선으로 이루어진 MST를 찾기 위해서 간선을 오름차순으로 정렬하여 가중치가 작은 간선부터 순서대로 선택을 한다. 이때 사이클이 생기지 않도록 확인하면서 선택해야한다.

 

- 과정

1. 그래프의 간선을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선들을 순서대로 선택한다.
3. 선택한 간선이 사이클을 이루는지 확인한다.
   • 각 정점에 Index를 부여하고 정점들이 연결될 때마다 두 정점의 index를 통일해서 각각의 연결관계를 관리한다.
   • 이 방법으로 index가 같은 경우 같은 서브트리에 포함되어있기 때문에 사이클을 이룬다는 것을 파악할 수 있다.
4. 사이클을 이루지 않는 경우 MST에 해당 간선 정보를 추가한다.

 

- 시간복잡도

• Edge의 weight를 기준으로 정렬: O(E log E)
• cycle 생성 여부 확인 및 index 통일: O(E + V log V)
• time complexity: O(E log E)

 

2) Prim algorithm

 

Kruskal 알고리즘이 간선을 중심으로 알고리즘을 진행한다면 Prim 알고리즘은 노드에 집중해서 알고리즘을 진행한다. 초기 source 정점에서부터 인접한 정점들을 확인해서 가장 작은 가중치의 간선을 통해 연결되는 정점을 추가하는 방법을 반복한다. 한마디로 이미 MST 집합에 추가된 정점들로부터 인접한 정점들 중 가장 가까운 정점을 추가하는 방식으로 알고리즘을 진행한다.

 

- 과정

1. 시작 정점을 MST 집합에 포함한다.
2. MST 집합에 포함된 정점들에 대해서 인접한 정점들 중 최소 간선으로 연결된 정점을 선택하여 트리에 추가한다.
3. 위의 과정을 MST가 N-1 개의 간선을 가질 때까지 반복한다.

 

- 시간 복잡도: O(E log V)

 

 

4. Shortest path problem

 

최단 경로 문제는 그래프 상의 두 정점의 사이를 잇는 최단 경로를 찾는 문제이다. 최단 경로를 찾는 문제는 경로를 찾는 정점의 개수에 따라서 문제의 유형과 풀이방법이 달라진다. 문제의 유형은 다음과 같다.

 

• 단일 노드 - 단일 노드 문제: 단일 정점에서 다른 한 정점으로의 최단 경로를 찾는 문제이다.
• 단일 노드 - 전체 노드 문제: 단일 정점에서 다른 모든 정점으로의 최단 경로를 찾는 문제이다.
• 모든 노드 간의 경로 문제: 그래프에 존재하는 모든 정점들 간의 최단 경로를 찾는 문제이다.

 

1) Dijkstra Algorithm

 

다익스트라 알고리즘은 두 정점 간의 가장 짧은 경로를 찾는 알고리즘이다. 보통 알고리즘을 반복하여서 한 정점으로부터 나머지 정점들로의 최단 거리를 구하는데 사용하는 알고리즘이다. 우선순위 큐를 사용해서 가장 낮은 가중치를 가진 방문하지 않는 정점을 찾고 방문하지 않은 나머지 정점과의 거리를 계산하여 비교하는 방법으로 구현한다.

 

2) Bellman-Ford Algorithm

 

벨만 포드 알고리즘은 가중치가 음인 그래프에서 최단 거리를 찾는데 사용하는 알고리즘이다. 다익스트라보다 시간복잡도가 크지만 음의 가중치가 있는 그래프에서 최단거리를 구하기 위해서는 벨만 포드 알고리즘을 사용한다.

 

3) Floyd-Warshall Algorithm

 

모든 정점 간의 최단 경로를 찾는데 사용하는 알고리즘이다. 그래프의 가중치가 음이든 양이든 상관없이 사용할 수 있는 알고리즘이다. 두 정점의 사이에 대해서 다른 모든 정점을 경유하는 경로를 비교하여 최단 거리를 찾는 방법으로 진행된다.

 

 

[reference]

- https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

- https://ko.wikipedia.org/wiki/최단_경로_문제

최단 경로 문제 - 위키백과, 우리 모두의 백과사전