최소 신장 트리

가중 그래프

• 가중 그래프(weighted graph): 각 간선이 무게(weight)라 부르는 수치값을 가지는 그래프
• 무게: 거리, 비용, 시간 등
• ex) 오른편 철도 그래프에서, 간선의 무게는 양끝점 역간의 여행거리(km)를 표현

 

최소 신장 트리

• 신장 부그래프(spanning subgraph)
  
  • 그래프 G의 모든 정점들을 포함하는 부그래프
• 신장 트리(spanning tree)
  
  • (자유) 트리인 신장 부그래프
• 최소 신장 트리(minimum spanning tree, MST)
  
  • 가중 그래프의 총 간선 무게가 최소인 신장트리
• 응용
  
  • 통신망
  • 교통망
• 속성
  • 싸이클 속성
  • 분할 속성
  • 최소신장트리 알고리즘의 정확성 검증에 이용

 

싸이클 속성

• 싸이클 속성
  
  • T를 가중그래프 G의 최소신장트리라 하자
  • e를 T에 존재하지 않는 G의 간선으로, C를 e를 T에 추가하여 형성된 싸이클로 가정
  • 그러면 C의 모든 간선 f에 대해,  weight(f)  weight(e)
• 증명
  
  • 모순법
  • 만약 weight(f) > weight(e)라면, f를 e로 대체함으로써 무게가 더 작은 신장트리를 얻을 수 있기 때문

 

분할 속성

• 분할 속성
  
  • G의 정점들을 두 개의 부분집합 U와 V로 분할한다고 하자
  • e를 분할을 가로지르는 최소 무게의 간선이라고 하자
  • 간선 e를 포함하는 G의 최소신장트리가 반드시 존재
• 증명
  • T를 G의 MST라 하자
  • 만약 T가 e를 포함하지 않는다면, e를 T에 추가하여 형성된 싸이클 C를 구성하는 간선들 가운데 분할을 가로지르
  • 는 간선 f가 존재
  • 싸이클 속성에 의해, weight(f) ≤ weight(e) 
  • 그러므로, weight(f) = weight(e)
  • f를 e로 대체하면 또 하나의 MST를 얻을 수 있다

 

탐욕법

• 탐욕법(greedy method): 일반적인 알고리즘 설계 기법 가운데 하나 – 다음 요소에 기초하여 설계
  
  • 구성(configuration): 다양한 선택, 모음, 또는 찾아야 할 값들
  • 목표(objective): 구성에 할당된 점수가 존재하며, 이를 최대화 또는 최소화해야 하는 상황
• 탐욕적 선택 속성(greedy-choice property)을 가진 문제에 적용할 경우 가장 잘 맞는다
  
  • 출발 구성으로부터 시작하여 지속적인 지역적 향상을 통해 전체 최적해를 항상 찾을 수 있다
• 예
  
  • 잔돈 거스르기
  • 부분적 배낭 문제(the fractional knapsack problem)
  • 최소신장트리 문제(minimum spanning trees)

 

최소 신장 트리 알고리즘

• Prim-Jarnik 알고리즘
• Kruskal 알고리즘
• Baruvka 알고리즘

 

Prim-Jarnik 알고리즘

• 탐욕 알고리즘
• 대상: 단순 연결 무방향 가중그래프
• 임의의 정점 s를 택하여, s로부터 시작하여 정점들을 (가상의) 배낭에 넣어가며 배낭 안에서 MST T를 키워 나간다 – s는 T의 루트가 된다
• 각 정점 v에 라벨 d(v)를 정의 – d(v)는 배낭 안의 정점과 배낭 밖의 정점을 연결하는 간선의 무게
• 반복의 각 회전에서:
  
  • 배낭 밖의 정점들 가운데 최소 d(z) 라벨을 가진 정점 z를 배낭에 넣는다
  • z에 인접한 정점들의 라벨을 갱신
• 배낭 밖의 정점들을 우선순위 큐에 저장
  
  • 키: 거리
  • 원소: 정점
• 보조 메쏘드
  
  • Q.replaceKey(e, k): 원소 e의 키를 k로 변경하고 우선순위 큐 Q 내의 e의 위치를 갱신
• 각 정점 v에 세 개의 라벨을 저장
  
  • 거리(distance): d(v)
  • 위치자(locator): 우선순위 큐에서의 v의 위치
  • 부모(parent): p(v), MST에서 v의 부모를 향한 간선

Alg PrimJarnikMST(G)
	input a simple connected weighted graph G with n vertices and m edges
	output an MST T for G

1. for each v E G.vertices()
		d(v) <- 무한대
		p(v) <- 공집합
2. s <- a vertex of G
3. d(s) <- 0
4. Q <- a priority queue containing all the 	vertices of G using d labels as keys
5. while (!Q.isEmpty())
		{pull a vertex into the sack}
 		u <- Q.removeMin() 
		for each e E G.incidentEdges(u)
			z <- G.opposite(u, e)
			if  ((z E Q) & (w(u, z) < d(z)))
				d(z) <- w(u, z)
				p(z) <- e
                Q.replaceKey(z, w(u, z))

 

 

