[Algorithm] Prim

MST(최소 신장 트리)를 찾는 알고리즘
1. Kruskal(크루스칼)
2. Prim(프림)

MST(최소 신장 트리) 알고리즘
신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘

신장 트리
하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

✔️ 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식

✔️ 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지

• 트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들
• 비트리 정점들(non-tree vertices) - 선택 되지 않은 정점들

✔️ 배열로 구현할 경우 시간 복잡도 O(V^2)

✔️ 최소 힙으로 구현할 경우 시간 복잡도 O(ElogV)

과정

초기 상태로 정점(=노드)는 서로 연결되어 있지 않다. 정점과 연결된 간선을 하나씩 추가하면서 MST를 만든다.

프림 알고리즘은 시작 정점을 정해 우선 순위 큐에 넣는다. 우선 순위 큐에는 (정점, 가중치) 형식으로 저장되며, 첫 시작은 (시작 정점, 0)으로 넣는다.

우선 순위 큐가 빌 때까지 아래를 반복한다.

**1)** 우선 순위 큐에서 하나를 꺼낸다. 꺼낸 정점을 `v`라고 하자. **2)** `v`가 이미 MST에 포함됐다면 **1)**로 돌아간다. 그렇지 않다면 아래를 진행한다. **3)** `v`와 연결된 간선을 모두 살핀다. 간선 `(w, cost)`는 `v`와 정점 `w` 사이 연결된 간선이며 `cost` 가중치를 가진다. 만약 `w`를 방문하지 않았다면 우선순위 큐에 추가한다.

• 예시

  • 왼쪽 표 : 각 정점에 이어진 간선을 저장한 표이다.

  • visit : boolean 배열로 각 정점을 방문했는지 체크한다.정점을 방문 했다면 이미 MST에 포함된 정점이다.

  • 우선 순위 큐 : (정점, 가중치) 형태로 저장된다.

    시작 정점은 1로 정했다. 따라서 우선 순위 큐에 (1, 0)를 저장했다.

    1) 우선 순위 큐에서 하나 꺼낸다. → (1, 0)

    

    정점 1은 아직 방문하지 않았으므로 방문 체크를 한다. 이제 정점 1은 MST에 속해있다.

    이후 정점 1과 연결된 간선을 모두 살핀다.

  • (3, 3) 우선 순위 큐에 추가정점 3은 아직 방문하지 않았다. 따라서 우선 순위 큐에 추가한다.

  • (4, 8) 우선 순위 큐에 추가

  • (2, 10) 우선 순위 큐에 추가

    2) 우선 순위 큐에서 하나 꺼낸다. → (3, 3)

    

    정점 3은 아직 방문하지 않았으므로 방문 체크를 한다. MST에 정점 3과 가중치 3이 추가된다.

    이후 정점 3과 연결된 간선을 모두 살핀다.

  • (1, 3) 우선 순위 큐에 추가 X정점 1은 이미 방문했다. 즉, 이미 MST에 포함된 정점이므로 우선 순위 큐에 추가하지 않는다.

  • (2, 13) 우선 순위 큐에 추가정점 2은 아직 방문하지 않았다. 따라서 우선 순위 큐에 추가한다.

    3) 우선 순위 큐에서 하나 꺼낸다. → (4, 8)

    

    정점 4은 아직 방문하지 않았으므로 방문 체크를 한다. MST에 정점 4와 가중치 8이 추가된다.

    이후 정점 4와 연결된 간선을 모두 살핀다

  • (1, 4) 우선 순위 큐에 추가 X

  • (5, 9) 우선 순위 큐에 추가

    4) 우선 순위 큐에서 하나 꺼낸다. → (8, 14)

    

    정점 5는 아직 방문하지 않았으므로 방문 체크를 한다. MST에 정점 5와 가중치 9가 추가된다.

    이후 정점 5와 연결된 간선을 모두 살핀다

  • (2, 14) 우선 순위 큐에 추가

  • (4, 9) 우선 순위 큐에 추가 X

    5) 우선 순위 큐에서 하나 꺼낸다. → (2, 10)

    

    정점 2는 아직 방문하지 않았으므로 방문 체크를 한다. MST에 정점 2와 가중치 10이 추가된다.

    이후 정점 2와 연결된 간선을 모두 살핀다

  • (1, 10) 우선 순위 큐에 추가 X

  • (3, 13) 우선 순위 큐에 추가 X

  • (5, 14) 우선 순위 큐에 추가 X

    연결된 간선 모두 이미 MST에 포함된 정점과 연결되어 있으므로 우선 순위 큐에 포함하지 않는다.

    6) 우선 순위 큐에서 하나 꺼낸다. → (2, 13)

    

    정점 2는 이미 방문했다. 즉, 이미 MST에 포함된 상태이므로 건너뛴다.

    7) 우선 순위 큐에서 하나 꺼낸다. → (2, 14)

    

    위와 동일한 이유로 건너뛴다.

    최종) 우선 순위 큐가 비었으므로 MST가 완성되었다. 아래는 최종 MST의 모습이며 총 가중치는 30이다.

    

