Kruskal & Prim 비교

2020/09/14 - [개발자/Algorithm] - Kruskal's Algorithm

2020/09/21 - [개발자/Algorithm] - Prim's Algorithm

블로그에 포스팅한 원글과, 원글에 포함된 원본 소스코드, 그 소스코드의 출처는 위와 같습니다. 아래 코드는 제가 원본 소스코드를 참고하여 수정한 코드입니다.

 

 

Kruskal

// 기존 1번 코드 원본에서 불필요하게 반복되는 find 함수의 실행을 줄임.

import java.io.IOException;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;


public class Kruskal2 {
    static int V, E;                    // V : 점, E : 변
    static ArrayList<Edge> mst;         // result값 Minimum spanning tree
    static PriorityQueue<Edge> pq;      // 모든 노드(점)을 힙에 넣고 시작.
    static int[] arr ;                  // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.

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

        // Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
        V = sc.nextInt();

        // Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
        E = sc.nextInt();

        mst = new ArrayList<>();
        arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
        // Queue는 기본적으로 FIFO 구조를 갖는다. Priority queue는  '최대 우선순위 큐'와 '최소 우선순위 큐'로 나뉜다.
        pq = new PriorityQueue<>();

        // vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
        for (int i = 0; i <= V; i++) {
            // 각 vertex는 시작할 때는 자기 자신을 root로 초기화.
            arr[i] = i;
        }

        // 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5...  1 3 4 에 해당)
        for (int i = 0; i < E; i++) {
            int v1 = sc.nextInt();      // 1번 노드와...  1번 노드와
            int v2 = sc.nextInt();      // 2번 노드의...  3번 노드의
            int value = sc.nextInt();   // 비용은 5다...  비용은 4다

            // 우선순위 큐에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
            pq.add(new Edge(v1, v2, value));
        }

        // V개의 노드를 연결하는 최소 Edge의 수는 '노드-1'이므로 mst.size()가 'V-1'이 될 때까지 반복한다.
        // 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
        while(mst.size() < (V-1)) {
            // PQ에 하나씩 넣었고, 이제 하나씩 뺀다. PQ로 넣어서 FIFO이 아닌 오름차순으로 나온다.(value 기준)
            Edge edge = pq.poll();
            // Edge의 양 끝 각 노드(start, end라 명명함)의 최종 부모(root)를 구한다.
            int parentEdgeStart = find(edge.start);
            int parentEdgeEnd = find(edge.end);

            // Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
            if(parentEdgeStart != parentEdgeEnd)
            {
                // 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 mst ArrayList에 edge 객체를 추가한다.
                mst.add(edge);
                // MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
                union(parentEdgeStart, parentEdgeEnd);
            }
        }
        System.out.println(mst);
    }

    static int find(int n) {            // 입력 받은 노드의 최종 부모를 구한다.
        if (n == arr[n]) {              // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
            return n;
        } else {
            int p = find(arr[n]);       // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
                                        // 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
            arr[n]=p;                   // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
                                        // 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
            return p;                   // 최종 부모(root)를 return.
        }
    }

    // Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
    static void union(int p1, int p2) {
        if (p1 != p2) {
            arr[p1]= p2;
        }
    }

    // Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
    static class Edge implements Comparable<Edge>{
        int start, end, value;

        Edge(int s, int e, int v) {
            this.start = s;
            this.end = e;
            this.value = v;
        }
        @Override
        public int compareTo(Edge o) {
            return this.value - o.value;
        }
        @Override
        public String toString() {
            return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
        }
    }
}

/*
6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
4 6 8
3 5 11
4 5 3
5 6 8
*/

// 2번 코드에서 Scanner를 BufferedReader, InputStreamReader로 바꿈.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;


public class Kruskal3 {
    static int V, E;                    // V : 점, E : 변
    static ArrayList<Edge> mst;         // result값 Minimum spanning tree
    static PriorityQueue<Edge> pq;      // 모든 노드(점)을 힙에 넣고 시작.
    static int[] arr ;                  // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        // throws IOException을 해주거나,
        // String var = null; 을 미리 인스턴스화 시킨 후
        // try {
        //      var = bufferedReader.readLine();
        // } catch (IOException | NumberFormatException e) {
        //      e.printStackTrace();
        // }
        // 을 해줘야한다.

        // Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
        V = Integer.parseInt(bufferedReader.readLine());

        // Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
        E = Integer.parseInt(bufferedReader.readLine());

        mst = new ArrayList<>();
        arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
        // Queue는 기본적으로 FIFO 구조를 갖는다. Priority queue는  '최대 우선순위 큐'와 '최소 우선순위 큐'로 나뉜다.
        pq = new PriorityQueue<>();

        // vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
        for (int i = 0; i <= V; i++) {
            // 각 vertex는 시작할 때는 자기 자신을 root로 초기화.
            arr[i] = i;
        }

