[Java] Prim 알고리즘

Kruskal과 같이 MST를 찾는 알고리즘입니다.

[Java] Kruskal 알고리즘

Prim을 잘 익혀두시면 최단거리를 구하는 Dijkstra 알고리즘을 학습하실 때 큰 도움이 됩니다!

[Java] Dijkstra 알고리즘

 

(설명을 잘 못해서 코드를 보시는 게 빠를 수 있습니다.... ㅠ)

1. 정점 정보를 저장할 객체인 Edge 클래스(정점번호와 해당 정점까지의 가중치를 저장)를 만들고 해당 정점에 연결되는 인접한 정점만의 정보를 담기 위해 ArrayList를 사용하여 배열(edge = new ArrayList[V + 1])을 만들어 줍니다. (ArrayList를 사용 안 하고 인접 행렬을 사용해도 됩니다!)

 

이때, 그래프는 방향이 없으므로 양쪽으로 연결돼있음을 주의하셔야 합니다!

 

ex) 

예를 들어,위 이미지와 같이

1번 정점에는 2번, 3번 정점이

2번 정점에는 1번 정점이

3번 정점에는 1번 정점이 연결되어있습니다.

 

이를 위에서 ArrayList를 사용한 인접 리스트로 표현하면

edge[1] = 2번의 edge 정보, 3의 edge 정보

edge[2] = 1번의 edge 정보

edge[3] = 1번의 edge 정보

가 저장됩니다.

 

이를 인접 행렬로 표현하면

정점	1	2	3
1	0	2	5
2	2	0	0
3	0	0	5

와 같이 됩니다.

 

2. MST를 구하기 위해 방문 체크를 위한 visted 배열과 최소거리를 저장할 minEdge 배열을 정점의 개수만큼 크기를 할당시켜줍니다. (이때, 정점이 1부터 시작하는 경우 인덱스와 맞추어주기 위해 +1을 했습니다.)

 

3. MST는 모든 정점을 연결했을 때 최소거리를 구하는 것이므로 minEdge 배열의 모든 인덱스를 큰 수로 초기화해줍니다. (자바의 경우, Arrays.fill(minEdge, Integer.MAX_VALUE); )

 

4. 시작점의 minEdge를 0으로 바꾸어줍니다. (아무 점이나 선택해도 되지만 1번 정점부터 시작하도록 했습니다.)

 

5. 모든 정점을 연결해야 하므로 반복문을 정점의 개수만큼 돌면서 MST를 찾는 과정을 반복합니다

   5-1. minEdge를 조사하면서 방문하지 않았으면서 가장 짧은 거리와 해당 인덱스를 저장합니다.

   (이 과정에서 힙을 사용하면 더욱 빠르게 처리가 가능합니다.)

   5-2. 가장 짧은 거리를 갖고 있는 정점을 방문처리를 하고 MST 값에 해당 거리를 추가합니다.

   5-3. 가장 짧은 거리를 갖고있는 정점과 연결되어있는 모든 정점을 조사합니다.

         5-3-1. 조사를 하면서 방문하지 않았고 현재 가장 짧은 거리를 갖고있는 정점과 연결되어있는 해당 정점의 minEdge 값보다 현재 정점에서 해당 정점으로 가는 가중치가 더 작다면 minEdge의 값을 가중치로 업데이트하여 최소 거리를 만듭니다.

         (이때, 인접 행렬의 경우 추가적으로 현재 정점과 해당 정점이 연결돼있는지 여부를 확인해야 하므로 if문에 만약 인접 행렬의 이름이 adj라면 adj[cur][j] > 0이라는 조건을 추가해야 합니다.)

         5-3-2. 5번을 이어서 반복합니다.

 

위 과정을 거치면 MST를 구할 수 있습니다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Prim {
	public static class Edge {
		int vertex, weight;
		
		public Edge(int vertex, int weight) {
			this.vertex = vertex;
			this.weight = weight;
		}
	}
	
	public static int V, E, answer;
	public static boolean[] visited;
	public static int[] minEdge;
	public static List<Edge>[] edge;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		edge = new ArrayList[V + 1];
		
		for (int i = 0; i <= V; ++i) {
			edge[i] = new ArrayList<Edge>();
		}
		
		for (int i = 0; i < E; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			// 양방향으로 연결되있음을 주의
			edge[from].add(new Edge(to, weight));
			edge[to].add(new Edge(from, weight));
		}
		
		visited = new boolean[V + 1];
		minEdge = new int[V + 1];
		
		Arrays.fill(minEdge, Integer.MAX_VALUE);
		minEdge[1] = 0;
		answer = 0;
		
		for (int i = 1; i <= V; ++i) {
			int min = Integer.MAX_VALUE;
			int cur = 0;
			
			for (int j = 1; j <= V; ++j) {
				if (!visited[j] && min > minEdge[j]) {
					min = minEdge[j];
					cur = j;
				}
			}
			
			visited[cur] = true;
			answer += min;
			
			for (int j = 0; j < edge[cur].size(); ++j) {
				Edge e = edge[cur].get(j);
				
				if (!visited[e.vertex] && minEdge[e.vertex] > e.weight) {
					minEdge[e.vertex] = e.weight;
				}
			}
		}
		
		System.out.println(answer);
	}
}