8.4.1크루스칼 알고리즘 구현

이제 크루스칼 알고리즘을 구현하기로 해요. 그래프는 프림 알고리즘을 구현하면서 만든 것을 사용하세요.

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

만약 a가 0이면 간선의 끝점을 하나라도 포함하는 그래프가 없는 것입니다.

이 때는 새로운 그래프를 생성하여 그래프 컬렉션에 추가합니다.

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

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

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

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

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

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