[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree) (자바/Java)

목차

최소 신장 트리 (MST)

신장트리: 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리

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

• 특징
  • 무방향 가중치 그래프
  • 그래프의 가중치 합이 최소여야 한다
  • N개의 정점을 가지는 그래프에 대해 반드시 N-1개의 간선을 사용
  • 사이클을 포함하면 안된다.

크루스칼 알고리즘

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

1. 최초, 모든 간선을 가중치에 따라 올므차순으로 정렬
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가
   • 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
   • (사이클 존재: 대표가 같으면 사이클(Find-Set))
3. n-1개의 간선이 선택될 때까지 2)를 반복

Kruskal(G) {
    A <- 0 // 0 공집합
    for vertex v in G.V // G.V 그래프의 정점 집합
        Make-Set(v) // G.E: 그래프의 간선 집합

    G.E 간선들을 가중치 w에 의해 정렬

    for 가중치가 가장 낮은 간선 (u,v) in G.E 선택 (n-1개)
        if (Find-Set(u) != Find-Set(v)) // 사이클 확인
            A = A U {(u,v)}
            Union(u,v);
    return A;

}

public class Mst_Kruskal {
	static int[] p;

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

		int[][] edges = new int[E][3];
		for (int i = 0; i < E; i++) {
			edges[i][0] = sc.nextInt(); // 시작
			edges[i][1] = sc.nextInt(); // 도착
			edges[i][2] = sc.nextInt(); // 가중치
		}

		// 1. 정렬
		Arrays.sort(edges, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[2] - o2[2]; // 가중치 순서
			}

		});

		// 대표 저장
		p = new int[V];
		// make-set 1-나 자신을 대표로 초기화
		for (int i = 0; i < V; i++)
			makeSet(i);

		// 간선 선택
		int ans = 0;
		int pick = 0;
		for (int i = 0; i < E; i++) {

			if (findSet(edges[i][0]) != findSet(edges[i][1])) {
				union(findSet(edges[i][0]), findSet(edges[i][1]));
				ans += edges[i][2];
				pick++;
			}

			if (pick == V - 1)
				break;
		}
	}

	static void makeSet(int x) {
		p[x] = x;
	}

	static int findSet(int x) {
		// path compression
		if (x != p[x])
			p[x] = findSet(p[x]);
		return p[x];

	}

	static void union(int x, int y) {
		p[findSet(y)] = findSet(x);

	}
}

프림 알고리즘

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

cf. 크루스칼: 간선을 하나씩 선택함, 프림: 정점을 선택

1. 임의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점을 선택
3. 모든 정점이 선택될 때까지 1, 2를 반복

MST_Prim(G, r)
    for u in G.V
        u.key = ∞
        u.π = null
    r.key = 0
    Q = G.V // 우선순위 큐
    while (Q != 0) // 빈 q가 아닐 동안
        u = extract_min(Q) // key 값이 가장 작은 정점
        visited[u]=true
        for (v in G.Adj[u]) // u의 인접 정점 v
            if (!visited[v] and w(u, v) < v.key) // v의 key 값 갱신
                v.π = u
                v.key = w(u,v)

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

public class Mst_Prim_pq {

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

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

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost; // 최소 힙
        }

    }

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

        // 인접 리스트
        List<Edge>[] adjList = new ArrayList[V];
        for (int i = 0; i < V; i++)
            adjList[i] = new ArrayList<>();

        for (int i = 0; i < E; i++) {
            int st = sc.nextInt();
            int ed = sc.nextInt();
            int cost = sc.nextInt();

            adjList[st].add(new Edge(st, ed, cost));
            adjList[ed].add(new Edge(ed, st, cost));
        } // 입력

        boolean[] visited = new boolean[V];

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

        visited[0] = true;
        // 인접한 v들을 pq에 넣어줌
        pq.addAll(adjList[0]);
        int pick = 1;
        int ans = 0;
        while (pick < V) {
            Edge edge = pq.poll();
            if (visited[edge.ed]) // 이미 뽑은 정점
                continue;

            ans += edge.cost;

            pq.addAll(adjList[edge.ed]);
            visited[edge.ed] = true;
            pick++;
        }
        System.out.println(ans);

    }

}