PRIM 알고리즘

  최소신장트리를 만드는 두 번째 방법인 PRIM 알고리즘에 대해서 알아보자. (첫 번째 방법으로는 KRUSKAL 알고리즘이 있었다.)

 

1. PRIM 알고리즘 👓

1. 기본 개념

그리디 방식을 이용하여 최소 신장 트리를 찾는 방식
시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 만들어 나가는 방식

2. 동작 방식

1. 그래프에서 하나의 정점을 선택하여 트리를 만든다.
2. 트리와 연결되어 있지만 아직 선택되지 않은 정점들 중에서 간선의 가중치가 가장 낮은 정점을 트리에 포함시킨다.
3. 트리가 N-1의 간선을 가질 때까지 2번을 반복한다.

 

2. 구현 (JAVA) 🤿

  구현 방식으로는 아래의 2가지 방법이 있다.

1. 반복문을 통해 다음 정점을 찾는 방식
2. PriorityQueue를 이용해 다음 정점을 찾는 방식

  위의 예시를 통해 PRIM 알고리즘을 알아보자.('a, b, c, d, e, f, g'는 '0, 1, 2, 3, 4, 5, 6'으로 나타낸다.)
  PRIM 알고리즘을 써야 하는 경우는 대체적으로 간선이 많은 경우이다. 이런 경우에는 행렬의 형식으로 입력이 많이 주어지므로 행렬의 형식으로 입력을 받아보자. 먼저 정점의 개수(vertexNum)를 받고, 그리고 가중치에 해당하는 2차원 행렬을 받는다.

  아래는 입력 정보와 구현 코드이다.

7
0 29 0 0 0 10 0
29 0 16 0 0 0 15
0 16 0 12 0 0 0
0 0 12 0 22 0 18
0 0 0 22 0 27 25
10 0 0 0 27 0 0
0 15 0 18 25 0 0

방법 1 - 반복문을 통해 다음 정점을 찾는 방식

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int vertexNum = Integer.parseInt(st.nextToken());
		int edgeNum = Integer.parseInt(st.nextToken());
		
		// 간선의 가중치를 저장하는 배열
		int[][] adjMatrix = new int[vertexNum][vertexNum];
		// 정점에 방문하기 위해 사용하는 간선의 최소 가중치
		int[] minWeightForVertex = new int[vertexNum];
		boolean[] visited = new boolean[vertexNum];
		
		for (int from = 0; from < vertexNum; from++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int to = 0; to < vertexNum; to++) {
				adjMatrix[from][to] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 아직 탐색을 하면서 최소 가중치를 업데이트 하기 전이므로,
		// 아래와 같이 초기화
		for(int i = 0; i < vertexNum; i++) {
			minWeightForVertex[i] = Integer.MAX_VALUE;
		}

		// 방문한 정점의 개수
		int vertexCount = 0;
		int mstWeight = 0;
		
		// 시작 정점은 아무거나 해도 됨
		int startVertex = 0;
		// 시작 정점에 방문하기 위해서 사용한 간선은 없으므로 
		// 간선의 가중치는 0으로 세팅
		minWeightForVertex[startVertex] = 0;
		
		// 
		for(int i = 0; i < vertexNum; i++) {
			
			// 트리와 연결되어 있지만 아직 선택되지 않은 정점들 중에서 
			// 가장 낮은 간선의 가중치(minWeightForNextVertex)와 
			// 해당 정점(minVertex)을 저장하기 위한 변수
			int minWeightForNextVertex = Integer.MAX_VALUE;
			int minVertex = startVertex;
			
			for(int j = 0; j < vertexNum; j++) {
				if(!visited[j] && minWeightForNextVertex > minWeightForVertex[j]) {
					minWeightForNextVertex = minWeightForVertex[j];
					minVertex = j;
				}
			}
			
			// 트리에 정점을 추가하는 과정
			visited[minVertex] = true;
			mstWeight += minWeightForNextVertex;
			
			// (정점 - 1)개의 간선이 생긴 경우
			if(++vertexCount == vertexNum) {
				break;
			}
			
			// 정점이 아직 트리에 포함되지 않았고
			// 간선이 존재하는 경우
			// 해당 정점으로 갈 수 있는 최소 가중치의 간선을 선택하는 과정
			for(int j = 0; j < vertexNum; j++) {
				if(!visited[j] && adjMatrix[minVertex][j] != 0
						&& minWeightForVertex[j] > adjMatrix[minVertex][j]) {
					minWeightForVertex[j] = adjMatrix[minVertex][j];
				}
			}
		}
		
		System.out.println(mstWeight);
	}
}

 

