Advanced Algorithm - MST(concepts of the MST)(1)

1. 신장 트리(Spanning Tree)란? 

- 그래프 내부의 모든 노드가 연결되어 있으며, 동시에 트리의 속성을 만족하는 그래프를 의미한다.

• 그래프의 모든 노드가 서로 연결되어 있다.(거리는 멀어도 접근경로가 있다.)
• 트리의 속성을 만족한다.(사이클이 없음)

좌측의 그래프에서 파생될 수 있는 신장트리의 종류(우측)를 표현

 

---

2. 최소 신장 트리(Minimum Spanning Tree)란? 

- 하나의 그래프를 기반으로 파생된 신장트리 중에서, 간선의 가중치 합이 최소인 신장트리를 의미한다.

- Minumun Spanning Tree의 약자로 MST라고 부른다. 

 

---

3. MST 대표 알고리즘

- MST 알고리즘이란, 어떤 그래프를 가지고 MST를 구하는 방법을 의미한다. 

- 대표적으로 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리즘(Prim's Algorithm)이 있다. 

---

4. 크루스칼 알고리즘(Kruskal's Algorithm)의 이해

- MST를 이루는 기본조건은 다음과 같다.

• 그래프 내부의 모든 노드는 연결되어야 한다. (Spanning Tree의 특징)
• 노드간의 사이클은 존재하지 않는다. (Spanning Tree의 특징)
• 그래프에서 파생된 Spanning Tree 중에서 가장 낮은 가중치를 갖는 간선의 조합으로 이루어진다. (Minimum Spanning Tree의 특징)

 

- 그렇다면 크루스칼 알고리즘에서는 MST를 찾기 위해서는 어떤 과정을 거칠까? 기본과정은 다음와 같다.

1. 모든 정점을 독립적인 집합(개별집합)으로 만든다.
2. 모든 간선을 가중치(비용)를 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점(루트노드)을 비교한다.
3. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다.(사이클 발생유무 판단과정) 
4. 모든 노드가 연결될 때까지 2, 3번 과정을 반복한다. 

 

- 사실 위에 설명된 크루스칼 알고리즘의 기본과정이 무슨소리인지 잘 이해가 가지않는다. 아래에 나오는 Union-Find 알고리즘을 이해해야만 무슨 뜻인지 알게 될 것이다. 그러므로 다음과 같이 설명하겠다. 

1. 각 노드를 독립적인 개별집합으로 만든다. 
2. 그래프가 갖고 있는 모든 간선의 가중치를 오름차순(뒤로 갈수록 높은 가중치)으로 정렬한다.
3. 가장 낮은 가중치를 갖는 노드부터 하나씩 시작 정점과 이어나간다.
4. 시작 정점과 이어지는 노드간에 사이클이 존재하는지 검증하고, 사이클이 없다면 해당 노드를 시작 정점과 연결한다.
5. 모든 노드가 연결되는 경로가 생성될 때까지 위의 과정을 반복한다. 

 

* 위의 과정에서 알 수 있는 크루스칼 알고리즘의 특징은 탐욕 알고리즘을 기반한 선택과 결정을 한다는 것이다. (매 순간 가중치가 가장 작은 간선을 우선 연결한다는 점) 

 

 

- 아래의 그림을 보면서 MST 알고리즘의 과정을 생각해보자. 

 

 

a) 크루스칼 알고리즘을 적용할 기본 그래프

무방향 그래프

 

 

b) 크루스칼 알고리즘의 진행 과정

 

 

• 1단계 - [A↔D, 5] / 사이클 없음
• 2단계 - [C↔E, 5] / 사이클 없음
• 3단계 - [D↔F, 6] / 사이클 없음 

 

 

 

 

4단계 - [A↔B, 7] / 사이클 없음

5단계 - [B↔E, 7] / 사이클 없음

6단계 - [E↔G, 9] / 사이클 없음

 

* 간선 [D↔E, 7], [F↔E, 8], [D↔B, 9]을 연결하지 않는 이유는 사이클이 생성되기 때문이다. 

* 간선 [F↔G, 11]을 연결하지 않는 이유는 이미 모든 노드간의 경로가 존재하기 때문이다. 

 

 

- 위의 예제를 통해, 크루스칼 알고리즘의 기본 메카니즘을 이해할 수 있다. 여기서, 한가지 궁금증이 생긴다. 이 과정을 코드로 구현한다면 사이클의 생성유무를 어떻게 판단할 것인가? 라는 부분이다. 

 

-  사이클의 유무를 검증하기 위하여, 크루스칼 알고리즘에서는 Union-Find 알고리즘을 사용한다.