        // Edge의 정보는 양쪽 Vertex와 비용, 3개의 정보만 고정적으로 존재하기 때문에 3으로 고정 선언.
        String[] inputTmp = new String[3];
        int v1;
        int v2;
        int value;

        // 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5...  1 3 4 에 해당)
        for (int i = 0; i < E; i++) {
            inputTmp = bufferedReader.readLine().split(" ");
            v1 = Integer.parseInt(inputTmp[0]);     // 1번 노드와...  1번 노드와
            v2 = Integer.parseInt(inputTmp[1]);     // 2번 노드의...  3번 노드의
            value = Integer.parseInt(inputTmp[2]);  // 비용은 5다...  비용은 4다

            // 우선순위 큐에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
            pq.add(new Edge(v1, v2, value));
        }

        // V개의 노드를 연결하는 최소 Edge의 수는 '노드-1'이므로 mst.size()가 'V-1'이 될 때까지 반복한다.
        // 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
        while(mst.size() < (V-1)) {
            // PQ에 하나씩 넣었고, 이제 하나씩 뺀다. PQ로 넣어서 FIFO이 아닌 오름차순으로 나온다.(value 기준)
            Edge edge = pq.poll();
            // Edge의 양 끝 각 노드(start, end라 명명함)의 최종 부모(root)를 구한다.
            int parentEdgeStart = find(edge.start);
            int parentEdgeEnd = find(edge.end);

            // Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
            if(parentEdgeStart != parentEdgeEnd)
            {
                // 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 mst ArrayList에 edge 객체를 추가한다.
                mst.add(edge);
                // MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
                union(parentEdgeStart, parentEdgeEnd);
            }
        }
        bufferedReader.close();
        System.out.println(mst);
    }

    static int find(int n) {            // 입력 받은 노드의 최종 부모를 구한다.
        if (n == arr[n]) {              // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
            return n;
        } else {
            int p = find(arr[n]);       // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
            // 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
            arr[n]=p;                   // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
            // 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
            return p;                   // 최종 부모(root)를 return.
        }
    }

    // Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
    static void union(int p1, int p2) {
        if (p1 != p2) {
            arr[p1]= p2;
        }
    }

    // Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
    static class Edge implements Comparable<Edge>{
        int start, end, value;

        Edge(int s, int e, int v) {
            this.start = s;
            this.end = e;
            this.value = v;
        }
        @Override
        public int compareTo(Edge o) {
            return this.value - o.value;
        }
        @Override
        public String toString() {
            return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
        }
    }
}

/*
6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
4 6 8
3 5 11
4 5 3
5 6 8
*/

 

 

Prim

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

public class Prim3 {
    static int V, E;                        // V : 점, E : 변
    static ArrayList<Edge> mst;             // result값 Minimum spanning tree
    static LinkedList<Edge>[] graph;        // Kruskal에서는 각 노드를 PriorityQueue<Edge>에 넣었다면, 여기서 graph는 해당 노드가 start인 모든 엣지를 넣는다. 즉, 3번 노드와 연결된 엣지가 5개면 3번 graph[3] start가 3인 엣지를 5개 가지고 있는 배열이 된다.
    static boolean[] visit;                 // 노드의 방문 여부 (Kruskal에서는 int[] arr에 각 노드의 부모가 누구인지를 저장했다.)

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

        V = sc.nextInt();
        E = sc.nextInt();

        // 각 노드를 graph로 정의한다. 배열을 V+1개로 만들면 인덱스가 0 ~ V까지 배정되고, 0을 버리고 1 ~ V번 인덱스를 사용한다.
        graph = new LinkedList[V+1];
        // 각 노드의 방문 여부를 boolean 타입의 일차운 단순 배열로 만든다.
        visit =  new boolean[V+1];

        // 1번 노드부터 V번 노드까지 LinkedList<Edge>[] 타입의 graph 변수에 넣는다. (1 ~ 6번 노드가 샘플로 주어진다.)
        for (int i = 1; i <= V; i++) {
            graph[i]= new LinkedList<>();
        }

        mst = new ArrayList<>();

        // 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5...  1 3 4 에 해당. 엣지가 총 9개 주어졌으니 9번 돈다.)
        for (int i = 0; i < E; i++) {
            int v1 = sc.nextInt();      // 1번 노드와...  1번 노드와
            int v2 = sc.nextInt();      // 2번 노드의...  3번 노드의
            int value = sc.nextInt();   // 비용은 5다...  비용은 4다

            // 노드1에서 노드2로 가는 방향으로 저장.
            graph[v1].add(new Edge(v1,v2,value));
            // 노드2에서 노드1로 가는 방향으로 저장.
            graph[v2].add(new Edge(v2,v1,value));

            // 왜 양방향으로 저장할까?
            // 노드를 기준으로 뻗어 나가는 엣지를 정의하고 그 중 비용이 작은 것을 택하는 것이기 때문에 각 노드에서 뻗어나가는 모든 엣지를 합하면 결국 양방향이 되고 전체 엣지의 2배가 된다.
        }

