<Algorithm> 49. 1197번 최소 스패닝 트리(Kruskal & prim)

1197번 최소 스패닝 트리(MST)

• MST는 모든 노드가 사이클 없이 최소 비용으로 모두 연결된 트리를 말한다. 간선은 Vertex - 1이 된다.
• MST 알고리즘에는 Kruskal 알고리즘과 Prim 알고리즘이 있다.
• Kruskal 알고리즘은 Edge들의 가중치로 오름차순으로 정렬하고 가장 적은 간선을 선택한다. 이때 사이클이 발생하면 선택하지않는다.
• Prim 알고리즘은 다익스트라처럼 해당 정점의 인접 정점을 탐색하고 업데이트 한 뒤 가장 최저비용을 선택한다.
• 다익스트라는 최단경로이고 Prim은 각 정점들을 N-1개의 간선으로만 구성되는 그래프를 만드는 것에 차이가 존재한다.
• 또한 다익스트라는 경로를 누적하지만 Prim은 경로의 가중치를 누적하지 않는다

Prim

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class PrimMain {
    static int[] dist;
    static int total = 0;
    static boolean[] visited;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken())+1;
        int M = Integer.parseInt(st.nextToken());
        dist = new int[N];
        visited = new boolean[N];
        ArrayList<Edge>[] alists = new ArrayList[N];
        for(int i = 0 ; i < N; i ++) {
            alists[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < M; i ++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            alists[a].add(new Edge(b,w));
            alists[b].add(new Edge(a,w));
            // 양방향으로 설정
        }
        
        prim(alists);
        
        int k = 0;
        for(int i = 1 ; i < N ; i ++) {
            k += dist[i];
        }
        System.out.println(k);
    }
    public static void prim(ArrayList<Edge>[] alist) {
        
        int startVertex = 1; // 시작정점 
        
        PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weigth - o2.weigth;
            }
        });
        
        for(int  i = 0; i < alist.length ; i++)
            dist[i] = Integer.MAX_VALUE;
        
        dist[startVertex] = 0;
    
        pq.add(new Edge(startVertex, dist[startVertex]));
        
        while(!pq.isEmpty()) {
            Edge edge = pq.poll();
            int vertex = edge.vertex;
            
            if(visited[vertex]) continue;
            visited[vertex] = true;
            
            for(Edge e: alist[vertex]) {
                
                if(!visited[e.vertex]) { 
                    // 이미 방문한 지점은 선으로 연결된 것이라고 할 수 있다.
                    // 거기에 양방향으로 설정했기 때문에 이미 방문한 지점은 한번더 처리해 주어야 한다!!
                    int destination = e.vertex;
                    int layoverWeight = e.weigth;
                    // 최단경로가 아닌 전체적인 최소비용 트리를 만들어야 하기 때문에
                    // 이미 방문한 지점부터의 인접 지점까지 해당 가중치만을 비교한다.  
                    if(dist[destination] > layoverWeight) {
                            dist[destination] = layoverWeight;
                            pq.add(new Edge(destination, dist[destination]));
                        }
                }
            }
            
        }
    }
    
                        
}
class Edge{
    int vertex;
    int weigth;
    public Edge(int vertex, int weigth) {
        super();
        this.vertex = vertex;
        this.weigth = weigth;
    }
}

   

 

Kruskal

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static int parent[] = new int[100002];
    static int total = 0;
    
    private static boolean union(int i, int j) {
        
        int iroot = find(i);
        int jroot = find(j);
        if(iroot == jroot) return false;
        // 사이클 발생 -> 연결안함
        
        parent[jroot] = iroot;
        return true;
        // 노드 연결
        
    }
    private static int find(int i) {
        if(parent[i] != i) {
            return find(parent[i]);
        }
        return parent[i];
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        ArrayList<Node> aList = new ArrayList<>();
        
        for(int i = 0; i < N ; i++) {
            parent[i] = i;
        }
        
        for(int i = 0; i < M; i ++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            Node node = new Node(a, b, w);
            aList.add(node);
        }
        
        Collections.sort(aList, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                // TODO Auto-generated method stub
                return o1.w - o2.w;
            }
        });
                
        for(int i = 0; i < M; i ++) {
            if(union(aList.get(i).a, aList.get(i).b)) {
                
                total += aList.get(i).w; // 노드가 연결되면 가중치 Up
            }
            
        }
        System.out.println(total);
    }
}
class Node{
    int a;
    int b;
    int w;
    public Node(int a, int b, int w) {
        super();
        this.a = a;
        this.b = b;
        this.w = w;
    }
}