[알고리즘 구현] 최소 신장 트리(Minimum Spanning Tree)

최소 신장 트리(Minimum Spanning Tree)

: 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법

• V: 노드
• E: 간선

---

1. 크루스칼 기법

• 간선 중 최소 값을 가진 간선부터 연결을 시작함 => 가중치에 대한 정렬이 필요함.
• 사이클(원형) 발생 시 다음 간선을 선택
• 주로 간선 수가 적을 떄 사용(정렬이 필요하기 때문에 O(ElogE)의 복잡도 발생)

구성 시 필요한 것

• 사이클을 체크 할 Parents 배열(노드의 수만큼)
  -> 자기 자신 노드의 인덱스로 초기화되어 있다가 연결이 진행되면 시작된 노드값으로 업데이트가 됨.
  -> 업데이트를 하려고 값을 봤을 때 시작된 노드값과 동일하다면 사이클 발생!
  -> 마지막까지 연결이 되면 시작된 노드값이 1개가 됨, 즉 부모노드가 1개라는 뜻으로 모든 간선으로 연결이 되었기 때문에 연결 완료.

import java.util.Arrays;

public class Kruskal {
    static int parents[];
    public static int kruskal(int[][] data, int v, int e) {
        int weightSum = 0;
        // 가중치로 정렬
        Arrays.sort(data, (x, y) -> x[2] - y[2]);

        // 부모노드 초기화 (노드가 1~ 라서 v + 1로 인덱스 관리)
        parents = new int[v + 1];
        for (int i = 1; i < v + 1; i++) {
            parents[i] = i;
        }
        // 반복문 돌면서 부모노드가 같지 않으면 연결작업하기
        for (int i = 0; i < e; i++) {
            if(find(data[i][0]) != find(data[i][1])) {
                union(data[i][0], data[i][1]);
                weightSum += data[i][2];
            }
        }
        return weightSum;
    }

    // 연결하는 메서드
    public static void union(int a, int b) {
        int aP = find(a);
        int bP = find(b);

        // 부모노드가 같지 않으면 연결(부도노드 같게 만들기)
        if(aP != bP) {
            parents[aP] = bP;
        }
    }

    // 부모노드 업데이트하는 메서드
    public static int find(int a) {
        if(a == parents[a]) {
            return a;
        }
        // 재귀호출하여 부모노드 끝을 따라감
        return parents[a] = find(parents[a]);
    }
    
    public static void main(String[] args) {
        int v = 7; // 노드
        int e = 10; // 간선
        int[][] graph = { {1, 3, 1}, {1, 2, 9}, {1, 6, 8}, {2, 4, 13}, {2, 5, 2}, {2, 6, 7}, {3, 4, 12}, {4, 7, 17}, {5, 6, 5}, {5, 7, 20} };
        System.out.println(kruskal(graph, v, e));
    }
}

---

2. 프림 기법

• 임의의 노드에서 시작 => 정렬 필요 없음.
• 연결된 노드들의 간선 중 낮은 가중치를 갖는 간선 선택
• 간선의 개수가 많을때 크루스칼보다 유리
• 시간복잡도: O(ElogV)

구성 시 필요한 것

• visited 배열: 연결된 노드 방문처리용
• Priority Queue(우선순위 큐): 연결된 노드들 중 낮은 가중치를 뽑아올 수 있도록 사용

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Prim {
    static class Node {
        int to;
        int weight;

        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static int prim(int[][] data, int v, int e) {
        int weightSum = 0;
        // 노드를 담을 ArrayList 를 담을 ArrayList
        ArrayList<ArrayList<Node>> graph = new ArrayList<>();
        // 노드 수 만큼 ArrayList 객체 생성
        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }
        // 간선 수만큼 graph정보 업데이트
        for (int i = 0; i < e; i++) {
            // 양방향이기 때문에 data[i][0] -> data[i][1]로 가는것과, 반대로 가는 것 모두 추가
            graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
            graph.get(data[i][1]).add(new Node(data[i][0], data[i][2]));
        }
        // 방문배열
        boolean[] visited = new boolean[v + 1];
        // 노드 넣어서 연결작업 할 우선순위큐
        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        pq.add(new Node(1, 0)); // 연결작업 시작을 위해 임의의 노드 추가

        int cnt = 0; // 연결작업 수 체크
        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            // 방문했었으면 넘어가고
            if(visited[cur.to]) {
                continue;
            } // 안했으면 방문체크하고 가중치 합산
            cnt++;
            visited[cur.to] = true;
            weightSum += cur.weight;
            // 간선수가 노드수 - 1개가 되면 다 연결된거니 리턴
            if(cnt == v) {
                return weightSum;
            }
            // 다 연결이 안됐으니 인접한 노드 개수만큼 순회하면서
            for (int i = 0; i < graph.get(cur.to).size(); i++) {
                Node adjNode = graph.get(cur.to).get(i); // 노드하나 가져와서
                if(visited[adjNode.to]) { // 방문했으면 넘어가고
                    continue;
                } // 방문안했으면 큐에 넣기 (연결작업 후보)
                pq.add(adjNode);
            }
        }
        return weightSum;
    }

    public static void main(String[] args) {
        int v = 7; // 노드
        int e = 10; // 간선
        int[][] graph = { {1, 3, 1}, {1, 2, 9}, {1, 6, 8}, {2, 4, 13}, {2, 5, 2}, {2, 6, 7}, {3, 4, 12}, {4, 7, 17}, {5, 6, 5}, {5, 7, 20} };
        System.out.println(prim(graph, v, e));
    }
}

*ArrayList<ArrayList> graph 의 구조*

(직관적으로 다가오질 않아서 그려봄…)

---

마지막 수정일시: 2022-07-20 14:30