개념

• 모든 노드를 덮었고, 간선갯수 = 노드개수-1
• input graph
  
• spaning tree는 이 input그래프를 바탕으로 사이클이 없는 트리를 만들어내는 것
• 하나의 input 그래프에선 여러개의 spanning tree가 나올 수 있다
• input tree: 방향없고, 가중치 있음, 모든요소가 연결되어있음
• cost: 선분에 대한 값들의 합

최소 신장 트리를 구하는 방법

1. 프림 알고리즘
2. 크루스칼 알고리즘

프림 알고리즘

1. 시작정점만 포함한다.
2. 인접정점중 최소간선으로 연결된 정점만을선택한다
3. 2번 내용 반복

import java.awt.print.Pageable;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.*;
import java.io.*;

public class Main{
    public static class Heap {
        Node[] heap;
        int hCnt=0;

        public Heap(int n) {
            heap = new Node[n];
        }

        public void push(Node x) {
            heap[++hCnt]=x;
            int idx = hCnt;
            while (idx>1 && heap[idx/2].compareTo(heap[idx])>0) {
                if (idx==1 || heap[idx].compareTo(heap[idx/2])>0)
                    break;
                Node tmp = heap[idx/2];
                heap[idx/2]=heap[idx];
                heap[idx]=tmp;
                idx/=2;
            }
        }
        public boolean isEmpty(){
            return hCnt==0;
        }

        public Node pop() {
            Node pop = heap[1];
            heap[1] = heap[hCnt--];
            int idx =1;
            int next;
            while (true) {
                next = idx*2;
                if (next<hCnt && heap[next].compareTo(heap[next+1])>0)
                    next++;
                if (next>hCnt || heap[next].compareTo(heap[idx])>0)
                    break;
                Node tmp = heap[idx];
                heap[idx]=heap[next];
                heap[next]=tmp;
                idx=next;
            }
            return pop;
        }
    }
    static class Node implements Comparable<Node> {
        int index;
        int w;
        Node(int index, int w){
            this.index = index;
            this.w = w;
        }
        @Override
        //이거 순서 중요
        public int compareTo(Node o) {
            return Integer.compare(w, o.w);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input[] = br.readLine().split(" ");
        int v = Integer.parseInt(input[0]);
        int e = Integer.parseInt(input[1]);
        boolean visited[] = new boolean[v+1];
        List<Node> adjacentNode[] = new List[v+1];//list<Node>가 [v+1]개 생성되는 것!
        for(int i=0;i<v+1;i++){
            adjacentNode[i] = new ArrayList<>();
        }

        for (int k =0;k<e;k++) {
            String infos[] = br.readLine().split(" ");
            adjacentNode[Integer.parseInt(infos[0])].add(new Node(Integer.parseInt(infos[1]), Integer.parseInt(infos[2])));

            adjacentNode[Integer.parseInt(infos[1])].add(new Node(Integer.parseInt(infos[0]), Integer.parseInt(infos[2])));
        }
        Heap pq = new Heap(1000000);
        long result = 0;
        int count =0;
        pq.push(new Node(1,0));
        while(!pq.isEmpty()){
            Node current = pq.pop();
            if(visited[current.index]) continue;
            //방문안한것들만
            visited[current.index] = true;
            result += current.w;
            count++;
            if(count == v) {
                System.out.println(result);
                break;
            }
            for (Node node: adjacentNode[current.index]) {
                pq.push(node);
            }
        }


    }


}

크루스칼 알고리즘

1. 간선중에 가중치가 큰 순서대로 정렬한다
2. 사이클이 안만들어지는 선에서 계속 합친다

import java.awt.print.Pageable;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.*;
import java.io.*;
import java.util.stream.Collectors;

public class Main{
    static class Edge implements Comparable<Edge>{
        public int e1;
        public int e2;
        public int w;
        Edge(int e1, int e2, int w){
            this.e1 = e1;
            this.e2= e2;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(w, o.w);
        }
    }
    static class Disjoint{
        int p[];
        int rank[];
        Disjoint(int n){
            p = new int[n];
            rank = new int[n];
            for(int i=0;i<n;i++){
                p[i] = i;
            }
        }
        public void makeSet(int u){
            p[u] = u;
            rank[u] = 0;
        }
        public int findSet(int u){
            if(p[u]==u) return u;
            else return p[u] = findSet(p[u]);
        }
        public void union(int u, int v){
            //p[u] = findSet(v);
            u = findSet(u);
            v = findSet(v);
            if(rank[u] > rank[v]) p[v] = u;
            else{
                p[u] = v;
                if(rank[u]==rank[v]){
                    rank[v]++;
                }
            }

        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int v = Integer.parseInt(br.readLine());
        int e = Integer.parseInt(br.readLine());
        Disjoint disjoint = new Disjoint(v+1);
        
        List<Edge> edgeList = new ArrayList<>();
         for (int k =0;k<e;k++) {
            String infos[] = br.readLine().split(" ");
            edgeList.add(new Edge(Integer.parseInt(infos[0]), Integer.parseInt(infos[1]), Integer.parseInt(infos[2])));
          }

         //toList쓰면 안됨
       Collections.sort(edgeList);

        int result = 0;
        while (!edgeList.isEmpty()){
            Edge edge = edgeList.remove(0);
            if(disjoint.findSet(edge.e1)!=disjoint.findSet(edge.e2)){
                disjoint.union(edge.e1, edge.e2);
                result+=edge.w;
            }
        }
        System.out.println(result);


    }


}

---

출처
https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html