최소 신장 트리 - 크루스칼 알고리즘

크루스칼 알고리즘이란?

가장 적은 비용으로 모든 노드를 연결하는 알고리즘입니다.

최소 비용 신장 트리를 만들 때 사용합니다.

 

예제

트루스칼 알고리즘

위의 그림은 노드가 5개 간선이 6개인 그래프를 나타낸 것입니다.

이들을 연결하는 가장 효율적인 선의 개수는 노드 개수-1=4개입니다.

4개를 어떤 조합으로 선택하면 가장 효율적인 연결이 되는지 알 수 있는 것이 크루스칼 알고리즘입니다.

 

 

알고리즘

1. 간선의 거리를 오름차순으로 정리하고 짧은 순서대로 그래프에 포함시킨다.

2. 사이클이 발생하는지 체크하고 발생한다면 해당 간선을 포함하지 않는다.

사이클

위의 그림이 사이클입니다.

1,2,3이 모두 연결되어 있지요.

1,2 그리고 2,3 사이에만 간선이 있어도 같은 그래프가 되는데 굳이 간선 하나를 더 사용할 필요는 없겠죠.

 

간선 길이를 오름차순으로 정리하면

1-2:10, 3-4:20, 1-5:25, 2-3:30, 2-4:45, 3-5:50입니다.

1-2를 포함시킵니다. [1-2]

3-4를 포함시킵니다. [1-2, 3-4]

사이클 유무를 확인합니다.

각 노드의 최상위 노드가 

1-5를 포함시킵니다.[1-2, 3-4, 1-5]

사이클 유무를 파악합니다.

2-3을 포함시킵니다.[1-2, 3-4, 1-5, 2-3]

사이클 유무를 파악합니다.

2-4를 포함시킵니다. [1-2, 3-4, 1-5, 2-3]

그렇게 되면 간선이 4개 포함되고 모든 노드가 아래와 같이 연결됩니다.

크루스칼 알고리즘

 

사이클 유무는 합집합 알고리즘(union-find를 사용합니다.)

진행 과정에서 사이클 테이블을 만들어 최상위 노드를 계속 추가해줍니다.

사이클

예를 들어 위의 그래프가 1-2:10, 2-3:25, 1-3:30로 연결되어있다고 해봅시다.

크루스칼 알고리즘에 의하면 

1-2가 추가되겠죠.

그런 다음 2-3이 추가되고요.

이때 사이클 테이블을 만들어

1:1, 2:1, 3:1 이런 식으로 union_find를 실행해줍니다.

그리고 3-1에서 3이 이미 1과 같은 그래프에 있기 때문에 포함하지 않아도 된다는 판단을 할 수 있지요.