Prim-Jarnik 알고리즘 정확성

• Prim-Jarnik 알고리즘은 반복의 각 회전에서 항상 배낭 C 안의 정점을 배낭 C 밖의 정점과 이어주는 최소 무게의 간선을 선택하므로, MST에 항상 타당한 간선을 추가한다
• 따라서 최소신장트리에 관한 분할 속성의 요건을 만족

 

Prim-Jarnik 알고리즘 분석

• 그래프 작업
  
  • 메쏘드 incidentEdges는 각 정점에 대해 한번 호출
• 라벨 작업
  
  • 정점 z의 거리, 부모, 위치자 라벨을 O(deg(z)) 시간 읽고 쓴다
  • 라벨을 읽고 쓰는데 O(1) 시간 소요
• 우선순위 큐 (힙으로 구현할 경우) 작업
  
  • 각 정점은 우선순위 큐에 한번 삽입되고 한번 삭제: 삽입과 삭제에 각각 O(log n) 시간 소요
  • 우선순위 큐 내의 정점 w의 키는 최대 deg(w)번 변경: 각 키 변경에 O(log n) 시간 소요 
• 그래프가 인접리스트 구조로 표현되어 있다면, Prim-Jarnik 알고리즘은 O((n + m) log n) 시간에 수행
  
  • 참고: deg(v)의 합 = 2m
• 단순 연결그래프에서 n = O(m)이므로, 실행시간: O(m log n)

 

Kruskal 알고리즘

• 탐욕 알고리즘
• 알고리즘을 위한 초기 작업
  
  • 모든 정점을 각각의 독자적인 (실제의) 배낭에 넣는다
  • 배낭 밖의 간선들을 우선순위 큐에 저장
    
    • 키: 무게
    • 원소: 간선
  • 비어 있는 MST T를 초기화
• 반복의 각 회전에서:
  
  • 두 개의 다른 배낭 속에 양끝점을 가진 최소 무게의 간선을 MST T에 포함하고 두 배낭을 하나로 합친다
• 반복이 완료되면:
  
  • MST T를 포함하는 한 개의 배낭만 남는다

Alg KruskalMST(G)
	input a simple connected weighted graph G with n vertices and m edges
	output an MST T for G

1. for each v E G.vertices()
		define a Sack(v) <- {v}
2. Q <- a priority queue containing all the edges of G using weights as keys
3. T <- 공집합
4. while (T has fewer than n – 1 edges)		
        (u, v) <- Q.removeMin()
		if (Sack(u) ≠ Sack(v))
			Add edge (u, v) to T
			Merge Sack(u) and Sack(v)
5. return T

 

 

 

Kruskal 알고리즘 정확성

• Kruskal 알고리즘의 정확성은 분할 속성으로부터 유도
• Kruskal 알고리즘은 반복의 회전마다 간선 (u, v)를 MST T에 추가
• 이때 정점 집합 V가 u를 포함하는 배낭 V1과, V1에 속하지 않은 나머지 정점들을 모두 포함하는 배낭 V2로 분할되었다고 보면, 이는 모든 정점이 두 부분으로 분리된 분할 상태
• Q로부터 간선들을 무게 순서로 추출하고 있으므로, (u, v)는 양끝점이 각각 V1과 V2에 속한 최소 무게의 간선
• 따라서, Kruskal 알고리즘은 항상 타당한 MST 간선을 추가한다

 

Kruskal 알고리즘을 구현하기 위한 데이터 구조

• Kruskal 알고리즘은 인접 정보를 사용하지 않는다
  
  • 인접 정보(부착리스트 또는 인접행렬)가 생략된, 즉 간선리스트 구조로 표현된 그래프에서 수행 가능
• Kruskal 알고리즘은 트리들의 숲을 유지
  
  • 각 트리들을 리스트로 구현된 분리집합에 저장하고 각 원소에 소속 집합을 가리키는 참조를 저장
    
    • 작업 find(u)는 u가 소속된 집합을 반환: O(1) 시간 소요
    • 작업 union(u, v)은 크기가 작은 집합의 원소들을 큰 집합 리스트로 옮기며 원소들의 참조를 갱신: O(min(nu, nv)) 시간 소요 – 여기서 nu와 nv는 각각 u와 v를 저장한 집합의 크기 

 

분리집합에 기초한 Kruskal 알고리즘

• Kruskal 알고리즘의 분리집합에 기초한 버전은 find로 소속 집합 검사를, union으로 배낭 합치기를 수행 

Alg KruskalMST-DisjointSets(G)
	input A simple connected weighted graph G with n vertices and m edges
	output An MST T for G

