[백준(Baekjoon)][자바(java)] 1197 : 최소 스패닝 트리 / 최소 신장 트리

 

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

▶  프림  ( Prim )

import java.io.*;
import java.util.*;

public class Main {
	
	static class Path implements Comparable<Path> {
		int v, w;		// vertex num, weight from adjacnet vertex
		Path( int v, int w ) {
			this.v = v;
			this.w = w;
		}
		@Override
	    public int compareTo( Path o ) {
	        return w - o.w;
	    }	
	}
	
	static class Node {
		int u, v, w;	// vertex num, vertex_connected num, weight
		Node( int u, int v, int w ) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
	}
	
	public static int spanning_prim( List<List<Node>> e, int n ) {
		int i, u, v, w, w_u, w_sum = 0;
		int d[] = new int[n];
		boolean c[] = new boolean[n];
		for( i = 1; i < n; i++ )
			d[i] = Integer.MAX_VALUE; 
		PriorityQueue<Path> pq = new PriorityQueue<>();
		pq.add( new Path( 0, 0 ) );
		while( !pq.isEmpty() ) {
			Path p = pq.remove();
			u = p.v; w_u = p.w;
			if( d[u] < w_u ) continue;
			if( c[u] ) continue;
			c[u] = true;
			w_sum += w_u;
			for( Node nd : e.get(u) ) {
				v = nd.v;	// connected vertex num
				w = nd.w;	// connected weight
				if( d[v] > w && !c[v] ) {
					pq.add( new Path( v, w ) );
					d[v] = w;
				}
			}
		}
		return w_sum;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		int n, m, a, b, c, i;
		StringTokenizer st = new StringTokenizer( br.readLine() );
		n = Integer.parseInt( st.nextToken() );
		m = Integer.parseInt( st.nextToken() );
		List<List<Node>> e = new LinkedList<>(); // edge
		for( i = 0; i < n; i++ )
			e.add( new LinkedList<Node>() );
		for( i = 0; i < m; i++ ) {
			st = new StringTokenizer( br.readLine() );
			a = Integer.parseInt( st.nextToken() ) - 1;	// u
			b = Integer.parseInt( st.nextToken() ) - 1;	// v
			c = Integer.parseInt( st.nextToken() );		// w
			e.get( a ).add( new Node( a, b, c ) );
			e.get( b ).add( new Node( b, a, c ) );
		}
		br.close();
		System.out.println( spanning_prim( e, n ) );
        
	}
}

 

▶  크루스칼  ( Kruskal )

import java.io.*;
import java.util.*;

public class Main {

	static class Node implements Comparable<Node> {
		int u, v, w;	// vertex num, vertex_connected num, weight
		Node( int u, int v, int w ) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
		@Override
		public int compareTo( Node o ) {
			return w - o.w;
		}
	}
	
	public static int spanning_kruskal( PriorityQueue<Node> e, int n ) {
		int w_sum = 0, i, t = 0, u, v, w;
		int p[] = new int[n], r[] = new int[n];
		for( i = 0; i < n; i++ )  // make set
			p[i] = i;
		while( t < n-1 && !e.isEmpty() ) {
			Node nd = e.remove();
			u = nd.u; v = nd.v; w = nd.w;
			if( find( u, p ) != find( v, p ) ) {  // find set
				w_sum += w;
				union( u, v, p, r );  // union set
				t++;
			}
		}
		return w_sum;
	}
	public static int find( int n, int p[] ) {  // 경로 압축 최적화
		if( n == p[n] ) 
			return n;
		return p[n] = find( p[n], p );
	}
	public static void union( int a, int b, int p[], int r[] ) {  // 랭크를 이용한 최적화
		a = find( a, p );
		b = find( b, p );
		if( r[a] > r[b] )
			p[b] = a;
		else {
			p[a] = b; 
			if( r[a] == r[b] )
				r[b]++;
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		int n, m, a, b, c, i;
		StringTokenizer st = new StringTokenizer( br.readLine() );
		n = Integer.parseInt( st.nextToken() );
		m = Integer.parseInt( st.nextToken() );
		PriorityQueue<Node> e = new PriorityQueue<>(); // edge
		for( i = 0; i < m; i++ ) {
			st = new StringTokenizer( br.readLine() );
			a = Integer.parseInt( st.nextToken() ) - 1;	// u
			b = Integer.parseInt( st.nextToken() ) - 1;	// v
			c = Integer.parseInt( st.nextToken() );		// w
			e.add( new Node( a, b, c ) );
		}
		br.close();
		System.out.println( spanning_kruskal( e, n ) );
		
	}
}

 

*  최소 스패닝 트리
-  정점 번호 입력받을 때 1씩 뺌
-  프림 알고리즘은 앞서 다룬 다익스트라 알고리즘과 유사함
-  크루스칼 알고리즘은 앞서 다룬 유니온-파인드 이용

 

 

※  최소 스패닝 트리  ( Minimum Spanning Tree )

 -  신장 트리인 그래프 중 전체 가중치의 합이 최소가 되는 신장 트리
 -  n-1 개의 간선만을 이용.
 -  순환 경로( 사이클( cycle ) ) 없음

#  프림( Prim ) 알고리즘

 -  시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법  
  ( 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장해 나감 )
-  정점 중심
-  간선 수가 많은 그래프에 유리

#  크루스칼( Kruskal ) 알고리즘

 -  간선 중심
 -  간선 수가 적은 그래프에 유리