최소 신장 트리(Minimum Spanning Tree)_크루스칼/프림

최소 신장 트리의 개념

 

신장 트리 중에서 사용된 간선의 가중치의 합이 최소인 트리'

 

 

최소 신장 트리의 특징

 

1) 무방향 가중치 그래프

2) 그래프 가중치의 합이 최소

3) N개의 정점이 있는 그래프에 대해 반드시 N-1개의 간선을 사용해야 함

4) 사이클을 포함하면 안 된다 => 사이클 포함 = 불필요한 간선 존재

 

 

최소 신장 트리의 실 사용

 

비용이 최소가 되어야 하는 도로망, 통신망과 같은 다양한 분야

 

 

최소 신장 트리 구현 

 

1) 크루스칼(Kruskal); 그리디 알고리즘의 한 종류  => 희소 그래프 인 경우 적합

 

간선을 하나씩 선택하며 MST를 찾는 알고리즘

  (1) 모든 간선을 가중치에 따라 오름차순 정렬
  (2) 가중치가 낮은 간선부터 선택하며 트리 증가 => 사이클이 존재*하면 그 다음 가중치를 가진 간선 선택

  (3) "n-1개의 간선"을 가질 때까지 (2) 반복 수행

 

* 사이클이 존재한다는 것: (Union-Find 활용) 한 간선의 양 정점의 대표를 찾아봤을 때(findset) 둘의 결과 값이 같으면 같은 집합에 속한다는 의미이고 이를 통해 사이클이 존재한다는 것을 알 수 있다. 

 

문제 예시

  여러 개의 네트워크 지점들이 있는데, 모든 지점들을 유선으로 연결하되 연결선의 총 길이가 최소가 되야 하는 문제
  도시들을 모두 연결하되, 연결하는 도로의 길이 합이 최소가 되야 하는 문제

 

크루스칼의 시간 복잡도:  O(elog₂e) *간선 정렬 시 퀵정렬과 같이 효율적인 알고리즘 이용하는 경우

 

 

2) 프림(Prim); 그리디 알고리즘의 한 종류 => 밀집 그래프 인 경우 적합 => 인접 리스트 + 우선순위 큐

 

크루스칼과 달리 정점을 선택해가며 MST를 만들어가는 방식인데 선택 시 간선의 가중치가 최소로 이어지는 정점을 선택한다.
"모든 정점"을 연결하는 것이기 때문에 시작정점을 무엇으로 설정하든지 크게 상관없다.

 

크루스칼의 시간 복잡도:  O(n^2)

 

 

백준 1922

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {// 최소 스패닝 트리
	static int pc, edge;
	static boolean[] visited;

	static public class Node implements Comparable<Node> {
		int st, ed, cost;

		public Node(int st, int ed, int cost) {
			this.st = st;
			this.ed = ed;
			this.cost = cost;
		}

		@Override
		public int compareTo(Node o) {
			return this.cost - o.cost;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		pc = sc.nextInt();
		edge = sc.nextInt();

		List<Node>[] network = new ArrayList[pc + 1];

		for (int i = 1; i <= pc; i++) {
			network[i] = new ArrayList<>();
		}
		visited = new boolean[pc + 1];

		for (int n = 0; n < edge; n++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();

			network[a].add(new Node(a, b, c));
			network[b].add(new Node(b, a, c));
		}

		PriorityQueue<Node> pq = new PriorityQueue<>();

		visited[1] = true;
		int connect = 1;
		for (int i = 0; i < network[1].size(); i++) {
			pq.offer(network[1].get(i));

		}

		int totalCost = 0;

		while (connect != pc) {
			Node n = pq.poll();
			if (visited[n.ed]) {
				continue;
			}
			totalCost += n.cost;
			pq.addAll(network[n.ed]);
			visited[n.ed] = true;
			connect++;
		}
		System.out.println(totalCost);

		sc.close();
	}
}