구현

우선 순위 큐 + 인접 리스트

• 프림 알고리즘

  // 간선 저장 위한 클래스
  class Edge implements Comparable<Edge>{
  	int w; // 간선 들어오는 정점
  	int cost; // 간선 가중치
  	
  	Edge(int  w, int cost){
  		this.w = w;
  		this.cost = cost;
  	}
  	
      // 간선 오름차순으로 정렬
  	@Override
  	public int compareTo(Edge o) {
  		return this.cost - o.cost;
  	}
  }
  
  // 프림 알고리즘
  public static void prim(int start, int n) {
  	boolean[] visit = new boolean[n + 1];
  		
  	PriorityQueue<Edge> pq = new PriorityQueue<>();
  	pq.offer(new Edge(start, 0));
  		
  	int total = 0;
  	while(!pq.isEmpty()) {
  		Edge edge = pq.poll();
  		int v = edge.w;
  		int cost = edge.cost;
  		
          //방문 했으면 건너뜀
  		if(visit[v]) continue;
          
  		visit[v] = true;
  		total += cost;
  		
  		for(Edge e : graph[v]) {
  			if(!visit[e.w]) {
  				pq.add(e);
  			}
  		}
  	}
      
      // 완성된 최소 신장 트리의 총 가중치 합 출력
  	System.out.println(total);
  }

• 전체 코드

  class Edge implements Comparable<Edge>{
  	int w;
  	int cost;
  
  	Edge(int  w, int cost){
  		this.w = w;
  		this.cost = cost;
  	}
  
  	@Override
  	public int compareTo(Edge o) {
  		return this.cost - o.cost;
  	}
  }
  
  public class prim_main {
  	static List<Edge>[] graph;
  
  	public static void prim(int start, int n) {
  		boolean[] visit = new boolean[n + 1];
  
  		PriorityQueue<Edge> pq = new PriorityQueue<>();
  		pq.offer(new Edge(start, 0));
  
  		int total = 0;
  		while(!pq.isEmpty()) {
  			Edge edge = pq.poll();
  			int v = edge.w;
  			int cost = edge.cost;
  
  			if(visit[v]) continue;
  
  			visit[v] = true;
  			total += cost;
  
  			for(Edge e : graph[v]) {
  				if(!visit[e.w]) {
  					pq.add(e);
  				}
  			}
  		}
  		System.out.println(total);
  	}
  
  	public static void main(String[] args) throws IOException {
     		// 그래프 입력, 저장
  		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  		int n = Integer.parseInt(bf.readLine());
  		int m = Integer.parseInt(bf.readLine());
  
          // 그래프 선언, 간선 리스트로 표현
  		graph = new ArrayList[n + 1];
  		for (int i = 0; i < graph.length; i++) graph[i] = new ArrayList<>();
  
  		StringTokenizer st;
  		for (int i = 0; i < m; i++) {
  			st = new StringTokenizer(bf.readLine());
  			int v = Integer.parseInt(st.nextToken());
  			int w = Integer.parseInt(st.nextToken());
  			int cost = Integer.parseInt(st.nextToken());
  
  			graph[v].add(new Edge(w, cost));
  			graph[w].add(new Edge(v, cost));
  		}
  
          // 프림 알고리즘 수행
  		prim(1, n);
  	}
  }

  입력
  5
  6
  1 3 3
  1 4 8
  4 5 9
  1 2 10
  2 3 13
  2 5 14
  
  출력 결과
  30

시간 복잡도

모든 노드에 대해 탐색을 진행하므로 $O(v)$이다. 그리고 우선순위 큐를 사용하여 매 노드마다 최소 간선을 찾는 시간은 $O(logV)$이다. 따라서 탐색과정에는 $O(VlogV)$가 소요된다.

그리고 각 노드의 인접 간선을 찾는 시간은 모든 노드의 차수와 같으므로 $O(\sum_{v=1}^V degree(v))$ = $O(2E)$ = $O(E)$ 다.

그리고 각 간선에 대해 힙에 넣는 과정이 $O(logV)$가 되어 우선순위 큐 구성에 $O(ElogV)$가 소요된다.

따라서, $O(VlogV + ElogV)$로 $O(ElogV)$가 된다. (∵ E가 일반적으로 V보다 크기 때문)

만약, 우선순위 큐가 아니라 배열로 구현한다면 각 정점에 최소 간선을 갖는 정점 탐색을 매번 정점마다 수행하므로 $O(|V|^2)$가 되고 탐색 결과를 기반으로 각 정점의 최소 비용 연결 정점 탐색에는 $O(1)$이 소요된다. 따라서 시간 복잡도는 $O(V^2)$이다.