[Java] 최소 신장 트리

1. 최소 신장 트리 (MST)

 

• 신장 트리
  • n개의 정점으로 이루어진 무향 그래프에서 n개 정점과 n-1개의 간선으로 이루어진 트리
• 최소 신장 트리 (Minimum Spanning Tree)
  • 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
  • 두 정점 사이의 최소 비용의 경로 찾기

 

알고리즘	방식	시간 복잡도	유리한 상황	자료구조
Kruskal	일반적	O(ElogE + V)	간선이 많지 않은 그래프	간선 리스트
Prim (PQ 구현)	우선순위 큐(PQ) 사용	O(ElogV) 또는 O(ElogE)	간선이 많지 않은 그래프	인접 행렬, 인접 리스트
Prim (반복문 구현)	반복문 사용	O(V^2)	간선이 많은 밀집 그래프	인접 행렬, 인접 리스트

(E : 간선의 수, V : 정점의 수)

 

But! PQ로 구현한 Prim 알고리즘으로 풀면 더 빠른 경우도 있다! (가지치기의 효과)

 

대부분은 Kruskal 또는 PQ로 구현한 Prim 알고리즘으로 문제를 풀면 된다.

 

---

2. 크루스칼 알고리즘

 

• Kruskal Algorithm
• 가중치가 있는 무방향 그래프에서 최소 신장 트리의 비용을 구하는 알고리즘.
• 간선을 하나씩 선택해서 MST를 구성. → 간선 리스트로 구현.

1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬.
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴.
    2-1. 사이클이 존재하면 남아 있는 간선 중 그 다음으로 가중치가 낮은 간선 선택.
3. n-1 개의 간선이 선택될 때까지 2번 작업을 반복

 

---

가. 구현

 

• 간선리스트과 서로소 집합(Union-Find) 응용.
  • 두 노드 a와 b를 잇는 간선을 선택한다. → 간선 리스트 정렬
  • 선택한 간선이 사이클을 발생시키는지 확인하고 → find(a) != find(b)
  • 사이클이 발생하지 않는다면 연결한다 → Union(a, b)

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

public class MST_Test {

    static int V, ret;
    static int[] p; // 부모 노드의 인덱스 저장
    static Edge[] edgeList; // 간선 리스트
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        edgeList = new Edge[E];

        int from, to, weight;
        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            weight = Integer.parseInt(st.nextToken());
            edgeList[i] = new Edge(from, to, weight);
        }
        // 전처리 : 간선리스트 오름차순 정렬
        Arrays.sort(edgeList);

        // Union-Find
        p = new int[V];
        make();

        // 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴.
        // 사이클이 존재하면 남아 있는 간선 중 그 다음으로 가중치가 낮은 간선 선택.
        int cnt = 0;
        for(Edge edge : edgeList) {
            if(!union(edge.from, edge.to)) continue;
            ret += edge.weight;
            cnt++;
            if(cnt > V-1) break;
        }

        System.out.println(ret);
        br.close();
    }

    static void make() {
        for(int i=0; i<V; i++) {
            p[i]=i;
        }
    }

    static int find(int x) {
        return (x == p[x]) ? x : (p[x]=find(p[x]));
    }

    static boolean union(int x, int y) {
        x = find(x);
        y = find(y);

        if(x == y) return false;
        p[y] = x;
        return true;
    }

    static class Edge implements Comparable<Edge>{
        int from, to, weight;

        public Edge(int from, int to, int weight) {
            super();
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

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

}

Kruskal 알고리즘의 시간복잡도는 O(ElogE)로 간선 E를 정렬하기 때문이다.

 

5 10
0 1 5
0 2 10
0 3 8
0 4 7
1 2 5
1 3 3
1 4 6
2 3 1
2 4 3
3 4 1

output==>10

 

7 11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51

output==>175

 

---

3. 프림 알고리즘

 

• Prim Algorithm
• 가중치가 있는 무향 그래프의 최소 신장 트리의 비용을 구한다.
• 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 구성.
• 정점 중심 → 인접 행렬, 인접 리스트로 구현.

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

 

SW Expert Academy

 

---

가. FOR문으로 구현

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

public class PrimTest {

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

        int V = Integer.parseInt(br.readLine());
        int[][] adjMatrix = new int[V][V]; // 인접 행렬
        boolean[] visited = new boolean[V]; // 트리 정점 여부
        int[] minEdge = new int[V]; // 비트리 정점 기준으로 트리 정점과 연결하기 위한 최소 간선 비용

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

        Arrays.fill(minEdge, Integer.MAX_VALUE); // 최소값 갱신 위해서 max로 초기화
        minEdge[0] = 0; // 임의의 시작점 0을 위해 처리
        int result = 0; // 최소 신장 트리 비용

        int c; // 트리에 포함된 정점의 수
        for(c=0; c<V; c++) {

            // 1. 비트리 정점 중 최소간선비용의 정점 찾기
            int min = Integer.MAX_VALUE;
            int minVertex = -1;

            for(int i=0; i<V; i++) {
                if(!visited[i] && minEdge[i] < min) { // 비트리 정점 중 최소 간선 비용
                    min = minEdge[i];
                    minVertex = i;
                }
            }

            if(minVertex == -1) break; // 더 이상 변화가 없음

            result += min; // 간선 비용 누적
            visited[minVertex] = true; // 트리 정점에 포함

            // 2. 새롭게 트리 정점에 확장된 정점 기준으로 비트리 정점들과의 간선비용 고려 최적 업데이트
            for(int i=0; i<V; i++) {
                if(visited[i]) continue;
                if(adjMatrix[minVertex][i] == 0) continue; // minVertex 정점에 인접한 비트리 정점
                if(adjMatrix[minVertex][i] < minEdge[i]) { // 최소 간선 비용으로 갱신
                    minEdge[i] = adjMatrix[minVertex][i];
                }
            }

        }
        System.out.println(c==V?result:-1); // 최소 신장 트리로 만들 수 있는 경우 result 출력
    }

}

