[C언어 알고리즘] 7.4 크루스칼(Kruskal) 알고리즘(최소신장트리 알고리즘)

7.4 크루스칼(Kruskal) 알고리즘(최소신장트리 알고리즘)

---

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

 

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

 

크루스칼 알고리즘(graph:원본 그래프)

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

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

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

    최적의 간선을 선택

 

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

[그림 7.3] 크루스칼 알고리즘

 

 

 

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

 

 최적 간선을 선택하기 쉽게 하려고 그래프의 간선을 비중 순으로 정렬하였습니다. 최적 간선은 비중 순으로 정렬한 간선 컬렉션의 간선을 순차적으로 확인하면서 탐욕 조건에 해당하는지 확인하여 그래프에 추가하고 그렇지 않다면 간선 컬렉션에서 간선을 제거합니다.

 

최적 간선 선택 알고리즘(graphs:생성한 그래프 컬렉션, std_edges:정렬 상태의 간선 집합)

반복(std_edges 컬렉션의 각 edge를 참조)

   조건(탐욕확인(graphs,참조한 edge)Is True)

   그렇지 않다면 std_edges 컬렉션에서 참조한 edge 제거

 

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

 

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

 

탐욕확인(graphs:생성한 그래프 컬렉션, edge:간선)

graph:=NULL

a:=NULL

seek:=그래프 컬렉션의 시작 위치

end:=그래프 컬렉션의 마지막 위치

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

    graph:= seek

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

    조건(graph에 하나의 정점만 포함하고 a is NULL)

        a:=seek

    아니면        반복문 탈출

조건(grapha is NULL)

    graph2:= 그래프 생성

    graphs 컬렉션에 graph2 를 추가

아니라면

    graph2:= graph

    조건(seek is not end)

        graph2에 graph의 정점과 간선을 추가 /*두 개의 그래프 통합*/

graph2에 edge에 있는 두 정점을 추가

graph2에 edge 추가

참 반환

 

---

[C언어 알고리즘] 7.4.1 크루스칼 알고리즘 구현

[C언어 알고리즘] 7.4.2 크루스칼 알고리즘 소스 코드