2024. 1. 14. 20:40ㆍ프로그래밍 공부/Data Structure
13.4 방향 그래프
이 절에서는 방향 그래프와 관련된 문제를 다룬다.
방향 그래프(디그래프,digraph)는 간선이 모두 방향인 그래프임을 기억하라.
간선 방향을 처리하는 방법
그래프의 일부 또는 모든 간선이 향하는 것을 허용할 때,
간선 방향을 다루기 위해서 우리는 그래프 ADT에 다음 두 가지 메소드를 추가해야 한다.
isDirected(e): 간선 e가 방향을 잡는지 여부를 테스트한다.
insertDirectedEdge(v, w, o):
원점 v 및 목적지 w와 저장 요소 o가 있는 새로운 방향이 있는 간선을 삽입하고 반환한다.
또한, 간선 e이 방향이 있는 경우,
endVertice(e) 메서드는 A[0]이 e의 원점이고 A[1]이 e의 목적지가 되도록 배열 A를 반환해야 한다.
메소드 Idirected(e)의 실행 시간은 O(1)이어야 하며,
메소드 insertDirectedEdge(v, w, o)의 실행 시간은 방향이 없는 간선 삽입의 실행 시간과 일치해야 한다.
도달가능성
도달 가능성(reachability): 방향 그래프에서 어디에 도달할 수 있는지를 결정하는 것을 다룬다.
방향 그래프에서 순회는 항상 방향 경로를 따른다.
방향 경로(directed path): 모든 간선이 각각의 방향에 따라 통과하는 경로
그래프의 정점 u와 v가 주어졌을 때, u에서 v로 향하는 방향 경로가 있으면 u는 v에 도달한다고 한다.
또한 v가 간선의 원점 정점 w에 도달하면 정점 v는 간선 (w,z)에 도달한다고 한다.
만약 G의 임의의 두 꼭짓점 u와 v에 대하여 u가 v에 이르고 v가 u에 도달한다면
→ 방향그래프 G는 강하게 연결된다(strongly connected).
G의 방향 사이클(directed cycle): 모든 간선들이 각각의 방향에 따라 순회하는 사이클
(G는 같은 꼭짓점 쌍 사이에서 서로 반대 방향을 가지는 두 간선으로 구성된 사이클을 가질 수 있다.)
방향 그래프 G가 방향이 있는 사이클을 가지 않은 경우 → 방향그래프 G는 비순환적(acyclic)
(몇 가지 예는 그림 13.8 참조)
그래프 G의 transitive closure: G*의 정점들이 G의 정점들과 같도록 하는 방향 그래프 G*
G가 u에서 v로의 방향 경로를 가질 때마다 G*는 간선 (u, v)을 갖는다.
= 방향그래프 G로 시작하여 각 u와 v에 대하여 v가 u에서 도달할 수 있고
(G에 이미 간선 (u, v)가 존재하지 않도록) 추가 간선 (u, v)를 추가함으로써 G*를 정의한다.
그림 13.8: 방향 그래프에서 도달 가능성의 예:
(a) BOS에서 LAX로 향하는 방향 경로는 파란색으로 그려진다.
(b) 방향 주기(ORD, MIA, DFW, LAX, ORD)는 파란색으로 표시되고,
그 정점은 강하게 연결된 하위 그래프를 유도한다.
(c) ORD에서 도달 가능한 정점 및 간선의 하위 그래프는 파란색으로 표시된다.
(d) 점선으로 표시된 파란색 간선을 제거하면 비순환 방향 그래프가 된다.
그래프에서 도달 가능성을 다루는 흥미로운 문제는 다음과 같다:
• 정점 u와 v가 주어졌을 때, u가 v에 도달하는지 여부를 결정하라.
• 주어진 정점에서 도달할 수 있는 G의 모든 정점을 찾아라.
• G가 강하게 연결되어 있는지 확인한다.
• G가 비순환적인지를 결정한다.
• G의 transitive closure G*를 계산하라.
이 절의 나머지 부분에서는 이러한 문제를 해결하기 위한 몇 가지 효율적인 알고리즘에 대해 알아본다.
13.4.1 방향 그래프 순회
무향 그래프와 마찬가지로 무향 그래프에 대해
이전에 정의된 깊이 우선 검색(DFS) 및 너비 우선 검색(BFS) 알고리즘과 유사한 방법으로
체계적인 방법으로 방향 그래프를 탐색할 수 있다(섹션 13.3.1 및 섹션 13.3.3).
예를 들어, 이러한 탐색은 도달 가능성 질문에 답하는 데 사용할 수 있다.
이러한 탐색을 수행하기 위해
이 섹션에서 개발하는 방향 그래프의 깊이 우선 검색 및 너비 우선 검색 방법은
무향 그래프의 대응 방법과 매우 유사하다.
사실, 유일한 실제 차이는 지향된 깊이 우선 탐색 및 너비 우선 탐색 방법이
각각의 방향에 따라 간선을 순회할 뿐이라는 것이다.
정점 v에서 시작하는 DFS의 지시된 버전은
코드 조각 13.11의 재귀적 알고리즘에 의해 기술될 수 있다(그림 13.9 참조)
코드 조각 13.11: 방향 그래프에서의 DFS 알고리즘.
Algorithm DirectedDFS(v):
Mark vertex v as visited.
for each outgoing edge (v, w) of v do
if vertex w has hot been visited then
Recursively call DirectedDFS(w).
그림 13.9: 방향 그래프에서 DFS의 예:
(a) 중간 단계에서 처음으로 이미 방문한 정점(DFW)에 도달한다.
(b) 완성된 DFS.
트리의 간선은 파란색 실선으로,
역행 간선은 파란색 점선으로,
순행과 교차 간선은 검은색 점선으로 표시하였다.
정점을 방문한 순서는 각 정점 옆에 있는 라벨로 표시하였다.
간선(ORD,DFW)는 역행 간선이지만 (DFW,ORD)는 순행 간선이다.
간선(BOS,SFO)는 순행 간선이고, (SFO,LAX)는 교차 간선이다.
그래프 G 위의 DFS는 시작 정점에서 도달할 수 있는 G의 간선을
트리 간선 또는 발견 간선과 비트리 간선으로 분할한다.
트리 간선(tree edge) 또는 발견 간선(discovery edge): 새로운 정점을 발견하도록 유도하는 간선
비트리 간선(nontree edge): 이전에 방문한 꼭짓점을 이동하는 간선
깊이 우선 탐색 트리(depth-first search tree): 트리 간선이 시작 정점에 루트를 둔 트리
세 종류의 비트리 간선이 있다:
• 역행 간선(back edge): DFS 트리의 조상에 정점을 연결하는 간선
• 정방향 간선(forward edge): DFS 트리의 자손에 정점을 연결하는 간선
• 교차 간선(cross edge): 한 꼭짓점을 그것의 조상도 그 후손도 아닌 꼭짓점에 연결하는 간선
그림 13.9b를 다시 참조하여 각 유형의 트리가 아닌 간선의 예를 확인한다.
명제 13.16:
G: 방향 그래프
정점 s에서 시작하는 G에 대한 깊이 우선 검색은 s에서 도달할 수 있는 G의 모든 정점을 방문한다.
또한 DFS 트리는 s로부터 s로부터 도달할 수 있는 모든 정점으로의 지시된 경로를 포함한다.
정당화:
Vs: 정점 s에서 시작하는 DFS가 방문하는 G의 정점들의 부분집합
Vs가 s를 포함하고 s에서 도달할 수 있는 모든 정점은 Vs에 속한다는 것을 보이고자 한다.
모순을 위해 이제, s에서 도달할 수 있는 정점 w가 Vs에 속하지 않는다고 가정하자.
s에서 w로의 방향 경로를 생각하고,
(u, v)를 Vs의 밖을 통과하는 경로의 첫 번째 간선,
즉 u는 Vs에 있지만 v는 Vs에 있지 않다고 하자.
DFS가 u에 이르면, 그것은 u의 모든 나가는 간선을 탐색하므로
간선 (u,v)를 통해 정점 v에도 도달해야 한다.
따라서 v는 Vs에 있어야 하고, 모순을 얻었다.
따라서 Vs는 s에서 도달할 수 있는 모든 정점을 포함해야 한다
방향 그래프의 DFS 메서드의 실행 시간을 분석하는 것은 무향 그래프에 대한 실행 시간과 유사하다.
특히 재귀적 호출은 각 정점에 대해 한 번씩만 수행되고, 각 간선은 원점에서 한 번만 수행된다.
따라서 n개의 정점과 ms개의 간선이 정점 s에서 도달할 수 있는 경우,
방향 그래프가 상수 시간 정점과 간선 메서드를 지원하는 자료 구조로 표현된다면
s에서 시작하는 지시된 DFS는 O(ns + ms) 시간으로 실행된다.
예를 들어 인접 리스트 구조는 이 요구 사항을 충족한다.
명제 13.16에 의해 DFS를 사용하여 주어진 정점에서 도달할 수 있는 모든 정점을 찾을 수 있으며,
따라서 G의 transitive closure를 찾을 수 있다.
즉, G의 각 정점 v에서 시작하여
V에서 도달할 수 있는 정점 w를 확인하기 위해 DFS를 수행할 수 있으며,
각 w에 대한 transitive closure에 간선 (v, w)를 추가할 수 있다.
마찬가지로 그래프 G를 DFS와 함께 반복적으로 각 정점에서 시작하여
G가 강하게 연결되어 있는지 여부를 쉽게 테스트할 수 있다.
즉, 각 DFS가 G의 모든 정점을 방문할 때 강하게 연결되어 있다.
따라서 바로 다음 명제를 도출할 수 있다.
명제 13.17:
G: n개의 꼭짓점과 m개의 간선을 가진 방향 그래프
DFS를 사용하여 G를 n번 순회하고
O(n(n+m)) 시간으로 실행하며 O(n) 보조 공간을 사용하는 알고리즘으로
다음 문제를 해결할 수 있다:
• G의 각 정점 v에 대하여, v에서 도달할 수 있는 부분 그래프 계산하기
• G가 강하게 연결되어 있는지 테스트하기
• G의 transitive closure G*를 계산하기
강력한 연결 테스트
실제로 우리는 두 번의 깊이 우선 검색을 사용하여
방향 그래프 G가 이보다 훨씬 빨리 강하게 연결되어 있는지 확인할 수 있다.
1. 임의의 정점 s에서 시작하여 지시 그래프 G의 DFS를 수행하는 것으로 시작한다.
2-1) 만약 이 DFS에 의해 연결되지 않고 s에서 연결되지 않는 G의 정점이 있다면,
그래프는 강하게 연결되어 있지 않다.
2-2) 만약 이 첫 번째 DFS가 G의 각 정점을 방문한다면,
(역방향 메소드를 사용하여) G의 모든 간선을 역방향으로 하고
이 "역방향" 그래프의 s에서 시작하는 또 다른 DFS를 수행한다.
2-3) 만약 두 번째 DFS에 의해 G의 모든 정점이 방문된다면,
그래프는 강하게 연결되어 있고, 이 DFS에 방문된 각 정점에 대해 s에 도달할 수 있다.
3. 이 알고리즘은 G를 단지 두 번만 순회하므로 O(n+m) 시간으로 실행된다.
방향을 가진 너비 우선 검색
DFS와 마찬가지로, 너비 우선 검색(BFS)을 확장하여 방향 그래프에 대해 작업할 수 있다.
알고리즘은 여전히 레벨별로 정점을 방문하여
일련의 간선을 트리 간선(또는 발견 간선)과 비트리 간선으로 분할한다.
트리 간선(tree edge) or 발견 간선(discovery edge):
시작 정점에 루트를 둔 방향이 있는 너비 우선 검색(breadth-first search) 트리를 함께 형성한다.
그러나 지시된 DFS 방법과 달리 지시된 BFS 방법은 두 가지 종류의 비트리 간선만 남긴다:
역행 간선(back edge): 정점을 조상 중 하나에 연결하는 간선
크로스 간선(cross edge): 정점을 조상이나 후손이 아닌 다른 정점에 연결하는 간선
DFS 방법과 달리 순행 간선은 없다.
13.4.2 Transitive Closure
이 절에서 우리는 그래프의 transitive closure를 계산하기 위한 다른 방법을 알아본다.
G: n개의 꼭짓점과 m개의 간선을 가지는 방향그래프
일련의 라운드에서 G의 transitive closure를 계산한다.
G0 = G를 초기화한다.
또한 임의로 G의 꼭짓점에 v1, v2,..., vn이라는 번호를 매긴다.
그런 다음 라운드 1부터 시작하여 라운드의 계산을 시작한다.
일반적인 라운드 k에서, 만약 그래프 Gk-1이 간선 (vi,vK)와 (vk,vj)를 모두 포함한다면,
그래프 Gk = Gk-1로 시작하여 Gk에 방향 간선 (vi,vj)을 추가하는 그래프 Gk를 구성한다.
이런 식으로, 다음 명제에 구체화된 간단한 규칙을 시행할 것이다.
명제 13.18:
i=1,...,n인 경우, 유향 그래프 G가 vi에서 vj로 향하는 방향 경로를 갖는 경우에만
방향 그래프 Gk는 간선 (vi, vj)을 가지며, 그 중간 정점 (있는 경우)은 집합 {v1,...,vk}에 있다.
특히 Gn은 G의 일시적 폐쇄인 G*와 같다.
제안 13.18은 위에서 설명한 일련의 라운드를 기반으로 하는
G0의 transitive closure를 계산하는 간단한 알고리즘을 제안한다.
이 알고리즘은 플로이드-워샬 알고리즘(Floyd-Warshall algorithm)으로 알려져 있으며,
코드 조각 13.12에 유사 코드가 부여되어 있다.
이 의사 코드로부터, G를 나타내는 자료 구조가
O(1) 시간의 areAdjacent와 insertDirectedEdge 메소드를 지원한다고 가정할 때
플로이드-워샬 알고리즘의 실행 시간을 쉽게 분석할 수 있다.
메인 루프는 n번 실행되고
내부 루프는 O(n^2)개의 정점 쌍을 각각 고려하여
각각의 정점에 대해 일정한 시간 계산을 수행한다.
따라서 플로이드-워샬 알고리즘의 총 실행 시간은 O(n^3)이다.
코드 조각 13.12: 플로이드-워샬 알고리즘에 대한 의사 코드.
이 알고리즘은 일련의 방향 그래프 G0, G1,..., GN(여기서 k = 1,..., n)을 점진적으로 계산하여
G의 transitive closure G*를 계산한다.
Algorithm FloydWarshall(G):
Input: A digraph G with n vertices
Output: The transitive closure G* of G
let v1, v2, ...., vn be an arbitrary numbering of the vertices of G
G0 ← G
for k ← 1 to n do
Gk ← Gk-1
for all i, j in {1, ..., n} with i ≠ j and i, j ≠ k do
if both edges (vi, vk) and (vk, vj) are in Gk-1 then
add edge (vi, vj) to Gk (if it is not already present)
return Gn
이 설명은 실제로 동적 프로그래밍으로 알려진 알고리즘 설계 패턴의 한 예이며,
이에 대해서는 12.5.2절에서 더 자세히 설명한다.
위의 설명과 분석을 통해 우리는 바로 다음과 같은 명제를 도출할 수 있다.
명제 13.19:
G: n개의 정점을 가진 방향 그래프
G를 O(1) 시간에 인접 정보의 조회 및 갱신을 지원하는 자료 구조로 나타내자.
그런 다음 플로이드-워샬 알고리즘은 G의 transitive colosure G를 O(n^3) 시간에 계산한다.
그림 13.10에서 플로이드-워샬 알고리즘의 실행 예를 보여준다.
그림 13.10: 플로이드-워샬 알고리즘에 의해 계산된 도표의 순서:
(a) 초기 방향 그래프 G* = G0 및 정점의 번호 부여;
(b) 방향 그래프 G1; (c) 방향 그래프 G2, (d) 방향 그래프 G3; (e) 방향 그래프 G4;
(f) 방향 그래프 G5.
G5 = G6 = G7.
도표 Gk의 그림에서 간선 (vi,vk) 및 (vk,vj)가 아닌 경우,
간선 (vi,vj)과 점선 파란색 선이 있는 간선 (vi,vk) 및 (vk,vj)가
점선 파란색 선이 있는 간선 (vi,vj)이 표시되고,
굵은 파란색 선이 있는 간선 (vi,vj)이 표시된다.
Floyd-Warshall 알고리즘의 성능
플로이드-워샬 알고리즘의 실행 시간은
각 정점에서 지시된 그래프의 DFS를 수행하는 것보다 느려 보일 수 있지만,
이는 그래프의 표현에 의존한다.
그래프가 인접 행렬을 사용하여 표현되는 경우
지시된 그래프에서 DFS 방법을 한 번 실행하면 O(n^2) 시간이 걸린다
따라서 DFS를 n번 실행하는 것은 O(n^3) 시간이 걸리므로
플로이드-워홀 알고리즘을 한 번 실행하는 것과 다를 바 없지만
플로이드-워홀 알고리즘은 구현하기가 훨씬 간단할 것이다.
그럼에도 인접 리스트 구조를 사용하여 그래프를 표현하면
DFS 알고리즘을 n번 실행하면 O(n(n+m)) 시간이 소요되어
transitive closure를 계산할 수 있다.
그럼에도 그래프의 밀도가 높은(dense) 경우, 즉 &(n^2)개의 간선이 있는 경우
이 접근 방식은 여전히 O(n^3) 시간에서 실행되며
플로이드-워홀 알고리즘의 단일 인스턴스보다 복잡하다.
DFS 방법을 반복 호출하는 것이 더 나은 유일한 경우는
그래프의 밀도가 높지 않고 인접 리스트 구조를 사용하여 표현되는 경우이다.
13.4.3 방향 비순환 그래프
방향 비순환 그래프(directed acyclic graph, DAG): 방향이 있는 사이클이 없는 방향 그래프
방향 비순환 그래프의 응용의 예
• Java 프로그램의 클래스 간 상속이다.
• 학위 과정 간의 필수 조건.
• 프로젝트 작업 간의 예약 제약 조건이다.
예제 13.20:
대규모 프로젝트를 관리하기 위해서는 프로젝트를 더 작은 작업들로 구성하는 것이 편리하다.
그러나 작업들은 거의 독립적이지 않은데, 그 이유는 스케줄링 제약들이 그들 사이에 존재하기 때문이다.
(예를 들어, 주택 건설 프로젝트에서, 못을 주문하는 작업은 분명히 지붕 데크에 못을 박는 작업보다 선행한다.)
확실히, 스케줄링 제약은 순환 관계를 가질 수 없는데,
왜냐하면 그것들은 프로젝트를 불가능하게 만들 것이기 때문이다.
(예를 들어, 직업을 얻기 위해서는 작업 경험이 있어야 하지만, 작업 경험을 얻기 위해서는 작업이 필요하다.)
스케줄링 제약은 작업이 실행될 수 있는 순서에 제한을 가한다.
즉, 작업 b가 시작되기 전에 작업 a가 완료되어야 한다고 제약 조건이 말하는 경우,
작업 실행 순서에서 a가 b 앞에 와야 한다.
따라서, 실현 가능한 작업 집합을 방향 그래프의 정점으로 모델링하고,
v에 대한 작업이 w에 대한 작업 전에 실행되어야 할 때마다 v에서 방향 간선을 배치한다면,
방향 비순환 그래프를 정의한다.
위의 예제는 다음과 같은 정의에 동기를 부여한다.
G: n개의 정점을 가진 방향 그래프
G의 위상 순서(topological ordering)
= G의 모든 간선 (vi, vj)에 대하여 i < j인 정점 G의 순서 v1,...,vn
= G의 임의의 방향 경로가 증가하는 순서로 정점을 가로지르도록 하는 순서
(그림 13.11 참조) 방향 그래프는 둘 이상의 위상 순서를 가질 수 있다.
그림 13.11: 동일한 비순환 방향 그래프의 두 가지 위상 순서.
명제 13.21: G는 비순환인 경우에만 위상 순서를 갖는다.
정당화:
(문에서 "유일한 경우에만" 부분)는 증명하기 쉽다.
G가 위상적으로 순서가 있다고 가정하자.
모순을 위해, G가 간선 (vi0, vi1), (vi1, vi2),..., (vik-1, vi0)으로 구성된 사이클을 가지고 있다고 가정하자.
위상적 순서 때문에, 우리는 분명히 불가능한 i0 < i1 ... < ik-1 < i0을 가져야 한다.
따라서, G는 비순환적이어야 한다.
이제 조건의 충분성("만약" 부분")을 논한다.
G가 비순환적이라고 가정하자.
G에 대한 위상수학적 순서를 만드는 방법에 대해 알고리즘적으로 설명하겠다.
G는 비순환적이므로 G는 들어오는 간선이 없는(즉, 차수가 0인) 정점을 가져야 한다.
v1이 이러한 정점이라고 하자.
실제로 v1이 존재하지 않는다면 임의의 시작 정점으로부터 유도된 경로를 추적할 때,
G의 비순환성과 모순되는 이전에 방문한 정점을 만나게 될 것이다.
만약 G에서 v1을 나가는 간선들과 함께 제거한다면, 결과적인 도표는 여전히 비순환적이다.
따라서 결과적인 도표는 들어오는 간선이 없는 정점도 있으므로 v2를 그러한 정점이라고 하자.
이러한 과정을 그래프가 비어버릴 때까지 반복하면 G의 정점들 중 순서 v1,...,vn을 얻는다.
위와 같은 구성으로 인해 (vi,vj)가 G의 간선이면 vj를 삭제하기 전에 vi를 삭제해야 하고, 따라서 i<j.
따라서 v1,...,vn은 위상수학적 순서이다.
제안 13.21의 정당성은 방향그래프의 위상 순서를 계산하기 위한
위상 정렬이라고 불리는 알고리즘(코드 조각 13.13)을 제안한다.
코드 조각 13.13: 위상 정렬 알고리즘을 위한 의사 코드.
(그림 13.12에서 이 알고리즘의 예시적인 적용을 보여준다).
Algorithm TopologicalSort(G):
Input: A digraph G with n vertices.
Output: A topological ordering v1, ...., vn of G.
S ← an initially empty stack.
for all u in G.vertices() do
Let incounter(u) be the in-degree of u.
if incounter(u) = 0 then
S.push(u)
i ← 1
while !S.isEmpty() do
u ← S.pop()
Let u be vertex number i in the topological ordering.
i ← i + 1
for all outgoing edge (u, w) of u do
incounter(w) ← incounter(w) - 1
if incounter(u) = 0 then
S.push(w)
명제 13.22:
G: n개의 꼭짓점과 m개의 간선을 갖는 방향그래프
위상 정렬 알고리즘은 O(n) 보조 공간을 이용하여 O(n + m) 시간으로 실행되며,
G가 방향을 가지는 사이클을 갖는다는 것을 나타내는
일부 꼭짓점의 위상 순서 G를 계산하거나 번호를 매기지 못한다.
정당화:
in-degree의 초기 계산과 반대변수들의 설정은
O(n + m) 시간이 걸리는 그래프의 단순한 순회로 수행할 수 있다.
데코레이터 패턴을 사용하여 반대값 속성을 정점들과 연결시킨다.
스택 S에서 u를 제거할 때 위상 정렬 알고리즘에 의해 정점 u가 방문되었다고 하자.
정점 u는 카운터 (u) = 0일 때만 방문할 수 있으며,
이는 이전의 모든 정점들(바깥쪽 간선이 u로 정점)이 이전에 방문했던 것을 의미한다.
그 결과로, 방향이 있는 사이클에 있는 어떤 정점도 방문하지 않고, 다른 정점들도 정확히 한 번 방문할 것이다.
알고리즘은 방문한 각 정점의 나가는 간선들을 한 번씩 모두 횡단하므로,
그 실행 시간은 방문한 정점들의 나가는 간선들의 수에 비례한다.
따라서 알고리즘의 실행 시간: O(n + m)
공간 사용과 관련하여, 스택 S와 정점들에 부착된 반대변수들이 O(n) 공간을 사용하는 것을 관찰하라.
부가적인 작용으로 코드 조각 13.13의 위상 정렬 알고리즘도 테스트를 수행한다
입력된 그래프가 비순환적인지 여부이다.
실제로 알고리즘이 모든 정점의 순서를 지정하지 않고 종료된다면,
순서를 지정하지 않은 정점의 부분 그래프는 반드시 방향이 있는 사이클을 포함해야 한다.
그림 13.12: 알고리즘 위상 정렬(코드 조각 13.13)의 실행 예:
(a) 초기 설정;
(b-i) 각 while문 반복 후.
정점 라벨은 정점 번호와 현재 카운터 값을 보여준다.
횡단하는 간선들은 점선 파란색 화살표들로 보여준다.
굵은 선들은 현재 반복에서 조사된 정점과 간선들을 나타낸다.
13.5 가중치 그래프
13.3.3절에서 살펴본 바와 같이,
너비 우선 탐색 전략은 연결된 그래프에서 시작하는
어떤 정점에서 다른 모든 정점으로 가는 최단 경로를 찾는 데 사용될 수 있다.
이 접근법은 각 간선이 다른 간선만큼 좋은 경우에는 타당하지만,
적절하지 않은 상황이 많이 발생한다.
예시1) 컴퓨터 네트워크를 나타내기 위해 그래프를 사용할 수도 있고,
두 컴퓨터 사이에서 자료 패킷을 라우팅하는 가장 빠른 방법을 찾는 데 관심이 있을 수도 있다.
이 경우 컴퓨터 네트워크의 어떤 연결은 일반적으로 다른 연결보다 훨씬 빠르기 때문에
모든 간선이 동일한 것은 적절하지 않을 수 있다.
예를 들어, 어떤 간선은 느린 전화선 연결을 나타내고, 어떤 간선은 고속 광섬유 연결을 나타낼 수도 있다.
예시2) 도시 간 도로를 나타내기 위해 그래프를 사용하고 싶을 수도 있고,
가장 빠른 국가 간 이동 방법을 찾는 데 관심이 있을 수도 있다.
이 경우, 어떤 도시 간 거리는 다른 간선보다 훨씬 클 것이므로
모든 간선이 동일한 것은 아마도 적절하지 않을 것이다.
따라서 간선이 동일하게 가중치가 부여되지 않은 그래프를 고려하는 것은 당연하다.
가중치 그래프(weighted graph):
각 간선 e와 관련된 숫자(예를 들어, 정수) 라벨 w(e)인 간선의 가중치를 갖는 그래프
그림 13.13에 가중치 그래프의 예를 보여준다.
그림 13.13:
다음 정점과 간선 가중치를 가지는 가중치 그래프이다.
정점: 미국의 주요 공항
간선 가중치: 거리(마일)
이 그래프는 총 가중치 2,777 (ORD와 DFW를 통함)의 JFK에서 LAX까지의 경로를 갖는다.
이는 그래프에서 JFK에서 LAX까지의 최소 가중치 경로이다.
이 장의 나머지 부분에서는 가중치 그래프에 대해 연구한다.
13.6 최단 경로
G: 가중치 그래프
경로의 길이(length)(또는 가중치(weight)): P의 간선들의 가중치들의 합
즉, P = (v0,v1), (v1,v2), ..., (vk-1,vk)이면,
w(P)로 표시되는 P의 길이는 다음과 같이 정의된다
G에서 정점 v에서 정점 U까지의 거리(distance)
= d(v, U)
= 이러한 경로가 존재할 경우
v에서 u로의 최소 길이 경로(최단 경로(shortest path)라고도 함)의 길이
G에서 v에서 u로의 경로가 전혀 없다면 d(v, u) = + ∞라는 규칙을 자주 사용한다.
G에서 v에서 u로의 경로가 존재하더라도
G에 총중량이 음수인 사이클이 존재한다면
v에서 U까지의 거리는 정의되지 않을 수 있다.
예시)
G에 있는 정점: 도시
G에 있는 간선의 무게: 한 도시에서 다른 도시로 가는 데 드는 비용
만약 누군가가 실제로 우리에게 JFK에서 ORD로 가는 데 돈을 지불할 의사가 있다면,
간선의 "비용"은 음수가 될 것이다.
만약 누군가가 ORD에서 JFK로 가는 데 돈을 지불할 의사가 있다면,
G에는 음수-가중치 사이클이 존재하고 거리는 더 이상 정의되지 않을 것이다.
즉, 이제 누구나 G 안에 임의의 도시 A에서 다른 도시 B로 가는 길을 만들 수 있고,
그 길은 처음에는 JFK로 가고,
다시 JFK에서 ORD로 오고,
다시 B로 가기 전에 원하는 만큼 순환한다.
그러한 경로의 존재는 임의로 낮은 음수-비용 경로를 만들 수 있게 해줄 것이다.
그러나 거리는 임의로 낮은 음수일 수 없다.
따라서 거리를 나타내기 위해 간선 가중치를 사용할 때마다
음수-가중치 사이클을 도입하지 않도록 주의해야 한다.
가중치 그래프 G가 주어졌을 때,
G에서 어떤 정점 v에서 다른 정점으로 가는 가장 짧은 경로를 찾도록 하고,
간선들의 가중치를 거리로 나타낸다고 가정하자.
이 절에서는, 그러한 가장 짧은 경로가 존재한다면,
그러한 모든 경로를 찾는 효율적인 방법을 알아본다.
우리가 논의하는 첫 번째 알고리즘은
G의 모든 간선 가중치가 음수가 아닌 경우
(즉, G의 각 간선 e에 대하여 w(e) ≥ 0)에 대한 것이므로,
G에는 음수-가중치 사이클이 없음을 미리 알 수 있다.
모든 가중치가 1일 때 가장 짧은 경로를 계산하는 특별한 경우는
13.3.3절에 제시된 BFS 순회 알고리즘으로 해결되었음을 기억하라.
그리디 방법(greedy method) 설계 패턴에 기반한
이 단일 소스(single source) 문제를 해결하기 위한 흥미로운 접근법이 있다(12.4.2절).
이 패턴에서는 각 반복에서 사용할 수 있는 것들 중에서 최선의 선택을 반복하여 선택함으로써
당면한 문제를 해결한다는 것을 기억하라.
이 패러다임은 종종 객체들의 컬렉션에 대해
일부 비용 함수를 최적화하려고 하는 상황에서 사용될 수 있다.
아직 선택되지 않은 것들 중에서 항상 함수를 최적화하는 다음 것을 선택하면서
한 번에 하나씩 객체를 컬렉션에 추가할 수 있다.
13.6.1 Dijkstra의 알고리즘
그리디 방법 패턴을 단일 소스 최단 경로 문제에 적용하는 주된 아이디어
= v에서 시작하는 "가중된" 너비 우선 검색을 수행하는 것
특히 그리디 방법을 사용하면 v에서 "구름"을 벗어나
정점들이 v에서 거리 순서대로 구름 속으로 들어가는 알고리즘을 개발할 수 있다.
따라서 각 반복에서 다음으로 선택된 정점은 구름 밖의 정점으로 v에 가장 가깝다.
알고리즘은 더 이상 구름 밖에 정점들이 없을 때 종료되며,
이때 우리는 v에서 G의 다른 모든 정점으로 가는 경로가 가장 짧다.
이 접근법은 그리디 방법 설계 패턴의 단순하지만 강력한 예이다.
최단경로 탐색을 위한 그리디 방법
단일 소스 최단 경로 문제에 그리디 방식을 적용하면
다익스트라의 알고리즘(Dijkstra's algorithm)으로 알려진 알고리즘이 나타난다.
그러나 다른 그래프 문제에 적용할 때 그리디 방법이 반드시 최선의 해결책을 찾지는 못할 수도 있다.
ex) 판매원 문제(traveling salesman problem): 그래프의 모든 정점을 한 번만 방문하는 최단 경로를 찾고자 하는 문제
그러나 그리디 방법이 최선의 해를 계산할 수 있게 해주는 여러 상황이 있다.
이 장에서 우리는 두 가지 상황, 즉 최단 경로 계산과 최소 신장 트리 구성에 대해 논의한다.
다익스트라의 알고리즘을 간단히 설명하기 위해,
다음과 같이 입력 그래프 G가 무방향이고 (즉, 모든 간선이 무방향이고) 단순하다고 가정한다.
따라서 G의 간선을 순서 없는 정점 쌍 (u,z)로 표기한다.
다익스트라의 최단 경로 찾기 알고리즘에서 그리디 방법을 적용할 때
최적화하려고 하는 비용 함수는 우리가 계산하려고 하는 함수, 즉 최단 경로 거리이다.
우리가 계산하려고 하는 거리 함수에 대한 근사치를 사용하는 것으로 구성된
"부트스트래핑" 기법을 사용하여
실제로 이 접근법을 구현할 수 있다는 것을 깨닫기 전까지는
처음에는 순환 추론처럼 보일 수 있다.
간선 이완
V의 각 정점 u에 대하여 V에서 u까지의 거리를 근사하는 데 사용되는 라벨 D[u]를 정의하자.
이 라벨들의 의미는
D[u]가 항상 v에서 U까지의 거리 중에서 찾은 최선의 경로의 길이를 저장한다는 것이다.
처음에 각각 u, v(u ≠ v)에 대하여 D[v] = 0이고 D[u] = + ∞이며,
정점들의 "구름(cloud)"인 집합 C를 처음에는 빈 집합 t로 정의한다.
알고리즘의 각 반복에서 D[u] 라벨이
가장 작은 C에 속하지 않는 정점 u를 선택하고, u를 C 안으로 끌어들인다.
물론 첫 번째 반복에서 우리는 v를 C 안으로 끌어들일 것이다.
일단 새로운 정점 u를 C 안으로 끌어당기면,
u를 통해 z로 가는 새롭고 더 나은 방법이 있을 수 있다는 사실을 반영하기 위해
u에 인접하고 C 밖에 있는 각 정점 z의 라벨 D[z]를 업데이트한다.
이 업데이트 연산은 relaxation 절차라고 알려져 있는데,
이는 이전의 추정치를 사용하고 실제 값에 더 가깝게 개선될 수 있는지 확인한다.
Dijkstra 알고리즘의 경우,
완화는 간선 (u,z)에 대해 수행되어 새로운 D[u] 값을 계산하고
간선 (u,z)를 사용하여 D[z]에 대해 더 나은 값이 있는지 확인하고자 한다.
구체적인 간선 relaxation 연산은 다음과 같다:
간선 relaxation:
만약 D[u] +w((u,z)) D[z]이면 D[z]←D[u]+w((u,z))
코드 조각 13.14에서 다익스트라 알고리즘에 대한 의사 코드를 제시한다.
우선순위 큐 Q를 사용하여 클라우드 C 외부의 정점들을 저장한다.
코드 조각 13.14: 단일 소스 최단 경로 문제에 대한 Dijkstra의 알고리즘.
Algorithm ShortestPath(G,v):
Input: A simple undirected weighted graph G with nonnegative edge weights,
and a distinguished vertex v of G.
Output: A label D[u], for each vertex u of G, such that D[u] is the length of a
shortest path from v to u in G
Initialize D[v] ← 0 and D[u] ← +∞ for each vertex u ≠ v.
Let a priority queue Q contain all the vertices of G using the D labels as keys.
while Q is not empty do
{pull a new vertex u into the cloud}
u ← Q.removeMin()
for each vertex z adjacent to u such that z is in Q do
{perform the relaxation procedure on edge (u,z)}
if D[u] + w((u,z)) < D[z] then
D[z] ← D[u] + w((u,z))
Change to D[z] the key of vertex z in Q.
return the label D[u] of each vertex u
그림 13.14와 13.15에 Dijkstra 알고리즘의 여러 번의 반복을 설명한다.
그림 13.14: Dijkstra의 알고리즘을 가중치 그래프로 실행한 것이다.
시작하는 정점은 BWI이다.
각 정점 v 옆에 있는 상자에는 D[v]라는 라벨이 저장되어 있다.
기호 •는 + ∞ 대신에 사용된다.
가장 짧은 경로 트리의 간선은 굵은 파란색 화살표로 그려져 있으며,
"구름" 바깥에 있는 각 정점 u에 대하여
파란색 실선으로 u를 당기기에 가장 좋은 현재의 간선을 보여준다.
(그림 13.15에서 계속된다).
그림 13.15: Dijkstra 알고리즘의 예시 실행 (그림 13.14부터 계속)
작동하는 이유
다익스트라 알고리즘의 특징
정점 u가 C로 끌려 들어가는 순간,
그것의 라벨 D[u]가 v에서 u로의 최단 경로의 정확한 길이를 저장한다는 것
따라서 알고리즘이 종료되면,
그것은 v에서 G의 모든 정점까지의 최단 경로 거리를 계산했을 것이다.
= 그것은 단일 소스 최단 경로 문제를 해결했을 것이다.
Dijkstra의 알고리즘이 그래프에서
시작 정점 v에서 다른 정점 u까지의 최단 경로를 정확히 찾는 이유는 분명하지 않을 것이다.
정점 u가 구름 C로 끌려 들어갈 때
v에서 u까지의 거리가 라벨 D[u]의 값과 같은 이유는 무엇인가?
이 질문에 대한 답은 그래프에 음의 가중치가 있는 간선이 없다는 것에 달려 있는데,
이는 다음의 명제에서 볼 수 있는 것처럼 그리디 방법이 올바르게 작동하도록 하기 때문이다.
제안 13.23:
Dijkstra 알고리즘에서 정점 u를 클라우드로 끌어들일 때마다
d[u]라는 라벨 = v에서 u로의 최단 경로 길이인 d(v, u)
정당화:
V의 어떤 정점 t에 대하여 D[t]>d(v,t)라고 가정하고,
알고리즘이 D[u]>d(v,u)와 같이 구름 C로 끌어들인 첫 번째 정점이라고 하자.
v에서 u로 가는 경로 P가 가장 짧다(그렇지 않으면 d(v)=+ ∞ = D[u]).
따라서 u가 C로 끌리는 순간을 고려하고,
z를 C에 없는 P(v에서 u로 갈 때)의 첫 번째 정점이라고 하자.
경로 P에서 z의 앞에 y가 있다고 하자(그림 13.16 참조).
z를 선택함으로써 y가 이 시점에서 이미 C에 있음을 알 수 있다.
또한, u가 첫 번째 잘못된 정점이므로 D[y] = d(v,y). Y를 C로 끌었을 때,
D[z]를 테스트하여 (그리고 아마도 업데이트된) D[z]를 얻었다
D[z]≤D[y]+w((y,z))=d(v,y)+w((y,z)).
그러나 z는 v에서 u로 가는 가장 짧은 경로의 다음 정점이므로, 이것은 다음을 의미한다
D[z] = d(v,z).
그러나 지금 C에 결합하기 위해 z가 아닌 u을 선택하는 중이다. 그러므로,
D[u] ≤ D[z].
가장 짧은 경로의 부분 경로는 그 자체로 가장 짧은 경로임을 분명히 해야 한다.
따라서 z는 v에서 u로 가는 가장 짧은 경로에 있으므로,
d(v,z)+d(z,u)=d(v,u)
또, d(z, u)는 음수 가중치 간선이 없기 때문에, 0의 ≥이다.
따라서, D[u] ≤ D[z] = d(v,z) ≤ d(v,z) + d(z, u) = d(v, u)이다.
그러나 이것은 u의 정의와 모순되므로 이러한 정점 u는 존재할 수 없다.
그림 13.16: 명제 13.23의 정당화를 위한 도식적인 그림.
Dijkstra 알고리즘의 실행 시간
이 절에서는 다익스트라 알고리즘의 시간 복잡도를 분석한다.
입력 그래프 G의 정점의 개수: n
입력 그래프 G의 간선의 개수: m
일정한 시간에서 간선 가중치를 더해서 비교할 수 있다고 가정한다.
코드 조각 13.14에서 다익스트라 알고리즘에 대해 설명의 높은 레벨로 인해,
다익스트라 알고리즘의 실행 시간을 분석하려면 구현에 대해 더 자세히 설명해야 한다.
구체적으로, 사용된 자료 구조와 그것들이 어떻게 구현되는지를 나타내야 한다.
우선 그래프 G를 인접 리스트 구조로 나타낸다고 가정하자.
이 자료 구조를 통해 u에 인접한 정점들의 수에 비례하는 시간적 여유 단계를 밟을 수 있다.
그러나 알고리즘의 또 다른 원리 자료 구조인
우선순위 큐 Q를 어떻게 구현해야 하는지에 대해서는
아직도 자세히 설명하지 못하고 있다.
우선순위 큐 Q의 효율적인 구현은 힙(heap)을 사용한다(섹션 8.3).
이를 통해 가장 작은 D 라벨로 정점 u를 O(logn) 시간 내에 추출할 수 있다.
의사 코드에서 언급된 바와 같이, D[z] 라벨을 업데이트할 때마다
우선순위 큐의 z 키를 업데이트해야 한다.
따라서 실제로 적응 가능한 우선순위 큐의 힙 구현이 필요하다(섹션 8.4).
만약 Q가 힙으로 구현된 적응 가능한 우선순위 큐라면,
이 키 업데이트는 예를 들어 replaceKey(e, k)를 사용할 수 있다.
(e: 정점 z에 대한 키를 저장하는 엔트리)
만약 e가 위치 인식형이라면,
Q가 힙에 z를 저장하는 엔트리에 즉시 액세스할 수 있기 때문에
O(logn) 시간 내에 이러한 키 업데이트를 쉽게 구현할 수 있다(섹션 8.4.2 참조).
Q의 이러한 구현을 가정할 때,
Dijkstra 알고리즘은 O((n + m) logn) 시간 내에 실행된다.
코드 조각 13.14를 다시 참조하면,
실행 시간 분석의 세부사항은 다음과 같다:
• 초기 키 값으로 Q의 모든 정점을 삽입하는 것은 반복 삽입에 의해 O(n logn) 시간에 수행되거나,
상향식 힙 구성을 사용하여 O(n) 시간에 수행될 수 있다(제8.3.6절 참조).
• while문의 각 반복에서 Q에서 정점 u를 제거하기 위해 O(logn) 시간을,
u에 결합된 간선에 대한 완화 절차를 수행하기 위해 O(degree(v)logn) 시간을 사용한다.
• while문의 전체 실행 시간은
이 값은 명제 13.6에 의해 O((n+m) log n)이다.
만약 달리는 시간을 n의 함수로만 표현하고자 한다면, 최악의 경우는 O(n^2 log n)이다.
Dijkstra 알고리즘의 대안적 구현
이제 정렬되지 않은 시퀀스를 사용하여
적응 가능한 우선순위 큐 Q에 대한 대안적인 구현을 고려해 보자.
물론 이를 위해서는 O(n) 시간을 할애하여 최소 요소를 추출해야 하지만,
Q가 위치 인식 항목을 지원한다면 매우 빠른 키 업데이트가 가능하다(8.4.2절).
구체적으로, O(1) 시간 내에 완화 단계에서 수행되는 각 키 업데이트를 구현할 수 있으며,
업데이트할 Q의 항목을 찾으면 키 값을 간단히 변경할 수 있다.
따라서 이를 구현하면 실행 시간은 O(n^2 + m)이며,
G는 간단하므로 O(n^2)로 단순화할 수 있다.
두 구현 비교
Dijkstra의 알고리즘에서 위치 인식 항목으로
적응 가능한 우선 순위 큐를 구현하기 위해
O((n+m)log n)의 실행 시간을 산출하는 힙 구현과
O(n^2)의 실행 시간을 산출하는 정렬되지 않은 시퀀스 구현 두 가지 방법이 있다.
두 구현 모두 코드화하기가 상당히 간단하기 때문에
필요한 프로그래밍 정교성 측면에서 거의 동일하다.
이 두 구현은 최악의 실행 시간에 대한 상수 요인 측면에서도 거의 동일하다.
이러한 최악의 경우 시간만 살펴보면
그래프의 간선 수가 작을 때(즉, m < (n^2)/(log n)일 때) 힙 구현을 선호하고,
간선 수가 많을 때(즉, m > (n^2)/(log n)일 때) 시퀀스 구현을 선호한다.
제안 13.24:
G: 각 간선의 무게가 음수가 아닌 n개의 정점과 m개의 간선을 갖는 단순한 무방향 가중 그래프
G의 정점 v가 주어지면,
Dijkstra의 알고리즘은 v에서 G의 다른 모든 정점까지의 거리를
O((n + m) log n) 최악의 경우 시간, 또는 대안적으로 O(n^2) 최악의 경우 시간으로 계산한다.
연습 R-13.17에서 v에서 정점 u로의 T의 경로가 v에서 u로의 G의 최단 경로가 되도록
v에 뿌리를 둔 트리 T를 출력하기 위해 Dijkstra의 알고리즘을 수정하는 방법을 탐구한다.
자바에서 Dijkstra의 알고리즘 프로그래밍
Dijkstra 알고리즘에 대한 의사 코드 설명을 제공한 후,
이제 양의 정수 가중치를 갖는 무방향 그래프가 주어졌다고 가정하고
Dijkstra 알고리즘을 수행하기 위한 자바 코드를 제시하자.
클래스 Dijkstra를 통해 알고리즘을 표현하는데,
이는 e의 가중치를 추출하기 위해 각 간선 e에 대한 가중치 장식을 사용한다.
클래스 Dijkstra는 각 간선이 가중치 장식을 갖는다고 가정한다.
코드 조각 13.15: Dijkstra의 알고리즘을 구현하는 클래스 Dijkstra.
(코드 조각 13.16에서 계속)
/* Dijkstra's algorithm for the single-source shortest path problem
* in an undirected graph whose edges have non-negative integer weights. */
public class Dijkstra<V, E> {
/** Infinity value. */
protected static final Integer INFINITE = Integer.MAX_VALUE;
/** Input graph. */
protected Graph<V, E> graph;
/** Decoration key for edge weights */
protected Object WEIGHT;
/** Decoration key for vertex distances */
protected Object DIST = new Object();
/** Decoration key for entries in the priority queue */
protected Object ENTRY = new Object();
/** Auxiliary priority queue. */
protected AdaptablePriorityQueue<Integer, Vertex<V>> Q;
/** Executes Dijkstra's algorithm.
* @param g Input graph
* @param s Source vertex
* @param w Weight decoration object */
public void execute(Graph<V, E> g, Vertex<V> s, Object w) {
graph = g;
WEIGHT = w;
DefaultComparator dc = new DefaultComparator();
Q = new HeapAdaptablePriorityQueue<Integer, Vertex<V>>(dc);
dikjstraVisit(s);
}
/** Get the distance of a vertex from the source vertex.
* @param u Start vertex for the shortest path tree */
public int getDist(Vertex<V> u) {
return (Integer) u.get(DIST);
}
Dijkstra 알고리즘의 주요 계산
메소드 dijkstraVisit: 위치 인식 항목을 지원하는 적응 가능한 우선 순위 큐 Q가 사용된다(섹션 8.4.2).
메소드 insert: Q에 정점 u를 삽입하고, 이를 통해 Q의 위치 인식 항목을 반환한다.
메소드 setEntry: Q의 u에 대한 항목을 "부착"한다.
메소드 getEntry: u의 항목을 검색한다.
정점에 항목을 연결하는 것은 데코레이터 디자인 패턴의 인스턴스라는 점에 유의하자(섹션 13.3.2).
라벨 D[u]에 대한 추가 자료 구조를 사용하는 대신,
D[u]가 Q의 정점 u의 키이므로
Q의 u에 대한 항목이 주어지면 D[u]를 검색할 수 있다는 사실을 이용한다.
호출 메소드 replaceKey(e,d): 완화 절차에서 정점 z의 라벨을 d로 변경한다.
(e: Q의 z에 대한 위치 인식 항목)
코드 조각 13.16: 클래스 Dijkstra의 메소드 dijkstraVisit .
(코드 조각 13.15부터 계속)
/** The actual execution of Dijkstra's algorithm.
* @param v source vertex.
*/
protected void dijkstraVisit (Vertex<V> v) {
// store all the vertices in priority queue Q
for (Vertex<V> u: graph.vertices()) {
int u_dist;
if (u==v)
u_dist = 0;
else
u_dist = INFINITE;
Entry<Integer, Vertex<V>> u_entry = Q.insert(u_dist, u); // autoboxing
u.pot(ENTRY, u_entry);
}
// grow the cloud, one vertex at a time
while (!Q.isEmpty()) {
// remove from Q and insert into cloud a vertex with minimum distance
Entry<Integer, Vertex<V>> u_entry = Q.min();
Vertex<V>> u = u_entry.getValue();
int u_dist = u_entry.getKey();
Q.remove(u_entry); // remove u from the priority queue
u.put(DIST, u_dist); // the distance of u is final
u.remove(ENTRY); // remove the entry decoration of u
if (u_dist == INFINITE)
continue; // unreachable vertices are not processed
// examine all the neighbors of u and update their distances
for (Edge<E> e: graph.incidentEdges(u)) {
Vertex<V> z = graph.opposite(u,e);
Entry<Integer, Vertex<V>> z_entry
= (Entry<Integer, Vertex<V>>) z.get(ENTRY);
if (z_entry != null) { // check that z is in Q, i.e., not in the cloud
int e_weight = (Integer) e.get(WEIGHT);
int z_dist = z_entry.getKey();
if ( u_dist + e_weight < z_dist ) // relaxation of edge e = (u,z)
Q.replaceKey(z_entry, u_dist + e_weight);
}
}
}
}
13.7 최소 신장 트리
새 사옥의 모든 컴퓨터를 최소한의 케이블을 사용하여 연결하려고 한다고 가정하자.
이 문제의 모델은 컴퓨터의 정점이 되고 간선이 되는
모든 컴퓨터 쌍(u, v)을 나타내는 가중치 그래프 G를 사용할 수 있는데,
간선 (v, u)의 무게 w(v, u)는 컴퓨터 v를 컴퓨터 u에 연결하는 데 필요한 케이블의 양과 같다.
어떤 특정 정점 v로부터 최단 경로 트리를 계산하는 것보다는
G의 모든 정점을 포함하고 그러한 모든 트리에 대하여
최소의 총 무게를 갖는 (자유) 트리 T를 찾는 것에 관심이 있다.
이 절에서는 이러한 트리를 찾는 방법을 중점적으로 다룬다.
문제 정의
G: 가중치가 부여된 무방향 그래프
T: G의 모든 정점을 포함하고 합을 최소화하는 트리
스패닝 트리(spanning tree): 이와 같이 연결된 그래프 G의 모든 정점을 포함하는 트리
최소 스패닝 트리(minimum spanning tree 또는 MST) 문제:
총 가중치가 가장 작은 스패닝 트리 T를 계산하는 문제
컴퓨터 과학 자체의 현대적 개념보다 앞서
최소 신장 트리 문제에 대한 효율적인 알고리즘이 개발되었다.
이 절에서는 MST 문제를 해결하기 위한 두 가지 고전적인 알고리즘에 대해 논의한다.
이 두 가지 알고리즘은 모두 그리디 방법의 적용으로,
앞 절에서 간단히 설명했듯이 비용 함수를 최소화하는 객체를 반복적으로 선택하여
증가하는 컬렉션에 합류할 객체를 선택하는 것을 기반으로 한다.
1. 크루스칼의 알고리즘(Kruskal's algorithm):
간선을 가중치 순서대로 고려하여 군집으로 MST를 성장시킨다.
2. 프림-얀니크 알고리즘(Prim-Jarník algorithm):
다익스트라의 최단 경로 알고리즘과 거의 동일한 방식으로 단일 루트 정점에서 MST를 성장시킨다.
13.6.1절에서와 같이, 알고리즘의 설명을 단순화하기 위해,
다음과 같이, 입력 그래프 G가 무방향이고 (즉, 모든 간선이 무방향이고) 단순하다고 가정한다.
따라서, G의 간선들을 순서화되지 않은 정점 쌍들 (u,z)로 표기한다.
그러나 이러한 알고리즘의 세부 사항을 논의하기 전에
알고리즘의 기본이 되는 최소 신장 트리에 대한 중요한 사실을 설명하자.
최소 신장 트리에 관한 중요한 사실
우리가 논의하는 두 가지 MST 알고리즘은 그리디 방식에 기반을 두고 있으며,
이 경우 다음과 같은 사실에 결정적으로 의존한다. (그림 13.17 참조)
그림 13.17: 최소 신장 트리에 대한 중요한 사실을 보여주는 그림.
명제 13.25:
G: 가중치가 부여된 연결 그래프
V1과 V2: G의 꼭짓점들을 서로소가 아닌 두 집합으로 분할한 것
e: V1에서 하나의 끝점을 가진 것들과 V2에서 다른 끝점을 가진 것들 중에서
최소 가중치를 갖는 G에서의 간선
e를 간선 중 하나로 갖는 최소 신장 트리 T가 있다.
정당화:
T: G의 최소 신장 트리
만약 T가 간선 e를 포함하지 않는다면, T에 e를 더하면 사이클이 생성된다.
f: V1에서 하나의 끝점을 V2에서 다른 끝점을 갖는 이 사이클의 일부 간선
또한 e를 선택함으로써 w(e) ≤ w(f)가 된다.
T {e}에서 f를 제거하면 총 가중치가 이전보다 크지 않은 신장 트리를 얻는다.
T가 최소 신장 트리였으므로 이 새로운 트리도 최소 신장 트리여야 한다.
사실 G의 가중치가 서로 다르다면 최소 신장 트리는 고유하며,
이 덜 중요한 사실의 정당성은 연습문제로 남겨둔다.
또한, 제안 13.25는 그래프 G가 가장 짧은 경로에 대해 제시한 알고리즘과 달리
음의 가중치 간선 또는 음의 가중치 사이클을 포함하더라도 여전히 유효하다.
13.7.1 Kruskal의 알고리즘
명제 13.25가 매우 중요한 이유는 최소 신장 트리를 구축하는 데 기초가 될 수 있기 때문이다.
크러스칼의 알고리즘에서는 최소 신장 트리를 클러스터로 구축하는 데 사용한다.
처음에는 각각의 정점이 모두 자신의 클러스터 안에 있다.
알고리즘은 가중치를 증가시켜 순서대로 각 간선을 고려한다.
만약 간선 e가 두 개의 다른 클러스터를 연결하면,
e는 최소 신장 트리의 간선 집합에 추가되고,
e에 의해 연결된 두 클러스터는 하나의 클러스터로 병합된다.
반대로 e가 이미 같은 클러스터 안에 있는 두 정점을 연결하면, e는 폐기된다.
알고리즘이 신장 트리를 구성할 만큼 충분한 간선을 추가하면,
그것은 종료되고 이 트리를 최소 신장 트리로 출력한다.
코드 조각 13.17에서 Kruskal의 MST 알고리즘에 대한 의사 코드를 제공하고,
그림 13.18, 13.19 및 13.20에서 이 알고리즘의 작동을 보여준다.
코드 조각 13.17: MST 문제에 대한 Kruskal의 알고리즘.
Algorithm Kruskal(G):
Input: A simple connected weighted graph G with n vertices and m edges
Output: A minimum spanning tree T for G
for each vertex v in G do
Define an elementary cluster C(v) ← {v}.
Initialize a priority queue Q to contain all edges in G, using the weights as keys.
T ← Φ { T will ultimately contain the edges of the MST}
while T has fewer than n - 1 edges do
(u, v) ← Q.removeMin()
Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
if C(v) ≠ C(u) then
Add edge (v, u) to T.
Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).
return tree T
앞에서 언급한 바와 같이 크루스칼의 알고리즘이 정확하다는 것은
최소 신장 트리에 관한 중요한 사실 명제 13.25로부터 찾을 수 있다.
크루스칼의 알고리즘이 최소 신장 트리 T에 간선 (v,u)를 추가할 때마다
V1: v를 포함하는 클러스터로 하고
V2: V의 나머지 정점을 포함하는 것으로 정점 집합 V의 분할
이것은 분명히 V의 정점들의 서로소 분할을 정의하고,
Q에서 가중치로 간선을 순서대로 추출하기 때문에
e: V1에서 하나의 정점을, V2에서 다른 정점을 갖는 최소 가중치 간선
따라서 크루스칼의 알고리즘은 항상 유효한 최소 신장 트리 간선을 추가한다.
그림 13.18:
정수 가중치가 있는 그래프에서 Kruskal의 MST 알고리즘을 실행한 예이다.
클러스터를 음영 지역으로 보여주고 각 반복에서 고려되는 간선을 강조한다
(그림 13.19에서 계속).
그림 13.19:
Kruskal의 MST 알고리즘의 실행 예.
거부된 간선은 점선으로 표시된다.
(그림 13.20에서 계속된다.)
그림 13.20:
Kruskal의 MST 알고리즘의 실행 예(계속).
(n)에서 고려한 간선 마지막 두 클러스터를 병합하고,
이로써 Kruskal의 알고리즘의 실행이 종료된다(그림 13.19부터 계속).
크루스칼 알고리즘의 실행시간
입력 그래프 G의 정점의 수: n
입력 그래프 G의 간선의 수: m
코드 조각 13.17에서 크루스칼의 알고리즘에 대해 설명한 내용이 매우 높기 때문에,
실행 시간을 분석하는 데에는 그 구현에 대해 더 많은 정보를 제공해야 한다.
구체적으로, 사용된 자료 구조와 그것들이 어떻게 구현되었는지를 나타내야 한다.
힙을 사용하여 우선순위 큐 Q를 구현할 수 있다.
따라서 반복적인 삽입을 통해 O(m log m) 시간으로 Q를 초기화하거나,
상향식 힙 구성을 사용하여 O(m) 시간으로 Q를 초기화할 수 있다(제8.3.6절 참조).
또한 While문을 반복할 때마다 G는 간단하므로
O(log m) 시간에 최소 가중치 간선을 제거할 수 있으며, 이는 실제로는 O(log n)이다.
따라서 우선순위 큐 연산을 수행하는 데 소요되는 총 시간은 O(m log n)에 지나지 않는다.
11.6.2절에서 논의한 조합 찾기 파티션 자료 구조 중 하나를 사용하여
각 클러스터 C를 나타낼 수 있다.
시퀀스 기반 조합 찾기 구조를 사용하면
일련의 N개의 조합을 수행하고 O(N log N) 시간에 연산을 찾을 수 있으며
트리 기반 버전은 이러한 일련의 연산을 O(N log* N) 시간에 구현할 수 있음을 기억한다.
따라서 메서드 union에 n - 1 호출을 수행하고 최대 m 호출을 수행하여 찾는 것이므로
클러스터를 병합하고 정점이 속하는 클러스터를 결정하는 데 소요되는 총 시간은
시퀀스 기반 접근법을 사용하는 O(mlogn) 또는
트리 기반 접근법을 사용하는 O(mlog* n)에 지나지 않는다.
따라서 Dijkstra의 알고리즘에 사용된 것과 유사한 주장을 사용하여
G가 단순하고 연결되어 있기 때문에
Kruskal의 알고리즘의 실행 시간은 O((n+m) logn)으로 단순화할 수 있다고 결론짓는다.
13.7.2 Prim-Jarnik 알고리즘
프림-자르니크 알고리즘:
어떤 "근" 정점 v로부터 시작하는 단일 군집으로부터 최소 신장 트리를 키운다.
프림 알고리즘의 주요 아이디어:
1. 정점 C의 초기 "구름"을 정의하는 일부 정점 v부터 시작한다.
2. 각 반복에서 구름 C의 정점 v를 C 밖의 정점 u에 연결하는
최소 가중치 간선 e = (v,u)를 선택한다.
3. 정점 u는 구름 C로 들어가고 신장 트리가 형성될 때까지 이 과정을 반복한다.
다시 최소 신장 트리에 대한 중요한 사실이 작용하게 되는데,
항상 C 내부의 정점과 C 외부의 정점을 연결하는 가장 작은 무게의 간선을 선택함으로써
MST에 항상 유효한 간선을 추가할 수 있기 때문이다.
이 접근법을 효율적으로 구현하기 위해,
Dijkstra의 알고리즘으로부터 또 다른 단서를 얻을 수 있다.
클라우드 C 외부의 각 정점 u에 대한 레이블 D[u]를 유지하므로,
D[u]는 클라우드 C에 결합하기 위한 최적의 현재 간선의 가중치를 저장한다.
이러한 라벨을 통해 클라우드에 합류할 정점을 결정할 때 고려해야 하는 간선의 수를 줄일 수 있다.
코드 조각 13.18에 있는 의사 코드를 제공한다.
코드 조각 13.18: MST 문제에 대한 Prim-Jarník 알고리즘.
Algorithm PrimJarnik(G):
Input: A weighted connected weighted graph G with n vertices and m edges
Output: A minimum spanning tree T for G
Pick any vertex v of G
D[v] ← 0
for each vertex u ≠ v do
D[v] ← +∞
Initialize T ← Φ.
Initialize a priority queue Q with an entry ((u, null), D[u]) for each vertex u,
where (u, null) is the element D[u]) is the key.
while Q is not empty do
(u, e) ← Q.removeMin()
Add vertex u and edge e to T.
for each vertex z adjacent to u such that z is in Q do
{perform the relaxation procedure on edge (u, z)}
if w((u,z)) < D[z] then
D[z] ← w((u,z))
Change to (z, (u, z)) the element of vertex z in Q.
Change to D[z] the key of vertex z in Q.
return the tree T
Prim-Jarn ık 알고리즘 분석
입력 그래프 G의 정점의 수: n
입력 그래프 G의 간선의 수: m
Prim-Jarník 알고리즘의 구현 문제
적응 가능한 우선 순위 큐 Q를 위치 인식 항목을 지원하는 힙으로 구현하면(섹션 8.4.2),
각 반복에서 정점 u를 O(log n) 시간에 추출할 수 있다.
또한 각 D[z] 값을 O(log n) 시간에 업데이트할 수 있으며,
이는 각 간선(u,z)에 대해 한 번에 고려되는 계산이다.
각 반복의 다른 단계는 일정한 시간에 구현할 수 있다.
따라서 총 실행 시간은 O(n + m) log n이며, 이는 O(m log n)이다.
Prim-Jarn ık 알고리즘 예시
그림 13.21부터 13.22까지 Prim-Jarn ık 알고리즘을 설명한다.
그림 13.21: Prim-Jarník MST 알고리즘을 설명한다.
(그림 13.22에서 계속된다.)
그림 13.22: Prim-Jarník MST 알고리즘의 그림.
(그림 13.21부터 계속)
'프로그래밍 공부 > Data Structure' 카테고리의 다른 글
| 14장 메모리 (0) | 2024.01.19 |
|---|---|
| 13장 그래프(1) (1) | 2024.01.13 |
| 12장 텍스트 처리 (1) | 2024.01.10 |
| 11장 집합, 정렬, 선택(2) (2) | 2024.01.07 |
| 11장 정렬, 집합, 선택(1) (1) | 2024.01.05 |