신장 트리 (Spanning Tree) & 크루스칼(Kruskal)

신장트리

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

 

이러한 성질을 가진 그래프는 다양한 문제에 활용되는데,

대표적인 유형이 여러 노드를 연결하는 간선이 비용을 가질 때, 그 비용의 합이 최소가 되는 신장트리를 찾아야 하는 경우이다.

예를 들어보면, 아래와 같은 그래프가 존재 한다고 한다.

 

간선의 비용의 합을 최소로 하기는 신장트리가 되기 위해서는 아래와 같이 연결을 해야 할 것이다.

 

이처럼 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트릴르 찾는 알고리즘을 이제 '최소 신장 트리 알고리즘'이라고 하자.

이러한 최소 신장 트리 문제를 해결하기 위한 대표적인 알고리즘을 다음을 통해 배워보자.

 

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

이는 가장 적은 비용으로 모든 노드를 연결할 수 있는 알고리즘으로 그리디 알고리즘으로 분류된다.

 

2단계로 알고리즘을 설명하면,

 

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2.  간선에서 하나씩 확인하여 현재의 간선에서 사이클이 발생하는지 확인하고 본 과정(2)을 반복한다.
   1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
   2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.

 

이는 신장 트리의 성질을 활용한 알고리즘으로 이해할 수 있는데, 신장 트리에 노드와 간선의 관계는 다음과 같다.

간선의 개수 = 노드의 개수 - 1

이를 활용해 크루스칼 알고리즘은 사이클이 발생시키는 간선을 제외한 가정 거리가 짧은 간선(비용이 작은)부터 차례대로 신장 트리에 추가한다. 이러한 과정은 항상 최적의 해를 보장한다고 할 수 있기 때문에 반드시 알아두어야 한다.

 

파이썬 소스