MST(최소신장트리) - 크루스칼 & 프림 알고리즘

최소신장트리(MST / Minimum Spanning Tree)는 방향성이 없는 가중 그래프에서 간선의 가중치의 합이 최소인 신장 트리이다. 

 

 

 

🕹️ 크루스칼 알고리즘 & 프림 알고리즘 과정 

 

🔹 크루스칼 알고리즘 : 간선 중심으로 최소 신장 트리 구하기 (간선의 개수가 적다면 프림보다 효율적 !)

1. 간선들의 가중치를 오름차순으로 정렬한 후 가중치가 낮은 간선부터 선택한다.
2. 선택한 간선으로 인해 사이클이 형성된다면 다음 간선으로 넘어가고, 사이클이 형성되지 않는다면 해당 간선을 선택한다. ➔ 사이클이 형성되는지 파악하기 위해 Union-Find 연산을 진행한다. 
3. 정점이 N개인 그래프일 때, N-1개의 간선을 선택했다면 반복문을 종료한다.

 

🔹 프림 알고리즘 : 정점 중심으로 최소 신장 트리 구하기 (정점의 개수가 적다면 크루스칼보다 효율적 !)

1. 임의의 정점을 선택한다.
2. 선택한 정점과 연결된 간선들 중에서 가중치가 낮은 간선을 선택한다. 
3. 모든 정점이 선택될 때까지 반복한다. ➔ 정점을 방문했는지 여부를 파악하기 위해 boolean[] visit을 사용한다. 

 

 

👩‍💻 크루스칼 알고리즘 코드 구현 

public class BOJ_1197_최소스패닝트리 {

    static int[] parent;
    static int v,e;
    static PriorityQueue<Node> pq;
    
    // 가중치를 오름차순으로 정렬 ➔ PriorityQueue 사용
    static class Node implements Comparable<Node>{
        int from, to, weight;

        public Node(int from, int to, int weight){
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
        public int compareTo(Node n){
            return this.weight-n.weight;
        }
    }

	/*
    	Union-Find 연산 
    */
    static void union(int x, int y){

        x = find(x);
        y = find(y);

        if(x!=y){
            parent[y]=x;
        }
    }

    static int find(int x){

        if(parent[x]==x) return x;
        return parent[x]=find(parent[x]);
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        pq = new PriorityQueue<>();
        parent = new int[v+1];

		// 부모를 본인으로 일단 초기화 
        for(int i=1; i<=v; i++){
            parent[i] = i;
        }

        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());

            pq.add(new Node(a,b,c));
        }

        int sum=0;

        while(!pq.isEmpty()){
            Node now = pq.poll();

			// 만약 사이클을 형성한다면 (부모가 같다면) 넘어가기 
            if(find(now.from)==find(now.to)) continue;
            
            // 형성하지 않는다면 선택 
            sum+=now.weight;
            union(now.from, now.to);
        }
        System.out.println(sum);
    }
}

 

 

 

👩‍💻 프림 알고리즘 코드 구현 

public class BOJ_1197_최소스패닝트리 {

    static boolean[] visit;
    static int v,e;
    static ArrayList<Node>[] list;
    
    static class Node implements Comparable<Node>{
        int from, to, weight;

        public Node(int from, int to, int weight){
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
        public int compareTo(Node n){
            return this.weight-n.weight;
        }
    }
  
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        
        list = new ArrayList[v+1];
        visit = new boolean[v+1];
        
        for(int i=1; i<=v; i++){
        	list[i] = new ArrayList<>();
        }

        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());

            list[a].add(new Node(a, b, c));
            list[b].add(new Node(a, b, c));
        }
        
        PriorityQueue<Node> pq = new PriorityQueue<>(); // 우선순위 큐 (최소 힙) 사용
        pq.add(new Node(0, 1, 0));
        
        int ans=0;
        
        while(!pq.isEmpty()){
        	Node node = pq.poll();
            
            if(visit[node.b]) continue;
            visit[node.b] = true;
            ans+=node.weight;
            
            // 현재 정점에 연결된 다른 정점들 탐색
            for(Node next : list[node.b]){
            	if(!visit[next.b]) pq.add(next);
            }
        }
		System.out.println(ans);
	}
}