자료구조 - 최소 신장 트리 (MST, Minimum Spanning Tree)

[개요]

1. 트리란?

1) 무향 그래프 G가 순환이 없는 그래프이면 G는 숲이다.

2) 무향 그래프 G가 순환이 없는 연결 그래프이면 G는 트리이다.

- G는 순환이 없고, 단순 그래프에서 간선을 추가할 경우 순환이 생긴다.

- G는 연결 그래프이고, 어떤 간선을 제거하면 연결그래프가 아니다.

- G의 어떤 두 정점에 대해서 단순 경로가 하나 존재한다.

 

2. 신장 트리 (Spanning Tree)

- 무향 연결 그래프 G의 부분그래프이고 G의 모든 정점을 포함하는 트리(Tree)인 그래프

 

1) 깊이 우선 신장 트리 (DFS Spanning Tree)

무향 연결 그래프 G에서 깊이 우선 탐색(DFS)으로 탐색하면서 생성된 신장 트리 (Spanning Tree)

 

2) 너비 우선 신장 트리 (BFS Spanning Tree)

무향 연결 그래프 G에서 너비 우선 탐색(BFS)으로 탐색하면서 생성된 신장 트리 (Spanning Tree)

 

3) 최소 신장 트리 (Minimum Spanning Tree)

무향 연결 가중 그래프 G에서 간선의 가중치의 합이 최소인 신장 트리

 

jina-developer.tistory.com/115

알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm)

 

 

 

 

 

참고 사이트

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