[알고리즘]최소신장트리: kruskal,prim알고리즘 - Java로 구현하기

📖최소신장트리

최소신장트리란 1)모든 정점을 포함하면서 2)간선의 가중치 합이 최소인 트리를 말한다.

최소신장트리를 찾는 알고리즘 중 대표적으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다.

 

🔍Kruskal 알고리즘

간선 중심 → edgeList가 필요

1. 최초 모든 간선을 가중치에 따라 오름차순으로 정렬

2. 가중치가 낮은 간선부터 선택하면서 트리를 증가시킨다. 이때, 사이클이 존재하면 남아 있는 간선 중 그 다음으로 가중치가 낮은 선택

=>N-1개의 간선이 선택될 때까지 2반복

*서로소 집합(Disjoint-set)을 이용한 Kruskal 알고리즘의 구현

서로소 집합(Disjoint-set)은 중복 포함된 원소가 없는 집합을 의미한다. 

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

//메모리:49648KB, 시간:632ms
public class Main_1197_G4_최소스패닝트리_KRUSKAL_조서영 {
    static int V; //정점의 개수
    static int E; //간선의 개수
    static Edge[] edgeList; //간선리스트

    ///서로소집합/////////////////////
    static int[] parents; //서로소 집합

    public static void make() {
        parents = new int[V+1];
        for(int i=1;i<V+1;i++){
            parents[i] = i;
        }
    }
    public static int find(int a){
        if(a==parents[a]) return a;
        return parents[a]=find(parents[a]);
    }
    public static boolean union(int a, int b){
        int aRoot = find(a);
        int bRoot = find(b);
        if(aRoot==bRoot) return false; //트리를 합칠 수 없음
        parents[bRoot] = aRoot;
        return true;
    }
    ///////////////////////////////

    static class Edge implements Comparable<Edge>{
        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 Integer.compare(this.weight, o.weight);
        }
    }
    public static int MSTKruskal(){
        make();

        Arrays.sort(edgeList);

        int result = 0;
        int cnt = 0;
        for(Edge edge : edgeList){
            if(!union(edge.from,edge.to)) continue;
            result += edge.weight;
            if(++cnt==V-1) break; //최소 신장 트리 완성
        }

        return cnt==V-1?result:-1;
    }

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

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

        for(int i=0;i<E;i++){
            st = new StringTokenizer(br.readLine());
            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);
        }

        System.out.println(MSTKruskal());
    }
}

 

🔍 Prim 알고리즘

정점 중심 → visited[]을 이용해서 정점 방문여부를 check

1. 임의 정점을 하나 선택해서 시작

2. 선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점을 선택

=>모든 정점이 선택될 때까지 2과정을 반복

*인접행렬(adjMatrix)을 이용한 Prim 알고리즘의 구현

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

public class Main_1197_G4_최소스패닝트리_PRIM_조서영 {
    static int V; //정점의 개수
    static int E; //간선의 개수
    static int[][] adjMatrix; //인접행렬
    static boolean[] visited; //정점 방문여부 check
    static int[] minEdge;

    public static int MSTPrim(){
        visited = new boolean[V+1];
        minEdge = new int[V+1];
        Arrays.fill(minEdge,Integer.MAX_VALUE);

        int result = 0;
        minEdge[1]=0;
        int c=0;
        for(c=0;c<V-1;c++){
            int min = Integer.MAX_VALUE;
            int minVertex = -1;

            for(int i=1;i<V+1;i++){
                if(!visited[i] && minEdge[i]<min){
                    min=minEdge[i];
                    minVertex=-1;
                }
            }

            if(minVertex==-1) break; //트리를 만들 수 없는 경우
            result+=min;
            visited[minVertex]=true;

            for(int i=1;i<V+1;i++){
                if(!visited[i] && adjMatrix[minVertex][i]!=0
                    &&adjMatrix[minVertex][i]<minEdge[i]){
                    minEdge[i]=adjMatrix[minVertex][i];
                }
            }
        }

        return c==V-1 ? result : -1;
    }

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

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        adjMatrix = new int[V+1][V+1];

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

        System.out.println(MSTPrim());
    }
}

그런데 인접행렬로 그래프를 구하는 경우 인접행렬 자체가 

배열 크기=10,000×10,000×4바이트

1024Byte = 1KB

1024KB = 1MB

약381.47 MB를 차지하므로 메모리 초과가 발생한다.​

 

 

⇒ 간선이 적은 희소행렬인 경우에는 Kruskal 알고리즘이, 간선이 많은 밀집행렬인 경우에는 Prim 알고리즘이 유리하다.

 

*백준: 최소 스패닝 트리

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리