/*
5
0 5 10 8 7 
5 0 5 3 6 
10 5 0 1 3 
8 3 1 0 1 
7 6 3 1 0

output==>10

7
0 32 31 0 0 60 51
32 0 21 0 0 0 0
31 21 0 0 46 0 25
0 0 0 0 34 18 0
0 0 46 34 0 40 51
60 0 0 18 40 0 0
51 0 25 0 51 0 0

output==>175
*/

• int[][] adjMatrix = new int[V][V];
  : 가중치를 저장하는 인접 행렬.
  
  
• boolean[] visited = new boolean[V];
  : “방문했다” = “트리에 포함된 정점이다”
  
  
• int[] minEdge = new int[V];
  : 비트리 정점 기준으로 트리 정점과 연결하기 위한 최소 간선 비용.
  
  
• Arrays.fill(minEdge, Integer.MAX_VALUE);
  : 비용은 MAX_VALUE로 초기화.
  
  
• minEdge[0] = 0;
  : 임의 정점(0)을 시작으로 트리에 새로운 정점을 추가해 나간다.
  
  
• if(!visited[i] && minEdge[i] < min) {
  : 최소 비용을 갖는 비트리 정점을 찾는다.

 

for(int i=0; i<V; i++) {
    if(visited[i]) continue;
    if(adjMatrix[minVertex][i] == 0) continue; // minVertex 정점에 인접한 비트리 정점
    if(adjMatrix[minVertex][i] < minEdge[i]) { // 최소 간선 비용으로 갱신
        minEdge[i] = adjMatrix[minVertex][i];
    }
}

• 새로운 정점이 추가될 때마다 연결가능한 정점의 가중치를 최소가 되도록 갱신한다.

 

시간복잡도가 O(V^2)로 정점의 수 V에 영향을 크게 받기 때문에 밀집 그래프일 때 유리하다.

 

---

나. PQ로 구현

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

public class PrimPQTest {

    static class Vertex implements Comparable<Vertex>{
        int no, weight;

        public Vertex(int no, int weight) {
            super();
            this.no = no;
            this.weight = weight;
        }

        @Override
        public int compareTo(Vertex o) {
            return Integer.compare(this.weight, o.weight); // 가중치 기준 오름차순으로 정렬
        }

    }

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

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

        int V = Integer.parseInt(br.readLine());
        int[][] adjMatrix = new int[V][V]; // 인접 행렬
        boolean[] visited = new boolean[V]; // 트리 정점 여부
        int[] minEdge = new int[V]; // 비트리 정점 기준으로 트리 정점과 연결하기 위한 최소 간선 비용

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

        PriorityQueue<Vertex> pq = new PriorityQueue<>(); // pq 생성
        Arrays.fill(minEdge, Integer.MAX_VALUE); // 최소값 갱신 위해서 max로 초기화
        minEdge[0] = 0; // 임의의 시작점 0을 위해 처리
        pq.offer(new Vertex(0, minEdge[0]));

        int result = 0; // 최소 신장 트리 비용

        int c = 0; // 트리에 포함된 정점의 수
        while(!pq.isEmpty()) {

            // 1. 비트리 정점 중 최소간선비용의 정점 찾기
            Vertex minVertex = pq.poll();
            if(visited[minVertex.no]) continue; // 이미 트리로 병합한 정점은 통과
            result += minVertex.weight; // 간선 비용 누적
            visited[minVertex.no] = true; // 트리 정점에 포함
            if(++c == V) break; // 모든 정점 처리 완료

            // 2. 새롭게 트리 정점에 확장된 정점 기준으로 비트리 정점들과의 간선비용 고려 최적 업데이트
            for(int i=0; i<V; i++) {
                if(visited[i]) continue;
                if(adjMatrix[minVertex.no][i] == 0) continue; // minVertex 정점에 인접한 비트리 정점
                if(adjMatrix[minVertex.no][i] < minEdge[i]) { // 최소 간선 비용으로 갱신
                    minEdge[i] = adjMatrix[minVertex.no][i];
                    pq.offer(new Vertex(i, minEdge[i])); // 갱신된 최소 간선 정보 삽입
                }
            }
        }
        System.out.println(c==V?result:-1); // 최소 신장 트리로 만들 수 있는 경우 result 출력
    }
}
/*
5
0 5 10 8 7 
5 0 5 3 6 
10 5 0 1 3 
8 3 1 0 1 
7 6 3 1 0

output==>10

7
0 32 31 0 0 60 51
32 0 21 0 0 0 0
31 21 0 0 46 0 25
0 0 0 0 34 18 0
0 0 46 34 0 40 51
60 0 0 18 40 0 0
51 0 25 0 51 0 0

output==>175
*/

