12.3.1 프림 알고리즘 구현

이제 프림 알고리즘을 구체적으로 구현해 보아요.

앞에서 작성했던 그래프 부분까지는 매우 비슷합니다. 먼저 간선을 정의합시다.

두 개의 정점과 간선의 비용이 필요하죠.

생성자는 두 개의 정점과 간선의 비용을 입력 인자로 받습니다.

특정 정점이 존재하는지 판별하는 메서드를 제공하세요.

두 개의 정점을 잇는 간선인지 판별하는 메서드를 제공하세요.

하나의 정점을 입력 인자로 받아 다른 나머지 정점을 구하는 메서드를 제공하세요.

간선의 정보를 출력하는 메서드를 제공하세요.

간선의 비용과 두 개의 정점에 접근하는 메서드를 제공하세요.

간선 생성자에서는 입력 인자로 받은 값으로 멤버 필드를 설정하세요.

특정 정점이 존재하는지 판별하는 메서드와 두 개의 정점을 잇는 간선인지 판별하는 메서드를 구현하세요.

한 정점을 입력 인자로 받아 나머지 정점을 반환하는 메서드를 구현하세요.

자신의 정보를 출력하는 메서드를 구현하세요.

간선의 비용과 두 개의 정점에 접근하는 메서드를 구현하세요.

 

이번에는 그래프를 구현합시다. 

먼저 정점 집합과 간선 집합을 vector를 이용하여 형식을 지정하세요.

그래프 클래스도 앞에서 작성했던 것들과 매우 비슷합니다.

멤버 필드와 정점과 간선의 집합이 필요하겠죠.

정점과 간선을 추가하고 존재하는지 판별하는 메서드와 이웃들의 정보를 출력하는 메서드도 제공합시다.

정점의 개수를 구하는 메서드를 제공하세요. 프림 알고리즘에서는 원본 그래프에 있는 정점을 선택해 나가는 알고리즘으로 모든 정점을 선택할 때까지 반복합니다. 따라서 그래프의 정점 개수를 알 수 있어야겠죠.

간선 집합을 구하는 메서드를 제공하세요.

첫 번째 정점을 구하는 메서드를 제공하세요.

그래프 소멸자에서는 내부에서 생성한 간선들을 해제해 주어야 합니다.

정점을 추가하는 메서드를 구현하세요. 앞에서 작성했던 부분과 차이가 없습니다.

정점이 존재하는 메서드도 구현하세요. 앞에서 작성했던 부분과 차이가 없습니다.

간선을 추가하는 메서드도 구현하세요. 앞에서 작성했던 부분과 차이가 없습니다.

두 개의 정점이 존재할 때만 추가합니다.

두 개의 정점을 잇는 간선이 없을 때만 추가합니다.

간선의 비용 순으로 배치하기 위한 로직입니다.

추가할 간선의 비용보다 크거나 같은 간선의 위치를 찾습니다.

탐색한 위치에 새로운 간선을 생성하여 추가하세요.

두 개의 정점을 포함하는 간선이 있는지 판별하는 메서드를 구현하세요. 앞에서 작성했던 부분과 차이가 없습니다.

이웃 정점들을 출력하는 메서드를 구현하세요. 앞에서 작성했던 부분과 차이가 없습니다.

정점의 개수를 구하는 메서드를 구현하세요.

간선 집합을 구하는 메서드를 구현하세요.

첫 번째 정점을 구하는 메서드를 구현하세요.

정점이 하나도 없으면 빈 문자열을 반환하세요.

 

이제 프림 알고리즘을 구현합시다.

멤버로 원본 그래프가 필요합니다. 편의상 원본 그래프의 간선 집합도 멤버로 기억하는 멤버도 추가합시다.

생성자에서 원본 그래프를 입력 인자로 받습니다.

최소 신장 트리를 만드는 메서드를 제공해야죠.

프림 알고리즘에서는 탐욕적인 방법으로 정점을 선택하면서 최소 신장 트리를 만듭니다. 만약 그래프의 고립 영역이 있으면 탐욕적인 방법으로 모든 정점을 선택하지 못할 수 있습니다. 탐욕적인 방법으로 정점을 선택하여 최소 신장 트리에 추가하는 메서드를 추가하세요. 반환 형식은 선택 여부를 반환하게 합시다.

현재 간선에 끝점 중에 탐욕적인 정점인지 판별하고 정점 이름을 반환하는 메서드를 제공하세요.

