[Algorithm] MST(최소 신장 트리)와 크루스칼(Kruskal), 프림(Prim) 알고리즘 정리

MST(최소 신장 트리, Minimum Spanning Tree)란?

MST(최소 신장 트리, Minimum Spanning Tree)는 가중치 그래프에서 모든 정점을 연결하는 간선들의 부분 집합 중에서 최소 비용을 가지는 트리이다.
즉, 모든 정점을 연결하면서 간선의 가중치 합이 최소가 되는 부분 그래프를 의미한다.

MST의 특징

1. 모든 정점이 연결되어 있어야 함 (Connected Graph)
2. 사이클(Cycle)이 포함되지 않음 (Tree)
3. (N-1)개의 간선으로 구성됨 (N개의 정점을 가지는 그래프라면 MST의 간선 수는 N-1)
4. 가중치 합이 최소여야 함

MST의 활용

• 통신 네트워크 구축 (최소 비용으로 도시 연결)
• 전력망 설계 (최소 비용으로 전선 연결)
• 도로 네트워크 최적화
• 이미지 처리, 군집화(Clustering) 알고리즘

 

MST를 찾는 대표적인 알고리즘은 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있다.

 

크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘 개요

• 간선 중심(Greedy) 알고리즘
• 간선을 오름차순 정렬 후, 작은 것부터 선택하여 MST를 만듦
• 유니온 파인드(Union-Find) 알고리즘을 사용하여 사이클을 방지

크루스칼 알고리즘 동작 과정

1. 모든 간선을 가중치 기준 오름차순 정렬
2. 가장 작은 가중치의 간선부터 선택 (사이클이 생기지 않는 경우)
3. 사이클이 생기지 않도록 유니온 파인드 사용
4. N-1개의 간선을 선택하면 종료

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

public class Kruskal {
    
    private static class Edge implements Comparable<Edge> {
        public int from, to, weight;
        
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;  // 가중치 오름차순 정렬
        }
    }
    
    private static Edge[] edgeList;
    private static int N;  // 정점 개수
    private static int[] parents;  // 유니온 파인드를 위한 부모 배열

    // 유니온 파인드: 단위 집합 생성
    private static void makeSet() {
        parents = new int[N];
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
    }

    // 유니온 파인드: find 연산 (경로 압축)
    private static int findSet(int a) {
        if (parents[a] == a) return a;
        return parents[a] = findSet(parents[a]);  // 경로 압축
    }

    // 유니온 파인드: union 연산
    private static boolean union(int a, int b) {
        int aRoot = findSet(a);
        int bRoot = findSet(b);
        if (aRoot == bRoot) return false;  // 사이클 발생 방지
        parents[bRoot] = aRoot;
        return true;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");

        N = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        
        edgeList = new Edge[E];

        // 간선 정보 입력
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            edgeList[i] = new Edge(from, to, weight);
        }

        // 1. 간선 정렬 (가중치 기준 오름차순)
        Arrays.sort(edgeList);

        // 2. 유니온 파인드 초기화
        makeSet();

        int result = 0;  // MST 비용
        int count = 0;  // MST 간선 수

        // 3. 최소 가중치 간선부터 선택하여 MST 생성
        for (Edge edge : edgeList) {
            if (union(edge.from, edge.to)) {
                result += edge.weight;
                if (++count == N - 1) break;  // MST 완성 시 종료
            }
        }

        System.out.println(result);  // MST 최소 비용 출력
    }
}

 

프림(Prim) 알고리즘

프림 알고리즘 개요

• 정점 중심(Greedy) 알고리즘
• 임의의 시작점에서 시작하여 점진적으로 MST 확장
• 우선순위 큐(Priority Queue)를 사용하면 더 효율적

프림 알고리즘 동작 과정

1. 임의의 시작 정점을 선택
2. 선택한 정점과 연결된 간선 중 최소 가중치 간선 선택
3. 해당 간선으로 새로운 정점을 MST에 추가
4. 모든 정점이 MST에 포함될 때까지 반복

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

// 프림 알고리즘 인접행렬
public class Prim_AdjMatrix {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine().trim());  // 정점 개수
        int[][] adjMatrix = new int[N][N];  // 인접 행렬
        int[] minEdge = new int[N];  // MST 포함 간선 최소 비용
        boolean[] visited = new boolean[N];  // MST 포함 여부

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                adjMatrix[i][j] = Integer.parseInt(st.nextToken());
            }
            minEdge[i] = Integer.MAX_VALUE;
        }

        int result = 0;  // MST 비용
        minEdge[0] = 0;  // 시작 정점

        for (int cnt = 0; cnt < N; cnt++) {
            int min = Integer.MAX_VALUE;
            int current = 0;

            for (int i = 0; i < N; i++) {
                if (!visited[i] && minEdge[i] < min) {
                    min = minEdge[i];
                    current = i;
                }
            }

            visited[current] = true;
            result += min;

            for (int i = 0; i < N; i++) {
                if (!visited[i] && adjMatrix[current][i] != 0 && minEdge[i] > adjMatrix[current][i]) {
                    minEdge[i] = adjMatrix[current][i];
                }
            }
        }

        System.out.println(result);
    }
}

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

// 프림알고리즘 - 인접 리스트
public class Prim_AdjMatrix {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine().trim());  // 정점 수

		int[][] adjMatrix = new int[N][N];  // 인접행렬
		int[] minEdge = new int[N];  // 다른정점에서 자신으로 연결하는 MST를 구성하는 간선비용 중 최소비용
		boolean[] visited = new boolean[N];  // 신장트리에 선택된 여부

		StringTokenizer st = null;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				adjMatrix[i][j] = Integer.parseInt(st.nextToken());
			}
			minEdge[i] = Integer.MAX_VALUE;  // 충분히 큰 값으로 최소값 초기화
		}
		
		// 0단계: 첫 방문 정점의 최소비용을 0으로 설정
		int vertexCount = 0;  // 선택된 정점의 개수
		int result = 0;  // MST 비용 (구하고자 하는 값)
		minEdge[0] = 0;  // 임의의 시작점을 0번 정점으로 설정
		
		
		for (int cnt = 0; cnt < N; cnt++) {
			
			// 1단계: 신장트리의 구성에 포함되지 않은 정점 중 최소비용 정점 선택
			int min = Integer.MAX_VALUE;
			int current = 0;
			
			for (int i = 0; i < N; i++) {
				if (!visited[i] && min > minEdge[i]) {
					min = minEdge[i];
					current = i;
				}
			}
			
			// 신장트리에 추가 (방문체크)
			visited[current] = true;
			
			// 최소비용 누적
			result += min;
			
			// (선택사항) 이미 MST가 완성 됐으므로 여기서 가지치기
			if (++vertexCount == N) {
				break;
			}
			
			// 2단계: 신장트리에 새롭게 추가되는 정점과 신장트리에 포함되지 않은 정점들의 기존 최소비용과 비교해서 갱신
			for (int i = 0; i < N; i++) {
				
				// 신장트리에 포함되지 않았고,
				// 선택된 정점과 인접한 정점이며,
				// 선택된 정점과의 비용이 이전까지의 최소비용보다 작다면
				if (!visited[i]
						&& adjMatrix[current][i] != 0
						&& minEdge[i] > adjMatrix[current][i]) {
					
					minEdge[i] = adjMatrix[current][i];  // 최소비용으로 갱신
				}
			}
		}
		
		System.out.println(result);
	}
}