[알고리즘] 최소신장트리(MST, Minimum Spanning Trees) / 위상정렬

신장 트리(Spanning Tree)란?

---

신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미한다. n개의 정점이 있다면 신장 트리의 간선 수는 n-1개가 된다. 최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리이다. 가중치는 거리, 비용, 시간등으로 응용할 수 있다. 최소 신장 트리의 대표적인 알고리즘 으로는 프림 알고리즘과 크루스칼 알고리즘이 있다.

프림 알고리즘(Prim's Algorithm)

---

프림 알고리즘은 최소 신장트리에 연결된 정점 주변에 있는 간선의 가중치 중 가장 작은 것을 골라 최소 신장 트리를 만드는 방법이다. 

[과정]

크루스칼 알고리즘(Kruskal's Algorithm)

---

크루스칼 알고리즘은 그래프 내의 모든 간선의 가중치를 화가인하고 가장 작은 가중치부터 확인해서 최소 신장 트리를 만드는 방법이다.

[과정]

 

위상정렬

---

위상정렬이란 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 이는 싸이클이 없는 유향 그래프로 모든 정점을 일렬로 나열하되 정점 x에서 정점 y로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치한다. 일반적으로 임의의 유향 그래프에 대해 복수의 위상 순서가 존재한다.

 

 

참고 자료

---

https://ssabi.tistory.com/60

[알고리즘] 최소 신장 트리(Minimum Spanning Tree)