[알고리즘] 최소 스패닝 트리 ( MST : Minimum Spanning Tree )

 

◇  설명

  ◎  스패닝 트리
    :  그래프 G=(V,E) 에서, 정점 집합 V를 그대로 두고 간선을 |V|-1 개만 남겨 트리가 되도록 만든 것
    -  DFS와 BFS도 스패닝 트리
    -  사이클을 이루지 않고 모든 정점이 연결된 트리

  ◎  최소 스패닝 트리 ( Minimum Spaning Tree )
    :  간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리

  ◎  최소 스패닝 트리( Minimum Spanning Tree ) 문제
    :  가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리를 찾는 문제
    -  크루스칼 알고리즘  --  상호 배타적 집합( = 서로소 집합 ) 자료 구조의 좋은 사용 예
    -  크루스칼, 프림 알고리즘  --  간선이 하나도 없는 상태에서 시작해 하나씩 트리에 간선을 추가해 가는 탐욕적 알고리즘

  ∎  프림( Prim ) 알고리즘
    -  하나의 시작점으로 구성된 트리에 간선을 하나씩 추가하며 스패닝 트리가 될 때까지 키워 감
    -  항상 선택된 간선들은 중간 과정에서도 항상 연결된 트리를 이루게 됨
    -  이미 만들어진 트리에 인접한 간선만을 고려함
    -  우선순위 큐를 사용하지 않고 다익스트라 알고리즘을 구현한 것과 비슷한 형태를 가지고 있음
    -  정점 중심, 간선 수가 많은 그래프에 유리

  ∎  크루스칼( Kruskal ) 알고리즘
    -  그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 사이클을 이루지 않도록 유의하며 스패닝 트리에 하나씩 추가해 감.
    -  여기저기서 산발적으로 만들어진 트리의 조각들을 합쳐 스패닝 트리를 만듦
    -  간선 중심, 간선 수가 적은 그래프에 유리

 

◇  코드

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class Tree_minimum_spanning_list {
	
	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;
		}
	}
    
	// prim
	public static int spanning_prim( List<List<Node>> e, int n ) {
		int i, u, v, w, w_u, w_sum = 0, t = 0;
		boolean c[] = new boolean[n];
		int d[] = new int[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() && t < n ) {
			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;
			t++;
			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;
	}

	// kruskal
	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];  // make set
		for( i = 0; i < n; i++ )
			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 );  // 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[] ) {
		a = find( a, p );
		b = find( b, p );
		if( a != b ) 
			p[b] = a;
	}

	public static void main(String[] args) {
		
		int n = 3;
		
		// prim
		List<List<Node>> e = new LinkedList<>();
		for( int i = 0; i < n; i++ )
			e.add( new LinkedList<Node>() );
		e.get( 0 ).add( new Node( 0, 1, 1 ) );
		e.get( 1 ).add( new Node( 1, 0, 1 ) );
		e.get( 1 ).add( new Node( 1, 2, 2 ) );
		e.get( 2 ).add( new Node( 2, 1, 2 ) );
		e.get( 0 ).add( new Node( 0, 2, 3 ) );
		e.get( 2 ).add( new Node( 2, 0, 3 ) );
		System.out.println( spanning_prim( e, n ) );
        
		// kruskal
		PriorityQueue<Node> e = new PriorityQueue<>();	// edge
		e.add( new Node( 0, 1, 1 ) );
		e.add( new Node( 1, 0, 1 ) );
		e.add( new Node( 1, 2, 2 ) );
		e.add( new Node( 2, 1, 2 ) );
		e.add( new Node( 0, 2, 3 ) );
		e.add( new Node( 2, 0, 3 ) );
		System.out.println( spanning_kruskal( e, n ) );
		
	}
}

 

◇  출처

  -  설명  --  알고리즘 문제 해결 전략 ( 구종만 )
  -  코드  --  쉽게 배우는 알고리즘 ( 문병로 )