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

이제 크루스칼 알고리즘을 구현하기로 해요. 이 책에서는 크루스칼 알고리즘을 구현할 때 그래프를 인접행렬로 표현하지 않고 정점과 간선의 집합체로 정의할게요. 인접행렬로 표현한 소스 코드는 인터넷이나 다른 레퍼런스에 많이 나와있으니 이를 참고하세요.

 

그래프는 프림 알고리즘을 구현하면서 만든 것을 사용하세요.

생성할 그래프를 보관할 컬렉션을 생성합니다.

원본 그래프의 간선 컬렉션을 기반으로 정렬 상태의 간선 컬렉션을 생성합니다. 이 부분은 별도의 함수로 작성합시다.

크루스칼 알고리즘은 간선을 정정 개수 -1 개 만큼을 선택합니다.

반복해서 간선을 선택합니다. 간선을 선택하는 부분도 별도의 함수로 작성합시다.

정상적으로 진행하면 그래프를 보관하는 컬렉션에 최소신장트리 하나만 남습니다. 맨 앞의 그래프를 반환합니다.

입력 인자로 전달받은 간선 컬렉션의 간선을 기반으로 정렬 상태의 간선 컬렉션을 생성하는 함수를 작성합시다.

원본 컬렉션의 시작 위치와 끝 위치를 구합니다.

순차적으로 위치를 이동하여 간선을 참조합니다.

컬렉션에 간선의 비중으로 위치를 찾아 추가합니다. 이 부분은 별도의 함수로 작성합시다.

컬렉션에 간선의 비중으로 위치를 찾는 함수를 작성합시다.

컬렉션의 시작 위치와 끝 위치를 구합니다.

순차적으로 이동하며 간선을 참조합니다.

새로운 간선의 비중이 참조한 간선의 비중보다 작다면 위치를 찾은 것이므로 루프를 탈출합니다.

찾은 위치에 간선을 추가합니다.

이제 간선을 선택하는 함수를 작성합시다.

간선 컬렉션의 간선을 순차적으로 참조합니다.

참조한 간선이 탐욕 간선이면 이를 추가한 후에 함수를 종료합니다. 탐욕 간선인지 확인하여 추가하는 부분은 별도의 함수로 작성합시다.

그렇지 않다면 해당 위치의 간선을 제거합니다. 이 때 참조할 간선의 인덱스는 증가하지 말아야 합니다. for 문에서 증가하므로 여기서 미리 감소합시다.

탐욕스런 간선인지 확인하여 맞다면 그래프에 추가하는 함수를 작성합시다.

순차적으로 이동하면서 컬렉션에 보관한 그래프를 참조할 변수를 선언합니다.

새로 생성하거나 두 개의 그래프를 통합할 그래프를 참조할 변수를 선언합니다.

간선의 끝 점이 하나 포함한 그래프를 처음 만날 때 그 위치를 기억할 변수를 선언합니다.

생성한 그래프를 보관하는 컬렉션의 시작 위치와 끝 위치를 구합니다.

순차적으로 이동하면서 컬렉션에 보관한 그래프를 참조합니다.

만약 간선의 첫 번째 끝점이 포함하는지 확인합니다.

만약 간선의 나머지 끝점도 포함하면 사이클이 발생하여 탐욕스런 간선이 아닙니다.

만약 간선의 나머지 끝점을 포함하지 않고 처음 발견한 것이라면 이 위치를 기억합니다.

그렇지 않다면 이전에 발견한 그래프와 현재 위치의 그래프는 병합할 것입니다. 여기에서는 현재 위치의 그래프를 그래프 컬렉션에서 제거하고 루프를 탈출한 후에 병합합시다.

여기에서도 나머지 끝점을 포함하고 있을 때의 처리는 같습니다.

만약 a가 0이면 간선의 끝점을 하나라도 포함하는 그래프가 없는 것입니다.  이 때는 새로운 그래프를 생성하여 그래프 컬렉션에 추가합니다.

그렇지 않고 루프를 중간에 탈출하였다면 두 개의 그래프를 하나로 통합합니다. 이 부분의 별도의 함수로 작성합시다.

크루스칼 알고리즘에서 간선을 추가하는 과정을 보여주기 위해 현재의 간선 정보를 출력합시다.

그래프에 간선의 두 끝점과 간선을 추가합니다. 각 함수에서는 이미 있을 때 필터링하도록 만들었습니다.

두 개의 그래프를 하나로 통합하는 함수를 작성합시다.

graph2의 정점 컬렉션의 시작 위치에서 끝 위치까지 이동하며 graph1에 정점을 추가합니다.

graph2의 간선 컬렉션의 시작 위치에서 끝 위치까지 이동하며 graph1에 간선을 추가합니다.

이제 구체적으로 구현합시다. 콘솔 응용 프로젝트를 생성하고 프림 알고리즘에서 사용한 Array.c와 Array.h, Graph.c, Graph.h 파일을 프로젝트 폴더에 복사하고 프로젝트에 추가하세요. 그리고 프림 알고리즘을 구현할 Program.c 파일을 추가합시다.

진입점 main 함수에서는 시뮬레이션에 사용할 그래프를 생성하고 크루스칼 알고리즘으로 최소신장트리를 생성하고 생성한 최소신장트리를 보여줍시다.

시뮬레이션에 사용할 그래프를 생성하는 부분은 프림 알고리즘에서 사용한 것과 같습니다.

크루스칼 알고리즘
[그림 7.3] 크루스칼 알고리즘
▷ 실행 결과


학습에 도움이 되시면 ebook을 구입(판매가 3000원, ebook)하여 소장하시면 감사하겠습니다.