최소 스패닝 트리 - kruskal 알고리즘

[알고리즘] 최소 스패닝 트리 - kruskal 알고리즘

• 최소 스패닝 트리
1. 정의: 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리를 찾는 문제
2. 종류: kruskal 알고리즘, prime 알고리즘이 존재한다.

• kruskal 알고리즘
1. 정의: 최소 스패닝 트리를 구현하는 하나의 방법으로 가중치가 가장 작은 간선이 최소 스패닝 트리에 포함될 가능성이 높다는 생각에 착안되어서 만들어진 알고리즘  
2. 구현 방법: 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가를 한다. 단, 추가를 했을 경우 사이클이 발생하면 안되기 때문에 이 간선은 제외해야 한다.
• 참고 문제: [LAN] 근거리 네트워크 http://yejin0730.tistory.com/10
• 출처: 알고리즘 문제 해결 전략2