        // Kruskal에서 while(mst.size() < (V-1)) { }에 해당. 메인 메소드에 다 넣지 않고 빼놓은 것 뿐이다.
        makeMst();
        System.out.println(mst);

    }
    static void makeMst() {
        // 1. 시작 노드는 아무거나 지정.
        // 2. 선택한 노드에 연결된 엣지들을 PrioityQueue에 넣는다. (비용을 기준으로 오름차순 정렬됨.)
        // 3. 비용이 최소인 Edge 객체를 poll()한다. 이 객체는 [start, end, value]를 갖고 있고, end를 visit 검사를 통해 방문 여부를 확인한다.
        // 4. 2~3 반복. n-1개의 간선이 선택할때까지 or 모든 정점이 연결될때까지

        // 노드를 기준으로 연결된 엣지를 담을 PriorityQueue를 하나 인스턴스화 한다. 그러면 해당 노드에 연결된 엣지들을 비용을 기준으로 오름차순 정렬한다.
        PriorityQueue<Edge> pq = new PriorityQueue<>();

        // 프림 알고리즘을 돌리기 위해 현재 방문중인 노드를 nowV라는 int타입 변수에 넣는다.
        // 1로 임의로 정한 것은 시작점을 1로 하겠다는 의미다. 3에서 시작하고 싶다면 3을 넣으면 된다.
        int nowV = 1;

        while(mst.size() < (V-1)) {
            // 현재 노드는 방문 했으니 true로 바꾼다.
            visit[nowV] = true;

            // LinkedList<Edge>[] graph에 모든 노드를 담고 시작했다. nowV에 해당하는 노드의 엣지를 하나씩 꺼낸다.
            // 즉, 1번 노드에 엣지가 3개면 각 엣지로 for문을 3번 돌거고, 5번 노드에 엣지가 1개면 for문을 1번 돌고 그런 식이다.
            // 그리고 이 엣지는 nowV라는 노드가 볼 때, start(자기 자신), end(연결된 노드), value(비용)을 가진 객체다.
            // 따라서 이 for문은 주어진 노드에 연결된 엣지를 개수만큼 꺼내 위에서 선언한 pq에 넣어 비용을 기준으로 엣지를 오름차순 정렬시킨다.
            // 이때 해당 노드의 모든 엣지를 무조건 가져올 수도 있찌만 이미 방문한 노드는 다시 계산할 필요가 없으니 if(!visit[edge.end]) { } 를 통해 방문된 노드와 연결된 엣지는 무시한다.
            for (Edge edge : graph[nowV]) {
                // Edge가 start -> end니까. start가 지금 들어온 nowV번 노드고, end가 start에서 뻗어 나간 엣지의 도착 방향의 노드다.
                // 이미 방문된 노드의 엣지는 무시하기 위한 로직.
                // *** 여기서 중요한 것은 방문한 노드가 end인 엣지를 추가하지 않았지만 그게 더 효율적일 수도 있다. 즉, 눈으로 볼 때는 그게 쉽게 보이지만
                // 컴퓨터로 볼 때는 그렇지 않다. 그러면 어떻게 처리를 할까? 방문한 노드 방향의 엣지를 담지 않는 대신 해당 엣지는 이미 이전에 반대편 노드가 start로 들어왔을 때
                // pq에 담겨있고, 그 pq를 매번 돌 때마다 초기화 하지 않기 때문에 유지가 된다. 즉,
                if(!visit[edge.end]) {
                    pq.add(edge);
                }
            }

            // nowV 노드의 엣지를 비용으로 정렬시킨 PriorityQueue가 모두 사라질 때까지 반복한다.
            while(!pq.isEmpty()) {
                // nowV 노드의 엣지중 비용이 작은 것부터 꺼낸다.
                Edge edge = pq.poll();
                // 해당 엣지의 end(nowV와 연결된 노드)가 방문하지 않았다면 if문으로 들어간다.
                if(!visit[edge.end]) {
                    // 이제 유효한 엣지를 찾았으니 방문중인 노드 nowV는 다음 노드로 이동한다.
                    nowV = edge.end;
                    // 그리고 그 엣지를 mst에 넣는다.
                    mst.add(edge);
                    // mst를 찾았으면 해당 nowV의 다른 엣지(지금 찾은 엣지보다 비용이 더 큰 엣지)는 반복을 중단한다.
                    break;
                }
            }
        }
    }
    static class Edge implements Comparable<Edge>{
        int start, end, value;

        Edge(int s, int e, int v) {
            this.start = s;
            this.end = e;
            this.value = v;
        }
        @Override
        public int compareTo(Edge o) {
            // TODO Auto-generated method stub
            return this.value - o.value;
        }
        @Override
        public String toString() {
            return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
        }
    }
}

/*
6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
4 6 8
3 5 11
4 5 3
5 6 8
*/