15-2. 최소신장트리

02. 최소신장트리

최소신장 트리의 정의

트리 : 사이클이 없는 단순 그래프

-> 트리는 그래프이기는 하지만 루트를 가지기 때문에 (일반 그래프에는 없는)계층 개념이 있고, 사이클이 없어서 한 정점에서 다른 정점으로 가는 경로가 유일한 독특한 구조

 

신장 트리(spanningtree) : 그래프 G의 모든 정점과 간선의 일부(또는 전부)를 포함하는 트리

-> 주어진 그래프의 정점을 모두 포함함

-> 최소 n-1개의 간선으로 구성한 그래프

 

- G 의 최소 부분 그래프 : 그래프 G의 부분 그래프 중에서 간선의 수가 가장 작은 것

 

프림(Prim)알고리즘

- n개의 정점을 갖는 연결 그래프 G에 대한 최소 비용 신장 트리 T를 구하는 알고리즘

- 그래프 전체에서 최소 비용을 갖는 간선 { u, v }를 선택하여 이 간선을 최소 비용 신장 트리 T에 추가함

     - > 이 간선을 최소 비용 신장 트리 T에 추가하였을 때 사이클을 형성하지 않으면 T에 추가하고 아니면 무시함

void prim(){ 
	T =φ； 
    W =φ； 
    E 로부터 최소 비용인 간선 { v, w }를 선택 ;
	while(T는 n-1개 이하의 간선 포함 &&E는 공집합 아님){ 
    	E 에서 간선 {v, w}를 제거 ;
		if({v, w}가 T 내에서 사이클을 생성 안함){ 
        	T = T ∪ v, w}}; //선택한 간선 추가 
        	W = W ∪ v, w}; //선택한 정점 추가 
            }
		  else 간선 {v, w}를 버림 ; 
       	E 로부터 W내의 정점과 최소 비용으로 연결된 간선 { v, w }를 선택 ;  }  }

 

크루스컬(Kruskal)알고리즘

- 남은 간선 중에서 무조건 최소 비용인 간선을 선택 한 후 사이클을 형성하지 않으면 그 간선을 선택함

- 중간 과정에 있는 T는 하나의 트리가 아니고 여러 개의 분리된 트리, 즉 숲일 수 있음

void kruskal(){
  while(T 가 n-1개 이하의 간선을 포함 && E 가 공집합 아님) 
  {
    E 로부터 최소 비용인 간선 { v,w }를 선택; 
    E 에서 간선 { v,w }를 제거;
	if({ v,w }가 T 내에서 사이클을 생성 하지 않음) 
      T = T ∪ v,w } };
	else
		간선 {v,w}를 버림;  }  }

 

솔린(Sollin)알고리즘

간선이 하나도 없는 그래프의 모든 정점들로 구성된 숲에서 시작함

-> 단계가 거듭되면서 숲 내의 트리들이 최소 비용을 갖는 간선으로 연결

void sollin(){
#집합 E의 초기 상태는 주어진 그래프의 간선 집합
#집합 F의 초기 상태는 그래프의 모든 정점들로 구성된 간선이 없는 숲

  T =φ;
	while(T는 완전한 하나의 트리가 아님 && E 는 공집합이 아님){
	  for(F내의 각각의 트리 T 에 대하여){
		T 와 다른 트리를 연결하는 E의 간선 {,}중에서 최소비용 간선{,} 선택 ;
		T = T ∪ {,}};
		E에서 간선 {,}를 제거 ;
		}
	  T에 새로 추가된 간선을 포함하여 F를 수정 ;
	}