[Java] 프림 알고리즘 & 2가지 구현방법 (반복문과 인접행렬, 우선순위큐와 인접리스트)
프림 알고리즘을 적용하여 최소 가중치의 합을 찾아보자.
- 표의 첫 행: 해당 노드 번호
- p[V] : 해당 노드가 어떤 노드로부터 오는지. 즉, 부모 노드번호를 저장한다.
- keys[V] : 해당 노드가 연결된 간선 중 최소 가중치
- visited[V] : 해당 노드가 방문했는지 여부
처음 keys 모든 값은 ∞로 세팅한다.
예시는 노드6번부터 출발한다.
6번이 시작점이므로 6번의 parent는 없고, 이제까지의 간선가중치도 없다. 따라서 p는 -1, keys는 0
p[6] = -1
keys[6] = 0
visited[6] = true (방문처리는 파란색으로 표시)
1. 6번부터 출발
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| p | -1 | ||||||
| keys | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 |
2. 인접 노드들의 가중치 갱신
- 6번은 0번(51), 2번(25), 4번(51)과 연결되어있다.
- 연결된 노드들이 현재 가지고 있는(∞) 값 보다 6번과의 간선이 가진 가중치 값이 더 작기 때문에 갱신해주자.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| p | 6 | 6 | 6 | -1 | |||
| keys | 51 | ∞ | 25 | ∞ | 51 | ∞ | 0 |
3. 최소 가중치를 가진 노드 선택 (2번)
- 선택되지 않은 노드들 중 2번(25)가 현재 keys들의 값 중 가장 작기 때문에 2번이 선택된다.
- 2번과 연결된 노드들 0번(31), 1번(21), 4번(46), 6번(25)들이 원래 가진 keys값들 보다 작으면 갱신하자.
- 0번(31), 1번(21), 4번(46) 갱신
- 위에서 6번은 이미 visited되었기 때문에 처리되지 않는다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| p | 2 | 2 | 6 | 2 | -1 | ||
| keys | 31 | 21 | 25 | ∞ | 46 | ∞ | 0 |
3. 최소 가중치 노드 선택 (1번)
- 선택되지 않은 노드들 중 최소 가중치 가진 1번(21)이 선택된다.
- 1번과 연결된 노드 중 아직 방문처리 되지 않은 0번(32)의 갱신여부를 점검하자.
- 현재 가진 값(31) < 1번과 연결된 가중치의 값(32) 더 크니깐 갱신하지 않는다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| p | 2 | 2 | 6 | 2 | -1 | ||
| keys | 31 | 21 | 25 | ∞ | 46 | ∞ | 0 |
4. 최소 가중치 노드 선택 (0번)
- 선택되지 않은 노드들 0번(31), 3번(∞), 4번(46), 5번(∞) 중 최소 가중치 가진 0번(31)이 선택된다.
- 0번과 연결된 노드 중 아직 방문처리 되지 않은 5번(60)의 갱신여부를 점검하자.
- ∞ > 60, 0번과 연결 했을 때 더 작으므로 갱신
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| p | 2 | 2 | 6 | 2 | 0 | -1 | |
| keys | 31 | 21 | 25 | ∞ | 46 | 60 | 0 |
5. 최소 가중치 노드 선택 (4번)
- 선택되지 않은 노드들 3번(∞), 4번(26), 5번(60) 중 최소 가중치 가진 4번(46)이 선택된다.
- 4번과 연결된 노드 중 아직 방문처리 되지 않은 3번(34), 5번(40)의 갱신여부를 점검하자.
- ∞ > 34, 60 > 40 이므로 둘 다 갱신
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| p | 2 | 2 | 6 | 4 | 2 | 4 | -1 |
| keys | 31 | 21 | 25 | 34 | 46 | 40 | 0 |
5. 최소 가중치 노드 선택 (3번) => 최종!
- 선택되지 않은 노드 3번(35), 5번(40) 중 최소가중치인 3번을 선택한다.
- 5번을 제외한 모든 노드들이 visited 상태이므로 5번(18)과의 갱신여부만 점검해주면 된다.
- 마지막으로 선택되지 않은 5번 노드의 경우, 5번을 제외한 모든 노드들이 선택(visited)됐으므로 갱신할 것이 더이상 없다. 따라서 여기서 멈추어도 된다(즉, 코드 상에서 반복문을 정점의 개수인 V만큼 아닌 V-1개만큼 돌려도 같은 결과)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| p | 2 | 2 | 6 | 4 | 2 | 3 | -1 |
| keys | 31 | 21 | 25 | 34 | 46 | 18 | 0 |
따라서 MST 비용의 합은 31+21+25+34+46+18 = 175와 같다.
이를 코드로 구현하면 아래와 같다!
(1) 반복문 & 인접행렬을 이용한 프림 구현
/*
* 프림 알고리즘 -> '정점' 선택해 MST 만들어 가기
* (1) 임의 정점 하나 선택
* - 아무거나 선택해도 되는 이유? 결과적으로 모든 정점을 선택하기 때문
* (2) 선택 정점과 인접 정점들 중 최소비용 간선인 정점을 선택
* (3) 모든 정점 선택할 때까지 (1),(2) 반복
*
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(input);
int V = sc.nextInt(); // V : 정점의 개수 정점은 0번부터 시작한다
int E = sc.nextInt(); // E : 간선의 개수
// 간선의 정보를 저장한다
// 인접행렬을 사용한다
int[][] adjArr = new int[V][V];
for (int i = 0; i < E; i++) {
int st = sc.nextInt(); // 시작 정점
int ed = sc.nextInt(); // 도착 정점
int w = sc.nextInt(); // 가중치
adjArr[st][ed] = w;
adjArr[ed][st] = w;
}
boolean[] visited = new boolean[V]; // 정점을 방문했는지
int[] p = new int[V]; // 정점이 어디서 왔는지 즉, 부모를 저장
int[] keys = new int[V]; // 정점에 연결된 간선 중 최소 가중치
// keys 들을 무한대의 값으로 갱신해준다
Arrays.fill(keys, Integer.MAX_VALUE);
// 임의 정점을 선택해서 돌린다. 0번부터 시작한다
p[0] = -1; // 0번이 시작점이다, 이미 0은 인덱스로 사용하기 때문에 다른 정점의 부모일 수도 있다. 따라서 -1로 초기화한다
keys[0] = 0; // 모든 정점의 key들은 무한대이므로 시작정점의 key는 0으로 초기화 해둠
int minCost = 0; // 최소값, 인덱스, MST 최소비용의 합
// 프림 만들기
// for는 V개수만큼 돌던 (V-1)개까지 돌던 차이 없음
for (int i = 0; i < V - 1; i++) {
int min = Integer.MAX_VALUE;
int idx = -1;
// 아직 안 뽑힌 정점들 중 가장 작은 값을 뽑는다
for (int j = 0; j < V; j++) {
if (!visited[j] && keys[j] < min) {
min = keys[j];
idx = j;
}
} // 이 for문이 끝나면 idx엔 이번에 선택한 정점이 들어있다
visited[idx] = true; // idx번째 정점을 선택했다
// 선택한 정점과 연결된 간선들을 갱신할 수 있으면 갱신하자
for (int j = 0; j < V; j++) {
// 방문하지 않았고 && 간선이 있으면 갱신
// 단, 방문한 친구는 이미 최소값이기에 갱신이 일어나지 않는다 (사실 방문은 체크 안해도 됨)
if (!visited[j] && adjArr[idx][j] != 0 && keys[j] > adjArr[idx][j]) {
keys[j] = adjArr[idx][j];
p[j] = idx;
}
}
} // 프림 만들기
for (int i = 0; i < V; i++) {
minCost += keys[i];
}
System.out.println(minCost);
}
static String input = "7 11\r\n" + "0 1 32\r\n" + "0 2 31\r\n" + "0 5 60\r\n" + "0 6 51\r\n" + "1 2 21\r\n"
+ "2 4 46\r\n" + "2 6 25\r\n" + "3 4 34\r\n" + "3 5 18\r\n" + "4 5 40\r\n" + "4 6 51\r\n" + "";
}
(2) 우선순위 & 인접리스트를 활용한 프림 구현
- (1)에서는 반복문을 통해서 최소가중치를 가지는 노드를 선택해왔다
- 이 역할을 PriorityQueue를 활용하여 최소힙을 구현한다. 큐에서 알아서 최소인 노드를 꺼내도록! (key값이 가장 작은 정점)
/*
* 우선순위 큐를 이용한 프림
* (1) 임의의 정점 하나 선택해 pq 에 넣는다
* (2) pq에서 정점 하나 꺼내기 (pq의해 비용 가장 작은 정점이 나온다)
* (3) pq에서 꺼낸 정점이 이미 visited라면, 다른 거 꺼내기
* (4) pq에서 꺼낸 정점이 아직 visited 아니면, 방문처리 후 정점의 비용 더하기
* (5) 4의 정점과 인접한 정점들 중 방문하지 않은 정점들 pq에 넣기
* (6) pq 빌 때까지 2~5 반복
*
*/
public class Main {
static class Edge implements Comparable<Edge> {
int st, ed, cost;
Edge(int st, int ed, int cost) {
this.st = st;
this.ed = ed;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost; // 최소힙. 루트노드가 가장 작으며, 루트부터 cost 오름차순 정렬
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(input);
int V = sc.nextInt(); // 정점의 개수, 0번부터 시작
int E = sc.nextInt(); // 간선의 개수
// 인접리스트를 이용하여 간선의 정보를 저장한다
List<Edge>[] adjList = new ArrayList[V]; // 리스트들의 배열
for (int i = 0; i < V; i++) {
adjList[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
int st = sc.nextInt();
int ed = sc.nextInt();
int cost = sc.nextInt();
adjList[st].add(new Edge(st, ed, cost));
adjList[ed].add(new Edge(ed, st, cost)); // 무향 그래프이므로
}
boolean[] visited = new boolean[V];
PriorityQueue<Edge> pq = new PriorityQueue<>();
// 시작정점을 하나 뽑는다. 0번 정점부터 시작한다
visited[0] = true;
pq.addAll(adjList[0]); // 0번 정점과 인접한 정점들 모두 넣자
int pick = 1; // 확보한 정점의 개수. 0번 정점을 하나 뽑았다
int minCost = 0; // 최소비용
while (!pq.isEmpty()) {
Edge edge = pq.poll(); // 우선순위큐에서 정렬기준을 정해줬으므로 cost 가장 작은 게 뽑힌다
if (visited[edge.ed]) { // 이미 뽑은 정점이었다면 넘겨
continue;
}
minCost += edge.cost;
pq.addAll(adjList[edge.ed]); // 다음으로 인접한 정점들 모두 넣어주자
visited[edge.ed] = true;
pick++;
}
System.out.println(minCost);
}
static String input = "7 11\r\n" + "0 1 32\r\n" + "0 2 31\r\n" + "0 5 60\r\n" + "0 6 51\r\n" + "1 2 21\r\n"
+ "2 4 46\r\n" + "2 6 25\r\n" + "3 4 34\r\n" + "3 5 18\r\n" + "4 5 40\r\n" + "4 6 51\r\n" + "";
}