[Python] 최소 신장 트리(MST, Minimum Spanning Tree)

정의

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

특징

• 간선의 가중치 합이 최소
• N개의 정점을 가지는 그래프에 대해 반드시 N-1개의 간선만을 사용
• 사이클이 존재해서는 안됨

🔗MST 구현 알고리즘

• Kruskal MST 알고리즘
• Prim MST 알고리즘