생성자에서는 원본 그래프를 입력받아 멤버에 설정하세요.

최소 신장 트리를 만드는 메서드를 구현합시다.

비어있는 최소 신장 트리를 생성하세요.

원본 그래프의 첫번째 정점을 선택하세요. 프림 알고리즘에서는 처음 선택하는 정점은 무엇을 선택하든 관계 없습니다.

편의를 위해 원본 그래프의 간선 집합과 정점 개수를 구하세요.

탐욕 알고리즘에서는 최소 신장 트리에 탐욕스런 방법으로 정점을 하나씩 추가합니다. 물론 원본 그래프의 정점 개수만큼 선택해야겠죠.

만약 원본 그래프에 고립 상태인 영역이 있으면 탐욕스런 방법으로 모든 정점을 선택할 수가 없습니다. 따라서 탐욕스런 방법으로 정점을 선택하였는지 판별하는 부분이 필요합니다.

만약 반복문을 탈출한 상태에서 최소 신장 트리의 정점 개수가 원본 그래프의 정점 개수보다 작으면 고립 상태의 영역이 있어서 최소 신장 트리를 만들 수 없는 것입니다. 이 때 메시지를 출력하고 0을 반환하세요.

이 부분에 도달했다면 최소 신장 트리에 정점 개수가 원본 그래프의 정점 개수와 같을 때입니다. 생성한 최소 신장 트리를 반환하세요.

탐욕스런 방법으로 정점을 선택하여 최소 신장 트리에 추가하는 메서드를 구현합시다.

원본 그래프의 정점을 순회하면서 탐욕스런 방법에 적합한 정점을 찾습니다. 여기에서 간선은 비용 순으로 배치한 상태이므로 탐욕스런 방법으로 발견한 첫 번째 정점만 찾아 추가합니다.

현재 간선에 탐욕스런 정점이 있는지 판별하는 메서드를 호출하세요.

만약 탐욕스런 정점이면 정보를 출력하세요.

그리고 선택한 정점을 추가하고 간선도 추가하세요.

이제 특정 간선의 끝 점중에 최소 신장 트리에 탐욕스런 방법으로 선택할 정점이 있는지 판별하는 메서드를 구현합시다.

먼저 간선의 두 개의 끝점을 구하세요.

만약 하나의 정점만 포함하고 있다면 나머지 정점이 탐욕스런 방법으로 선택할 정점입니다. 만약 하나도 포함하고 있지 않다면 현재까지의 최소 신장 트리의 정정들 중에 갈 수 있는 경로가 없는 것이라 선택할 정점이 없습니다. 그리고 둘 다 포함하고 있다면 사이클이 만들어져서 선택하지 말아야 합니다.

둘 다 포함하고 있을 때이므로 빈 문자열을 반환하세요.

vtx1은 포함하고 있고 vtx2가 없으므로 vtx2를 선택합니다.

vtx1은 없고 vtx2만 있으므로 vt1을 선택합니다.

둘 다 없을 때이므로 빈 문자열을 반환하세요.

 이제 프림 알고리즘을 이용하여 최소 신장 트리를 만드는 예제 코드르 작성합시다.

그래프

그래프를 생성하세요.

테스트에 사용할 그래프에 정점을 추가하세요.

간선도 추가하세요.

원본 그래프의 정보를 출력하세요.

프림 알고리즘을 생성하세요.

최소 신장 트리를 만들 것을 요청합니다.

반환받은 최소 신장 트리가 존재하면 성공을 출력하고 최소 신장 트리 정보를 출력하세요.

▷ 실행 결과

이상으로 프림 알고리즘을 이용하여 최소 신장 트리를 만드는 코드를 구현하였습니다. 여기에서 작성한 프림 알고리즘은 몇 가지 개선할 사항이 있습니다.

제일 먼저 개선할 사항은 탐욕스런 정점을 선택하는 과정에서 특정 간선의 두 개의 정점이 현재까지 만든 최소 신장 트리에 포함하고 있다면 해당 간선은 다음 선택 과정에서는 확인할 필요가 없습니다. 따라서 이럴 때 간선 집합에서 제거한다면 보다 나은 성능을 발휘할 수 있습니다.

이 외에도 몇 가지 개선 사항이 있습니다. 여러분께서 보다 나은 탐욕 알고리즘을 구현하고자 한다면 무엇을 개선하면 좋을 지 고민하시고 수정해 보세요.