[DS] 최소 신장 트리(Minimum Spanning Tree)란?

신장 트리(Spanning Tree) 란?

한 Graph의 모든 vertex를 연결하는 cycle이 없는 sub graph입니다.

 

- 스패닝 트리는 (n-1)개의 edge를 가진다.

- 스패닝 트리는 DFS, BFS 알고리즘을 이용해 찾을 수 있다.

(움직인 edge를 연결하면 된다.)

- Cycle이 있어서는 안된다.

 

아래와 같은 그래프가 존재할 때 

DFS, BFS spanning tree를 만들어보면

 

 

 

↓↓↓     DFS    ↓↓↓ 

https://yyyeji.tistory.com/379

[DS] 깊이 우선 탐색(DFS)이란?

 

 

 

↓↓↓     BFS    ↓↓↓ 

https://yyyeji.tistory.com/380

[DS] 넓이 우선 탐색(BFS)이란?

이렇게 됩니다.

 

 

 

신장 트리(Spanning Tree) 관련 용어(Terminology)

---

 

Biconnected components - articulation point를 갖지 않는 connected graph

Articulation point - 해당 vertex를 제거했을 때, 원 graph가 두 개 이상의 biconnected component로 분리되는 vertex

 

 

아래 그래프에서 articulation point는

ⓐ 입니다.

 

 

 

최소 신장 트리(Minimum Spanning Tree)

---

Weighted graph에서 cost의 합이 최소인 spanning tree입니다.

 

cost의 합을 최소로 만드는 알고리즘은 여러개가 있습니다.

 

① Kruskal's Algorithm

전체 edge 집합을 cost 순서로 sort하고, cost 순서대로 edge를 판단하는 알고리즘입니다.

 

- 전체 edge의 집합을 cost 순서로 sorting한다.

- Cost 순서로, 해당 edge가 cycle을 이루지 않으면 선택한다.

- (n-1)개의 edge가 선택될 때까지 반복한다.

 

 

cost가 낮은 순으로 이동하기 때문에 1(edge)을 먼저 선택합니다.

 

 

2(edge)를 선택하면 cycle이 이뤄지지 않기 때문에 2(edge)를 선택합니다.

 

다음으로 큰 3(edge)를 선택합니다.

 

다음으로 4(edge)를 선택하게 되면 cycle이 만들어지기 때문에 5를 선택합니다.

 

 

cycle이 만들어지지 않는 이상 cost 순서대로 edge를 선택합니다.

 

.

.

.

 

6(n-1)개의 edge가 생성되었으므로 종료합니다.

 

 

 

 

 

② Prim's Algorithm

시작 vertex에서 시작하여 현재 유지되고 있는 conneccted component와 연결된 edge를 고려하는 알고리즘입니다.

 

- 시작 vertex로부터 시작을 한다.

- 현재 구성되는 connected component와 외부로 연결된 edge 중에서 최소 cost edge를 선택한다.

- (n-1)개의 edge가 선택될 때까지 반복한다.

 

 

ⓐ를 시작 vertex로 잡으면 갈 수 있는 edge가 7, 8, 4, 2 입니다.

 

 

그 중에서 cost가 제일 작은 2 edge를 선택합니다.

ⓐ와 ⓑ에서 갈 수 있는 edge는 7, 8, 4, 3인데 

 

 

cost가 제일 작은 3 edge를 선택합니다.

ⓐ, ⓑ, ⓔ 에서 갈 수 있는 edge는 7, 8, 4, 1, 6입니다.

 

 

cost가 제일 작은 1번을 선택합니다.

.

.

.

선택된 vertex 중에서 cycle을 이루지 않는 가장 작은 edge 선택을 반복하다가

 

 

6(n-1)개의 edge가 선택되면

알고리즘을 종료합니다.

 

 

③ Sollin's Algorithm

각 node를 개별 connected component로 고려하여, 한 개씩 edge를 선택하여 추가하는 알고리즘입니다.

 

- 각 vertex를 서로 다른 connected component로 고려한다.

- 각 connected component에 대하여 최소 cost edge를 한 개씩 추가한다.

- 전체가 한 개의 connected component가 되면 종료한다.

 

 

각 vertex에서 작은 cost의 edge를 하나씩 선택하게 됩니다.

 

 

ⓐ - 2, ⓑ -2, ⓒ - 5

ⓓ - 1, ⓔ - 1, ⓕ - 5, ⓖ - 6

를 한 번에 선택하고 

 

 

묶는 vertex는 하나로 생각해 줍니다.

여기서 다시 한 번에 edge를 선택해 줍니다.

 

 

 

ⓐ , ⓑ - 3

ⓒ, ⓕ - 7

ⓓ, ⓔ, ⓖ - 3

 

다른 알고리즘과 마찬가지로 6(n-1)개의 edge가 선택되면

알고리즘을 종료합니다.

 

 

 

◡̈