최소 신장 트리 알고리즘

최소 신장 트리(MST) 란?

그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.

 

특징

• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1 개이다.

 

※ 절대적이지 않지만,

간선이 적으면 KRUSKAL, 간선이 많으면 PRIM 알고리즘이 유리

 

(1) Kruskal MST 알고리즘

(간선을 고르는 간선 중심)

 

핵심 이론

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기

• 데이터를 노드가 아닌 에지 중심으로 저장하므로 에지 리스트의 형태로 저장한다.
• 사이클 처리를 위한 유니온 파인드 배열도 함께 초기화한다. 배열의 인덱스를 해당 자리의 값으로 초기화하면 된다.

2. 그래프 데이터를 가중치 기준으로 정렬하기

• 에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.

3. 가중치가 낮은 에지부터 연결 시도하기

• 가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다.
• 이때, 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 여부를 find 연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union 연산을 이용해 두 노드를 연결한다.

4. 전체 노드의 개수가 N개일 때, 연결한 에지의 개수가 N-1이 될 때까지 과정을 반복한다.

 

Use edgeList

public class MST_Kruskal_Test {
 
    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);
        }
    }
 
    static int V, E;
    static Edge[] edgeList;
    static int[] parents;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader in = 
            new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine(), " ");
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        edgeList = new Edge[E];
        parents = new int[V];
 
        // 각 간선 및 가중치에 대한 정보(간선의 가중치)
        int from, to, weight;
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(in.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);
        // 정점 초기화
        make();
        // 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가
        int cnt = 0, res = 0;
        for (Edge edge : edgeList) {
            // 싸이클이 형성되지 않았다면
            if (union(edge.from, edge.to)) {
                res += edge.weight;
                // N-1개의 간선이 선택될 때까지 반복
                if (++cnt == V - 1) break;
            }
        }
        
        System.out.println(res);
    }
 
    // 정점 초기화(자신을 대표자로)
    private static void make() {
        for (int i = 0; i < V; i++) {
            parents[i] = i;
        }
    }
    // Find : Path Compression
    private static int find(int a) {
        if (a == parents[a]) return a;
        return parents[a] = find(parents[a]);
    }
    // Union
    private static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        // 사이클 존재 시 false
        if (aRoot == bRoot) return false;
        // 사이클이 생성되지 않는다면(다른 부모를 갖는다면) Union 수행
        parents[bRoot] = aRoot;
        return true;
    }
}

 

 

(2) Prim 알고리즘

(정점을 고르는 점 중심)

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법, 즉, 이전 단계에서 만들어진 신장 트리를 확장하는 방법

 

[과정]

• 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.
• 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
  • 즉, 가장 낮은 가중치를 먼저 선택한다.
• 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.

[인접행렬]

public class MST_Prim_Test {
 
    static class Node implements Comparable<Node> {
        // 목적지
        int no;
        // 비용
        int edge;
        public Node(int no, int edge) {
            super();
            this.no = no;
            this.edge = edge;
        }
        @Override
        public int compareTo(Node o) {
            return this.edge - o.edge;
        }
    }
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine().trim());
        int[][] input = new int[cnt][cnt];
        boolean[] visited = new boolean[cnt];
        int[] minEdge = new int[cnt];
        PriorityQueue<Node> queue = new PriorityQueue<Node>();
 
        StringTokenizer st;
        for (int i = 0; i < cnt; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < cnt; j++) {
                input[i][j] = Integer.parseInt(st.nextToken());
            }
            minEdge[i] = Integer.MAX_VALUE;
        } // i노드에서 j노드까지의 비용을 모두 배열에 저장
 
        int result = 0, nodeCount = 0;
        minEdge[0] = 0;
        queue.offer(new Node(0, 0));
 
        while (!queue.isEmpty()) {
 
            // 일단 꺼내자. 그럼 젤 작은애가 나오겠찌.
            Node minVertex = queue.poll();
            // 근데 그 나온애가 이미 목적지가 확보된 녀석이라면 패스.
            if (visited[minVertex.no]) continue;
 
            // 확보되지 않은애가 나왔으면 고르자.
            result += minVertex.edge;
            visited[minVertex.no] = true;
            if (++nodeCount == cnt) break;
 
            for (int j = 0; j < cnt; j++) {
                // 새로 확보된 녀석으로부터 출발하는 간선을 다 PQ에 넣는다.
                if (!visited[j] && input[minVertex.no][j] != 0 && input[minVertex.no][j] < minEdge[j]) {
                    minEdge[j] = input[minVertex.no][j];
                    queue.offer(new Node(j, input[minVertex.no][j]));
                }
            }
        }
        System.out.println(result);
    }
 
}

 

 

[인접 리스트]

public class MST_Prim_Test {
 
    static int V, E;
    static ArrayList<Node>[] adj;
    static class Node implements Comparable<Node> {
        int to, weight;
 
        public Node(int to, int weight) {
            super();
            this.to = to;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.weight, o.weight);
        }
        
    }
    
    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());    // 간선 개수
        
        adj = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) {
            adj[i] = new ArrayList<>();
        }
        
        // Edge 정보 입력
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            // 인접 리스트
            adj[a].add(new Node(b, c));
            adj[b].add(new Node(a, c));
        }
        
        System.out.println(prim());
    }
 
    private static long prim() {
        
        boolean[] visited = new boolean[V + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 1번 노드부터 출발
        pq.add(new Node(1, 0));
        
        long res = 0;
        int cnt = 0;
        while(!pq.isEmpty()) {
            
            Node edge = pq.poll();
            // 이미 확인한 정점이면 pass
            if(visited[edge.to]) continue;
            
            res += edge.weight;
            visited[edge.to] = true;
            // 모든 노드를 방문했다면 return
            if(++cnt == V) return res;
            
            for (int i = 0; i < adj[edge.to].size(); i++) {
                // 연결된 노드들 중 방문하지 않은 노드 찾기
                Node next = adj[edge.to].get(i); 
                if(visited[next.to]) continue;
                
                pq.add(next);
            }
        }
        
        return res;
    }
 
}