[자료구조] 프림알고리즘

개념

하나의 정점에 연결된 간선들 중에 가중치가 가장 작은 간선을 하나씩 선택하면서❓최소신장트리(MST)를 만들어 가는 알고리즘

• 정점 중심

• 정점보다 간선이 많을때 좋다.

• 알고리즘 순서
  1. 임의의 정점을 하나 선택해서 시작한다.
  2. 선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점을 선택한다.
     • 배열, 우선순위큐를 사용해서 간선 비용의 최소값을 관리할 수 있다.
  3. 모든 정점이 선택될 때까지 1,2과정을 반복한다.
• 서로소인 2개의 집합으로 정보 유지
  • 트리정점들: MST를 만들기 위해 선택된 정점들
  • 비트리 정점들: 선택되지 않은 정점들

  ⇒ boolean형 visited[]배열로 관리 가능: true이면 선택 / false이면 비선택

최소신장트리(MST) 무향 가중치 그래프에서 신장 트리의 가중치 합이 최소인 신장트리

구현 코드

• 백준 1197번을 기준으로 작성함 정점 개수, 간선 개수, 간선 정보를 입력받아 그래프의 최소신장트리를 만드는 코드

간선의 최소 비용을 관리하기 위한 배열, 우선순위큐로 분류하였다.

그래프 구현은 이와 상관없이 인접행렬, 인접리스트, 간선리스트 중 하나로 사용해도 무관하다.

1. Dist[]

---

• 인접행렬로 구현 시 정점의 수가 매우 많으면 메모리초과 나는 경우가 많으므로 필요한 정점만을 저장하는 인접리스트를 자주 사용하자.

인접행렬 + 배열

package 프림알고리즘;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//배열
public class PrimTest {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine().trim());
		int[][] input = new int[N][N]; //인접행렬
		int[] minEdge = new int[N]; //연결할 수 있는 정점중 가중치가 최소인 정점 계속 업데이트
		boolean[] visited = new boolean[N]; //최소신장트리에 포함된 것1, 포함되지 않은 것0 처리
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				input[i][j] = Integer.parseInt(st.nextToken());
			}
			minEdge[i] = Integer.MAX_VALUE; //초기에 최대 비용으로 셋팅
		}//i에서 j노드까지의 비용을 모두 배열에 저장
		
		int minVertex, min, result = 0; //최소 간선비용의 정점 기억, 최소 비용, 최소비용 누적(답)

		//0번 정점을 시작정점으로 한다고 가정
		minEdge[0] = 0; //시작점 최소간선비용은 0
		// 정점 N개를 모두 돌려야하기 때문에 N번 반복, 모든 정점 돌기, 이미 방문한 정점으로 돌아가지x
		for (int c = 0; c < N; c++) {
			min = Integer.MAX_VALUE;
			minVertex = 0;
			//1. 신장트리에 포함되지 않은 정점 중 최소간선비용의 정점 찾기
			//PQ에서는 이부분이 빠지고 PQ로 접목함
			for (int i = 0; i < N; i++) { //정점만큼 모두 돌면서
				if(!visited[i] && min > minEdge[i]) { //신장트리가 아니고 자신의 간선의 비용이 최소인 놈을 찾아서
					min = minEdge[i]; //계속 갱신하고
					minVertex = i; //그때의 정점번호 기억하고
				}
			}
			
			result += min; //신장트리 비용 누적
			visited[minVertex] = true; //신장트리에 포함 시킴
			
			//2. 선택된 최소비용 정점 기준으로 신장트리에 포함되지 않은 다른 정점으로의 비용 계산하여 최소값 갱신
			for(int i=0; i<N; i++) {
				if(!visited[i] && input[minVertex][i] != 0 && minEdge[i] > input[minVertex][i]) {
					minEdge[i] = input[minVertex][i];
				//아직 신장트리에 포함되지 않은 정점, 선택된 정점에서 i로 인접
				//현재 i의 최소비용보다 로직에서 들고있는 minVertext에서 i까지의 비용이 더 적다면
				//업데이트한다.
				}
			}
			System.out.println(result);
		}
	}
}

2. 우선순위큐

---

자료구조 ❓Heap은 일반적으로 우선순위 큐를 사용해서 구현한다.

Heap 완전이진트리 형태로 관리한다.

• 부모노드 < 자식노드: 최소힙

• 부모노드 > 자식노드: 최대힙 데이터를 추가, 삭제할 때마다 교환을 해서 위 성질을 계속 유지한다. 데이터가 N개 있어도 이진트리이기 때문에 위로 올라가면 반으로 준다. ⇒ 시간복잡도 O(logN) ⇒ 원소가 많을때 유리하다.

• 여기서는 위 코드의 1번 ⇒ 우선순위큐로 변경된다.
• 아래는 연결리스트+우선순위큐코드이다며 인접행렬을 대신 사용해도 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

//프림알고리즘
public class Main {

	static int V, E;
	static int from, to;
	static long weight;
	static ArrayList<Node>[] graph; //간선 정보
	static int Ans; //최소신장트리의 가중치
	static StringTokenizer st;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		graph = new ArrayList[V + 1]; //1번~V번
		
		for(int i=1; i<V+1; i++) {
			graph[i] = new ArrayList<>();
		}
		
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
			from = Integer.parseInt(st.nextToken());
			to = Integer.parseInt(st.nextToken());
			weight = Long.parseLong(st.nextToken());
			graph[from].add(new Node(to, weight));
			graph[to].add(new Node(from, weight));
		}
		
		makeMST();
		System.out.println(Ans);
	}
	
	
	//최소 신장 트리
	private static void makeMST() {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[V+1];
		int now = 1; //1번 정점에서 출발
		visited[1] = true; //방문 표시
		
		//모든 정점 돌아야하니까
		for(int i=1; i<V; i++) {
			 //현재 정점에 있는 간선 정보를 큐에다 넣어줌
			for(Node node : graph[now]) {
				if(!visited[node.num])  //아직 방문하지 않았다면
					pq.offer(node);
				
			}
			//다음으로 갈 정점 찾기
			//큐에 담긴 정점 중 가장 가중치가 작은 정점 고르기
			while(!pq.isEmpty()) {
				Node node = pq.poll();
				if(!visited[node.num]) {
					now = node.num;
					visited[now] = true;
					Ans += node.weight;
					break;
				}
			}
		}
	}

	static public class Node implements Comparable<Node>{
		int num; //연결된 정점
		long weight; //가중치
		
		public Node(int num, long weight) {
			super();
			this.num = num;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return Long.compare(this.weight, o.weight);
		}
	}
}

• ArrayList[] graph 배열이 헷갈려서 그림으로 정리함