12.4 크루스칼 알고리즘 [디딤돌 자료구조와 알고리즘 with C++]

12.4 크루스칼 알고리즘

이번에는 크루스칼 알고리즘으로 최소신장트리를 만드는 방법을 알아봅시다.

 

프림 알고리즘은 최적의 정점을 선택하여 최소신장트리를 만드는 방법입니다. 반면 크루스칼 알고리즘은 최적의 간선을 선택하여 최소신장트리를 만드는 방법입니다.

 

크루스칼 알고리즘

선택한 간선 0으로 설정

원본 그래프의 간선 집합을 복제

복제한 간선 집합을 비중 순으로 정렬

반복(선택한 간선 개수가 graph의 정점 개수-1 보다 작다면)

    조건(탐욕스런 간선을 선택이 실패

        반복문 탈출

    아니면

        선택한 간선 개수 1 증가

 

최적의 간선은 비중이 작은 간선 중에 선택합니다. 그런데 선택한 간선을 현재까지 만들고 있는 그래프(최소신장트리)에 추가하였을 때 사이클이 발생하지 말아야 합니다. 이를 효과적으로 구현하기 위해 원본 그래프의 간선 집합을 복제하여 간선의 비중 순으로 정렬하는 것을 초기에 수행합니다.

 

 

프림 알고리즘은 문제를 해결해가는 과정을 보면 최소신장트리의 범위를 넓혀가는 형태입니다. 이에 알고리즘 초기에 그래프(최소신장트리)에 정점과 간선을 추가하였습니다. 하지만 크루스칼 알고리즘은 간선을 선택하는 원리로 진행하기에 연결이 끊긴 그래프들이 생깁니다. 이러한 특징을 고려하여 최적 간선 선택 알고리즘을 생각합시다.

 

최적 간선을 선택하기 쉽게 하려고 그래프의 간선을 비중 순으로 정렬하였습니다. 최적 간선은 비중 순으로 정렬한 간선 컬렉션의 간선을 순차적으로 확인하면서 탐욕 조건에 해당하는지 확인합니다. 만약 전체 간선을 조사해도 탐욕 조건에 만족하지 않으면 거짓을 반환하세요.

 

최적 간선 선택 알고리즘

반복(간선 집합에 간선 개수가 0보다 크면 )

   조건(맨 앞의 간선이 탐욕스런 간선일 때 )

       참 반환

거짓 반환

 

간선의 두 정점이 생성한 그래프 컬렉션의 특정 그래프에 포함하고 있다면 해당 간선을 추가하면 사이클이 발생합니다. 따라서 이런 조건에서는 거짓을 반환합니다. 이 외의 간선은 탐욕 조건에 만족하는 간선입니다.

 

간선의 하나의 정점만 포함하고 있는 그래프가 하나 있다면 간선을 해당 그래프에 추가하고 나머지 정점도 포함합니다. 간선의 끝점을 하나 포함하는 그래프가 두 개 있다면 두 개의 그래프를 하나로 통합하고 간선을 추가합니다. 간선의 끝점을 하나도 포함하고 있는 그래프가 없다면 새로운 그래프를 생성하고 간선의 두 끝점과 간선을 생성한 그래프에 추가합니다.

 

첫 번째 간선이 탐욕 조건에 맞족하는지 확인

edge:=간선 집합의 첫 번째 간선, graph_a:=NULL

seek:=그래프 컬렉션의 시작 위치, end:=그래프 컬렉션의 마지막 위치

반복(seek가 end가 아니면, seek 순차이동)

    graph:= seek 위치의 그래프로 설정

    조건(graph에 간선의 두 정점이 있다면)

        간선 집합에서 맨 앞의 간선 제거, 거짓 반환

    조건(graph에 하나의 정점만 포함할 때)

        조건(grah_a is NULL)

            a:=seek 위치의 그래프로 설정

        아니면

            반복문 탈출

조건(graph_a is NULL)

    graph_a:= 그래프 생성, graphs 컬렉션에 graph_a 를 추가

아니라면

    조건(seek is not end)

        graph_a

2016/04/14 - 12.4.1 크루스칼 알고리즘 구현 [디딤돌 자료구조와 알고리즘 with C++]

2016/04/14 - 12.4.2 크루스칼 알고리즘 소스 코드 [디딤돌 자료구조와 알고리즘 with C++]