1. Let D be a disjoint set of the vertices of G, where each vertex forms a separate set
2. Let Q be a priority queue storing the edges 	of G, sorted by their weights
3. Let T be an initially-empty tree
4. while (!Q.isEmpty())
	    (u, v) <- Q.removeMin()
	    if (D.find(u) ≠ D.find(v))
			Add (u, v) to T
			D.union(u, v)
5. return T

 

 

Kruskal 알고리즘 분석

• 우선순위 큐 초기화 작업
  
  • 힙을 사용하여 우선순위 큐 Q를 구현하면, 반복적인 삽입 방식에 의해서는 O(m log m) 시간에, 상향식 힙 생성 방식에 의해서는 O(m) 시간에 Q 생성 가능
• 반복의 각 회전에서
  
  • 최소 무게의 간선을 O(log m) 시간에 삭제 가능 – 여기서, G가 단순그래프이므로, O(log m) = O(log n)
  • 각 배낭을 위한 분리집합을 리스트로 구현하면, find(u) ≠ find(v) 검사에 O(1) 시간
  • 두 개의 배낭 Sack(u), Sack(v)를 합치는데 O(min(Sack(u), Sack(v))) 시간 – 원소가 새 배낭으로 합쳐질 때마다 최소 두 배 크기의 배낭으로 합쳐지므로, 각 원소는 최대 log n번 이동 – 이를 모든 정점에 대해 누적하면 O(n log n)
• 총 반복 회수: 최악의 경우 m번
• 그러므로 Kruskal 알고리즘은 O((n + m)log n) 시간에 수행
• G가 단순 연결그래프인 경우 n = O(m)이므로, 실행시간은 O(m log n)

 

Baruvka 알고리즘

• a.k.a. Sollin 알고리즘
• Kruskal이나 Prim-Jarnik 알고리즘과 달리, 우선순위 큐를 사용하지 않는다
• Kruskal 알고리즘과 마찬가지로, Baruvka 알고리즘도 모든 정점을 각각의 독자적인 (실제의) 배낭에 넣고 시작
• Kruskal이나 Prim-Jarnik 알고리즘이 반복의 각 회전에서 한 개의 간선을 취함으로써 배낭을 키워 나가는 것과 달리, 한꺼번에 여러 개의 간선을 취하여 여러 수의 배낭을 동시에 키워 나감

Alg BaruvkaMST(G)
	input A simple connected weighted graph G = (V, E) with n vertices and m edges
	output An MST T for G

1. T <- V {just the vertices of G}
2. while (T has fewer than n – 1 edges)
		for each connected component Ci in T
			Let edge e be the smallest-weight edge from Ci to another component in T
			if (e is not already in T)
				Add edge e to T
3. return T

 

 

Baruvka 알고리즘 정확성

• Baruvka 알고리즘 반복의 각 단계에서는, 현재의 MST T의 각 연결요소 Ci 사이를 교차하는 최소 무게의 간선들을 취한다
• 여기서 V가 Ci에 속한 정점들과, Ci 바깥의 정점들로 분할되었다고 가정하면,
• Ci를 위해 선택된 간선 e는 e가 MST에 반드시 포함되어야 한다는 MST에 관한 분할 속성의 요건을 만족
• 따라서 반복의 각 단계에서 취해지는 간선들은 모두 타당한 선택이 된다

 

Baruvka 알고리즘 구현

• 간선 삽입에 따른 연결요소(트리)들의 숲을 유지: 인접리스트를 사용하면 O(1) 시간에 처리 가능
• 연결요소들을 찾기 위해 숲을 순회: DFS를 사용하면 O(n) 시간에 수행 가능
• 정점이 소속된 연결요소 표시: 각 정점에 라벨 정의하여 표시
• 연결요소 Ci에 인접한 최소 무게의 간선 찾기: 그래프 G의 인접리스트에서 Ci에 속한 정점들을 조사

 

Baruvka 알고리즘 분석

• 반복의 각 회전에서
  
  • 각 연결요소 Ci 사이를 교차하는 최소 무게의 간선들을 찾기 위해, 각 Ci의 인접리스트를 전면적으로 탐색
    
    • 이때 그래프 G의 모든 간선 (v, u)를, (각 정점은 자신이 소속된 연결요소 라벨을 가지므로) 한 번은 v에 대해 또 한 번은 u에 대해, 합계 두 번 조사하므로 총 O(m) 시간 소요
• 모든 정점을 재라벨: O(n)
• T의 모든 간선을 순회: O(n)
• 따라서 반복 1회전의 수행 시간은 O(m) (∵n ≤ m)
• 반복회수
  
  • 반복의 각 회전에서, 각 배낭으로부터 나오는 하나의 간선을 고르고, 각각의 새로운 연결요소들을 합쳐 새 배낭을 만든다
  • 즉, 각각의 기존 배낭이 최소 한 개의 다른 기존 배낭과 합쳐진다
  • 따라서 반복의 회전마다 배낭의 총수는 최소 절반으로 줄어든다
  • 따라서 총 반복회수: O(log n)
• 그러므로 Baruvka 알고리즘의 실행시간: O(m log n)