방법 2 - PriorityQueue를 이용해 다음 정점을 찾는 방식

public class Main {
	
	private static class Vertex implements Comparable<Vertex> {
		public int idx;
		public int weight;
		
		public Vertex(int idx, int weight) {
			super();
			this.idx = idx;
			this.weight = weight;
		}

		@Override
		public int compareTo(Vertex o) {
			return Integer.compare(this.weight, o.weight);
		}
		
		
	}
	

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int vertexNum = Integer.parseInt(st.nextToken());
		
		// 간선의 가중치를 저장하는 배열
		int[][] adjMatrix = new int[vertexNum][vertexNum];
		// 정점에 방문하기 위해 사용하는 간선의 최소 가중치
		int[] minWeightForVertex = new int[vertexNum];
		boolean[] visited = new boolean[vertexNum];
		
		for (int from = 0; from < vertexNum; from++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int to = 0; to < vertexNum; to++) {
				adjMatrix[from][to] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 아직 탐색을 하면서 최소 가중치를 업데이트 하기 전이므로,
		// 아래와 같이 초기화
		for(int i = 0; i < vertexNum; i++) {
			minWeightForVertex[i] = Integer.MAX_VALUE;
		}

		// PriorityQueue
		Queue<Vertex> queue = new PriorityQueue<>();
		// 시작 정점은 아무거나 해도 됨
		int startVertex = 0;
		// 시작 정점에 방문하기 위해서 사용한 간선은 없으므로 
		// 간선의 가중치는 0으로 세팅
		queue.offer(new Vertex(startVertex, 0));
		
		// 방문한 정점의 개수
		int vertexCount = 0;
		int mstWeight = 0;
		
		while(!queue.isEmpty()) {
			
			// 다음 정점의 후보들 중 간선의 가중치가 가장 작은 정점을 선택
			Vertex minVertex = queue.poll();
			
			// 이미 트리에 포함된 경우
			if(visited[minVertex.idx]) {
				continue;
			}

			// 트리에 정점을 추가하는 과정
			visited[minVertex.idx] = true;
			mstWeight += minVertex.weight;
			
			// (정점 - 1)개의 간선이 생긴 경우
			if(++vertexCount == vertexNum) {
				break;
			}
			
			// 정점이 아직 트리에 포함되지 않았고
			// 간선이 존재하는 경우
			// 해당 정점으로 갈 수 있는 최소 가중치의 간선을 선택하는 과정
			for(int i = 0; i < vertexNum; i++) {
				if(!visited[i] && adjMatrix[minVertex.idx][i] != 0
						&& minWeightForVertex[i] > adjMatrix[minVertex.idx][i]) {
					minWeightForVertex[i] = adjMatrix[minVertex.idx][i];
					queue.offer(new Vertex(i, adjMatrix[minVertex.idx][i]));
				}
			}
		}
		
		System.out.println(mstWeight);
	}
}

  코드를 통해 알 수 있는 것처럼 KRUSKAL에 비해 상당히 복잡하다. 간선의 개수가 작으면 KRUSKAL 알고리즘을 사용하도록 하자.

 

3. 시간복잡도 🥽

  '방법 1 - 반복문을 통해 다음 정점을 찾는 방식'에서는 O(V ^ 2)의 시간복잡도를 가진다.

  '방법 2 - PriorityQueue를 이용해 다음 정점을 찾는 방식'에서는 O((E + V) log V)만큼의 시간복잡도를 가진다. (자바에서는 우선순위 큐가 피보나치 힙이 아닌 이진 힙 형태이기 때문이다.) (만약 피보나치 힙이면 O(E + VlogV)를 가지게 된다.)

(시간복잡도 관련해서는 해당 글을 참고하기 바란다.)

  앞에서 계속해서 언급한 것처럼 간선의 개수에 따라서 KRUSKAL 알고리즘과 PRIM 알고리즘을 적절하게 선택해야 한다.