[알고리즘] 최소 신장 트리 (크루스칼, 프림 알고리즘)

최소 신장 트리 (MST)

※ 일반적으로 그래프의 모든 정점이 연결되어 있다고 가정

- 신장 트리 : 모든 정점이 연결되는 트리

- 최소 신장 트리 : 신장 트리 중 사용된 간선들의 가중치가 가장 작은 간선으로만 연결된 트리

 

- V : 정점

- E : 간선

 

- 최소 신장 트리의 조건

무방향

가중치 합이 최소

간선의 개수는 $V-1$개

사이클이 없어야 함

 

- 활용

도시간 비용을 최소화 하는 문제 등에서 사용함

 

최소 신장 트리를 만드는 방법은 크루스칼과 프림 알고리즘이 있음

 

 

 

크루스칼 알고리즘 (Kruskal Algorithm)

- 특징

간선 리스트를 사용

간선을 가중치 기준으로 정렬이 먼저 이뤄저야 함 (간선이 적으면 유리)

순환 여부는 서로소를 통하여 검사함 (매 간선 선택마다 정점의 대표를 확인)

그리디 알고리즘으로 분류됨

시간 복잡도는 $O(ElogE)$ -> 간선의 정렬이 알고리즘 내에서 시간 소모에 가장 큰 영향을 미침

 

 

- 로직

0) 데이터를 간선 객체를 이용한 배열, 또는 리스트로 구현

1) 간선의 가중치를 기준으로 데이터 오름차순 정렬을 수행

2) 비용이 최소인 간선을 선택하고 서로소를 통해 객체 양 끝의 대표가 같은지(==순환이 발생할 지) 확인

    -> 연결했을 때 순환 여부를 미리 확인

3) 대표가 서로 다르면 같은 대표로 바꾸고, 간선의 가중치 정보 저장

4) 앞선 2), 3)을 선택된 간선이 $V-1$개가 될 때까지 반복

 

 

- 코드

public class Main {
	static class Edge implements Comparable<Edge> {
		int s, e, c;

		public Edge(int s, int e, int c) {
			super();
			this.s = s; // 시작 정점
			this.e = e; // 종료 정점
			this.c = c; // 비용
		}

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

	}

	static int V, E;
	static int[] parents;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt(); // 정점
		E = sc.nextInt(); // 간선

		Edge[] edges = new Edge[E]; // 간선 정보 저장
		for (int i = 0; i < E; i++) {
			edges[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
		}

		parents = new int[V];
		for (int i = 0; i < parents.length; i++) {
			parents[i] = i;
		}

		// 1) 가중치 기준 간선 정렬
		Arrays.sort(edges);

		int sum = 0, cnt = 0;
		for (int i = 0; i < edges.length; i++) {
			Edge edge = edges[i];
			// 2) 시작과 끝의 부모가 서로 다르면 (순환이 이루어지지 않는다면)
			if (find(edge.s) != find(edge.e)) {
				// 3) 대표를 변경
				union(edge.s, edge.e);
				cnt++;
				sum += edge.c;
				// 4) 선택된 간선이 V-1개 일 때까지 반복
				if (cnt == V - 1)
					break;
			}
		}

		System.out.println(sum); // output
	}

	private static int find(int s) {
		if (parents[s] == s)
			return s;
		else
			return parents[s] = find(parents[s]);
	}

	private static void union(int s, int e) {
		int ps = find(s); // 앞에서 체크 했으므로 하지 않아도 무방
		int pe = find(e); // 서로소의 union을 그대로 보존하기 위해 작성
		if (ps != pe) {
			parents[ps] = pe; // 왼쪽 정점을 오른쪽 정점의 밑으로 연결함
		}

	}
}

 

 

 

프림 알고리즘 (Prim's algorithm)

- 특징

하나의 정점에 연결된 간선 중 하나를 선택

최소 비용으로 다음 정점으로 이동하는 방법을 찾아감

Queue를 사용하며, 정렬에 대한 성능 향상을 위해 Priority Queue를 사용

시간 복잡도는 $O(logV)$ (일반 Queue를 사용했을 때는 시간 복잡도가 $O(ElogV)$) 

정점마다 최소 거리를 저장하는 배열, 방문 배열 두 가지를 사용함

 

 

- 로직

0) 최소 거리 배열, 방문 배열, 인접 리스트 구현

1) 임의의 시작 정점 선정 후 cost가 0인 상태로 Priority Queue에 삽입

2) Queue에서 데이터를 꺼내고 방문하지 않은 정점이면 방문 체크

3) 방문 체크 후 해당 정점과 연결된 모든 정점에 대해서 거리 정보 체크

4) 거리 정보가 업데이트 될 때마다 Queue에 삽입

5) Queue가 빌 때까지 2), 3), 4) 반복

 

 

- 예시

 

 

- 코드

import java.io.*;
import java.util.*;

public class Main {
	static class Vertex implements Comparable<Vertex> {
		int e, c;

		Vertex(int e, int c) {
			// 시작 정점은 배열 또는 배열 리스트의 인덱스가 됨
			this.e = e; // 도착 정점
			this.c = c; // 비용
		}

		@Override
		public int compareTo(Vertex o) {
			return Integer.compare(this.c, o.c); // 비용에 따른 정렬
		}
	}

	static int V, E;
	static ArrayList<Vertex>[] list;
	static int[] dist;
	static boolean[] v;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();
		E = sc.nextInt();

		// 리스트 생성 및 초기화
		list = new ArrayList[V];
		for (int i = 0; i < list.length; i++) {
			list[i] = new ArrayList();
		}

		for (int i = 0; i < E; i++) {
			int a = sc.nextInt(); // 시작 정점
			int b = sc.nextInt(); // 끝 정점
			int c = sc.nextInt(); // 비용
			list[a].add(new Vertex(b, c)); // 무방향 그래프
			list[b].add(new Vertex(a, c));
		}
		
		dist = new int[V]; // 정점마다 최소거리를 저장하는 배열
		v = new boolean[V]; // 방문 배열
		int sum = 0; // 결과 저장 변수
		
		Arrays.fill(dist, Integer.MAX_VALUE); // dist 모든 값을 최대 값으로 시작
		dist[0] = 0; // 임의의 정점 선택

		PriorityQueue<Vertex> q = new PriorityQueue<>();
		q.add(new Vertex(0, 0)); // 시작 정점 입력
		while (!q.isEmpty()) {
			Vertex p = q.poll(); // pq로 인해서 가장 작은 정점이 시작 정점이 됨
			if (v[p.e]) // 방문한 정점이면 continue
				continue;

			v[p.e] = true; // 방문 체크
			sum += p.c;
			for (Vertex next : list[p.e]) { // 시작 정점과 연결된 모든 정점에 대해여
				int e = next.e;
				int cost = next.c;
				if (!v[e] && cost < dist[e]) { // 연결된 정점에 방문하지 않았고, 현재 dist보다 cost가 작다면
					dist[e] = cost;
					q.add(next);
				}
			}

		}
		System.out.println(sum); // output
	}
}