• static class Vertex implements Comparable<Vertex>{
  : PQ에 넣기 위해서 별도의 class를 정의하고 Comparable을 구현한다.
  
  
• pq.offer(new Vertex(0, minEdge[0]));
  : 임의의 시작점(0)부터 시작.
  
  
• Vertex minVertex = pq.poll();
  : 비트리 정점 중 최소간선비용의 정점일 수도 있음.
  
  
• if(visited[minVertex.no]) continue;
  : 이미 트리로 병합한 정점은 통과
  
  

// 2. 새롭게 트리 정점에 확장된 정점 기준으로 비트리 정점들과의 간선비용 고려 최적 업데이트
for(int i=0; i<V; i++) {
    if(visited[i]) continue;
    if(adjMatrix[minVertex.no][i] == 0) continue; // minVertex 정점에 인접한 비트리 정점
    if(adjMatrix[minVertex.no][i] < minEdge[i]) { // 최소 간선 비용
        minEdge[i] = adjMatrix[minVertex.no][i]; // 으로 갱신
        pq.offer(new Vertex(i, minEdge[i])); // 갱신된 최소 간선 정보 PQ에 삽입
    }
}

비트리 정점(MST에 포함되지 않은 정점) 중에서 최소 비용을 갖는 정점 찾을 때 PQ를 활용.

 

시간복잡도가 O(ElogE)로 간선의 수 E에 영향을 받기 때문에 희소 그래프일 때 유리하다.

 

보통의 경우 PQ로 구현하는 것이 보통의 경우 빠르지만 밀집 그래프일 때는 오히려 느리거나 문제가 생길 수 있다.

 

---

• MST 문제

SW Expert Academy

 

 

알고리즘	용도	설명	표현	시간복잡도	기타
Prim	최소 신장 트리	가중치가 있는 무방향 그래프에서 최소 신장 트리를 찾는 알고리즘.	인접 리스트, 인접 행렬	FOR : O(V^2) PQ : O(ElogE)	무방향
Kruskal	최소 신장 트리	가중치가 있는 무방향 그래프에서 최소 신장 트리를 찾는 알고리즘.	간선 리스트	O(ElogE + V)	무방향
Dijkstra	최소 경로	음의 가중치가 없는 그래프의 한 정점에서 다른 정점들까지의 최단 거리 비용을 구하는 알고리즘.	인접 리스트, 인접 행렬	FOR : O(V^2) PQ : O(ElogE)	음의 가중치 X
Bellman-Ford	최소 경로	그래프의 한 정점에서 다른 정점들까지의 최단 거리 비용을 구하는 알고리즘.	간선 리스트	O(VE)	음의 가중치 O
Floyd-Warshall	최소 경로	모든 정점 사이의 최단 거리 비용을 구하는 알고리즘.	인접 행렬	O(V^3)	음의 가중치 O 단, 음수 사이클 X