MST(Minimum Spanning Tree)

1. MST(Minimum Spanning Tree)

1.1. Spanning Tree(신장 트리) 개념

출처: https://velog.io/@jailies/with-Python-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-myhrmdd0

• 신장트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.
  • 이 때 모든 그래프가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다.
• n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다.
• 즉, 그래프에서 일부 간선을 선택해서 만든 트리

1.2. MST(Minimum Spanning Tree, 최소 신장 트리) 개념

• Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
  • 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다.
  • MST는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말한다.
  • 즉, 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.

1.3. MST 특징

• 간선의 가중치의 합이 최소여야 한다.
• n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
• 사이클이 포함되어서는 안된다.

• •  

2. Kruskal MST 알고리즘

2.1. Kruskal MST 알고리즘 개념

• 대표적인 MST 알고리즘이다.
• 가장 적은 비용으로 모든 노드를 연결할 수 있다.
• 그리디 알고리즘이다.
• 신장 트리에 포함되는 간선의 개수가 '노드의 개수 - 1'과 같다는 특징이 있다.

2.2. 과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는 지 확인한다.
   • 사이클이 발생하지 않는 경우 MST에 포함시킨다.
   • 사이클이 발생하는 경우 MST에 포함시키지 않는다.
3. 모든 간선에 대하여 2번의 과정을 반복한다.

2.3. 시간 복잡도

• 간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가진다.
• 왜냐하면 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업이기 때문이다.
• 크루스칼 내부에서 사용되는 서로소 집합 알고리즘의 시간 복잡도는 정렬 알고리즘의 시간 복잡도보다 작으므로 무시한다.

---

참고

나동빈.『이것이 코딩테스트다 with 파이썬』.한빛미디어, 2020.

https://github.com/WeareSoft/tech-interview/blob/master/contents/algorithm.md#mst%EB%9E%80

GitHub - WeareSoft/tech-interview: 🙍 tech interview