CHAP 10: 그래프(part 2) 2015. 9. 30 순천향대학교 하상호

목차 그래프 용어 그래프 표현 그래프 탐색 연결 성분 신장 트리 최소비용 신장 트리 최단 경로 위상정렬

신장 트리(spanning tree) 신장트리(spanning tree): 그래프내의 모든 정점을 포함하는 트리 신장 트리는 모든 정점들이 연결되어 있어야 하고 또한 사이클을 포함해서는 안 된다.

신장 트리 G가 연결그래프이고, G를 dfs(또는 bfs)로 순회할 때, G의 간선은 2개의 집합 T, B로 분리 T: 그래프 순회시 사용되는 간선들의 집합 B: 그래프 순회시 사용되지 않는 간선들의 집합 G의 모든 정점과 T에 속한 간선들로만 구성된 트리를 신장 트리라 한다. 깊이-우선 신장트리(depth-first spanning tree) 너비-우선 신장트리(breath first spanning tree)

신장 트리: 예제 깊이-우선 신장트리는? 너비-우선 신장트리는? 2 1 4 5 3

신장 트리: 예제 2 1 3 4 5 6 7 8 깊이-우선 신장트리는? 너비-우선 신장트리는?

신장 트리 알고리즘 신장트리의 용도 dfs(v: vertex) // 전역 변수 visited[1..n]가 false로 초기화 되었다고 가정 // 전역 변수 T = {}으로 초기화되었다고 가정 { visited[v] = true; for (v에 인접한 각 정점 w에 대해서) { if (visited[w] <> true ) then } 신장트리의 용도 통신 네트워크 구축: 최소의 링크를 사용하여 네트워크를 구축하고 싶은 경우

신장 트리 G의 |V| = n일 때, 구성된 신장 트리에 대해서 답하시오. 사용 예 간선의 개수는? 모든 정점들은 연결되어 있는가? 사이클을 포함하는가? 그래프의 최소 연결 그래프인가? 사용 예 통신 네트워크 구축 N개의 위치를 연결하는 통신네트워크를 구성할 때, 최소의 링크의 개수는 어떻게 구하는가? 도시를 연결하는 도로 건설 사내 전화기를 가장 적은 수의 케이블을 사용하여 연결하는 경우 링크의 구축 비용이 다를 경우에는? 최소 링크의 개수가 최소 비용을 보장하는가? 주어진 그래프에서 신장 트리는 여러 개 존재 가능하다. 어느 것을 선택할 것인가? 링크 구축 비용을 어떻게 고려하는가?

최소비용신장트리 신장 트리의 비용 최소비용 신장트리 (MST: minimum spanning tree) MST의 응용 가중치가 부여된 무방향 그래프의 신장 트리에 속한 모든 간선들의 비용들의 합 최소비용 신장트리 (MST: minimum spanning tree) 주어진 그래프에 대한 신장 트리중에서 간선들의 가중치 합이 최소인 신장 트리 MST의 응용 도로 건설 - 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제 전기 회로 - 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제 통신 - 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제 배관 - 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제

MST 알고리즘 2가지의 대표적인 알고리즘 탐욕적인 방법(greedy method) Kruskal의 알고리즘 Prim의 알고리즘 탐욕적인 방법(greedy method) 알고리즘 설계에서 있어서 중요한 기법 중의 하나 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달(최적의 해답을 단계별로 구한다.) 탐욕적인 방법은 항상 최적의 해답을 주는지를 반드시 검증해야 한다. 일단 내려진 결정은 번복 불가능 Kruskal의 알고리즘은 최적의 해답을 주는 것으로 증명

Kruskal 알고리즘 개념 예제: 다음 그래프에 대해서 최소비용 신장트리를 구하라. 최소비용 간선 트리 T를 생성 간선들의 비용을 nondecreasing order의 순서로 T에 추가하되 새로 추가된 간선이 T에 포함된 간선들과 사이클이 형성되지 않게 예제: 다음 그래프에 대해서 최소비용 신장트리를 구하라.

Kruskal 알고리즘 Kruskal(g: graph) // 가정: g= (V, E) where |V| = n { T <- φ; // T는 신장트리에 포함된 간선들의 집합 while (|T| < n-1 and |E| > 0 ) { } return T

Kruskal 알고리즘: 예제 다음 그래프에 대한 최소비용신장트리를 Kruskal 알고리듬으로 구하라.

Kruskal 알고리즘: 예제 다음 그래프에 대한 최소비용신장트리를 Kruskal 알고리듬으로 구하라.

Kruskal 알고리즘의 구현 어떻게 구현할 것인가? Kruskal(g: graph) // 가정: g= (V, E) where |V| = n { E에 속한 모든 간선들을 가중치의 오름차순으로 정렬하라 T <- φ; // T는 신장트리에 포함된 간선들의 집합 while (|T| < n-1 and |E| > 0 ) { E에서 가중치가 가장 낮은 간선 (v, w)를 선택; if ((v, w)가 T 상에서 사이클을 형성하지 않으면) then (v, w)를 T에 추가 else (v, w)를 버린다 end if } return T 어떻게 구현할 것인가?

Kruskal 알고리즘의 구현(1) T에 속한 간선들로 구성된 연결 성분을 식별 새로운 간선 (v, w)를 T에 추가할 때, V, w가 다른 연결 성분에 속할 경우에만 (v, w)를 T에 추가 a와 b가 같은 컴포넌트 에 속함 a와 b가 다른 컴포넌트에 속함

Kruskal 알고리즘의 구현(1): 예제 같은 연결 성분에 속한 모든 정점들을 같은 집합에 속하게 한다. 두 정점 v, w가 같은 연결 성분에 속한다. iff v, w는 같은 집합에 속한다. 다음 그래프에 대해서 간선 추가시 사이클 형성 여부를 판단하는 방법을 적용한다. 처음에, 각 원소는 자신만을 포함하는 한 개의 집합으로 구성 {a}, {b}, {c}, {d}, {e}, {f}, {g} 간선들을 차례대로 선택해보라.

Kruskal 알고리즘의 구현(2) 집합을 어떻게 표현할 것인가? 집합 연산 여러 가지 방법 존재: 비트벡터, 배열, 연결리스트, 트리 트리가 가장 효율적인 방법 집합 연산 집합은 pairwise disjoint 임의 두 집합, Si, Sj는 disjoint union(Si, Sj) find(i): 원소 i를 포함하는 집합을 찾는다.

Kruskal 알고리즘의 구현(2) 집합을 트리로 어떻게 표현할 것인가? 집합 연산 트리 노드는 집합 원소를 표현 트리의 루트로 집합을 식별 트리를 배열로 표현 노드는 부모의 정점(원소)을 가리키게 루트의 부모는 (- 원소개수)를 포함하게 집합 연산 union(i, j): 루트 i, j의 2개 트리를 join find(i): 원소 i를 포함하는 집합(트리의 루트) 식별 효율적 find 연산을 위해서 특정 원소와 루트와의 거리를 짧게 union 연산시, 작은 트리의 루트가 큰 트리의 루트를 가리키게 find 연산시, 원소 i부터 트리 루트까지의 경로상의 모든 노드들이 루트를 가리키게

예제 8개의 정점을 포함하는 그래프 고려 처음에, 한 개의 원소로 구성된 8개의 집합 생성 루트의 부모를 -1로 설정: parent(i) = -1 루트 부모의 절대값은 루트의 크기를 나타내게 다음 연산을 순차적으로 수행: union(1, 2), union(3,4), union(5, 6), union(7,8)

예제(2) 다음 연산을 계속 수행 Union(1, 3), union(5, 7) 다음 연산을 수행: union(1, 5) find(8)

Kruskal 알고리즘의 구현(1): 예제 다음 그래프에 대해서 간선 추가시 사이클 형성 여부를 판단하는 방법을 적용한다. 집합을 트리로 표현하라. 처음에, 각 원소는 자신만을 포함하는 한 개의 집합으로 구성 {a}, {b}, {c}, {d}, {e}, {f}, {g} 간선들을 차례대로 선택해보라.

union 알고리즘 int parent[NumOfVertices];// 각 정점에 대한 집합의 루트 표현 … union(i, j: integer) { int tmp;// 결과 집합의 크기 표현 // 합집합의 집합 크기 계산 // 작은 집합이 큰 집합을 가리키게 }

union 알고리즘 int parent[NumOfVertices];// 각 정점에 대한 집합의 루트 표현 … union(i, j: integer) { int tmp;// 결과 집합의 크기 표현 // 합집합의 집합 크기 계산 tmp = parent[i] + parent[j]; // 작은 집합이 큰 집합을 가리키게 if (parent[i] >parent[j]) then //|j|>|i| parent[j] = tmp; parent[i] = j; else parent[i] = tmp; parent[j] = I; end if }

find 알고리즘 Integer find(i: integer) { int tmp, tmp1, tmp2; tmp = i; }

find 알고리즘 Integer find(i: integer) { int tmp, tmp1, tmp2; tmp = i; while parent[tmp] < 0 ) do tmp = parent[tmp]; end while //i부터 루트까지의 경로상의 노드들이 루트를 가리키게 tmp2 = i; while (tmp2 <> tmp) do tmp1 = parent[tmp2]; parent[tmp2] = tmp; // 루트 변경 tmp2 = tmp1; }

Kruskal 코드 (1)

Kruskal 코드 (2)

Example 다음 그래프에 대해서 kruskal 알고리즘을 이용하여 MST를 구하라. 1 4 7 5 6 3 2 10 1 2 1 1 4 2 8 5 6 7 5 4 12 9 7 6 3 3 2 11

Prim의 MST 알고리즘 Prim의 알고리즘은 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함 앞 단계에서 만들어진 신장 트리 집합에, 인접한 정점들 중에서 이미 구성된 트리 상에서 사이클을 형성하지 않는 최저 간선으로 연결된 정점을 선택하여 트리를 확장 이 과정은 트리가 n-1개의 간선을 가질 때까지 계속된다. 간선 (a, b)와 간선 (f, e)의 가중치를 비교해보면 (f, e)가 27로서 (a, b)의 29보다 높다. 따라서 (f, e) 간선이 선택되고 정점 e가 신장 트리 집합에 포함된다.

Prim의 MST 알고리즘

Example 다음 그래프에 대해서 Prim 알고리즘을 이용하여 MST를 구하라. 단, 0의 정점을 시작 정점으로 하라. 1 10 1 1 4 2 8 5 6 7 5 4 12 9 7 6 3 3 2 11

Prim의 MST 알고리즘 T = {}; // 선택된 트리 간선들의 집합 TV = {0}; // 선택된 트리 정점들의 집합, 0은 시작 정점 While ( |TV| < n ) { // G = (V, E), |V| = n u ∈ TV이고 v ∈ TV인 최저비용 간선을 (u, v)라 함; if (그러한 간선 (u, v)가 존재하면) then add v to TV; add (u, v) to T; else { print “No spanning tree”; break; } end if end while

Kruskal vs Prim 구분 Kruskal Prim 방법 간선을 nondecreasing 순서로 추가(사이클 형성불가) 하나의 정점으로 된 트리에서 시작하여 이 한 개의 트리를 확장(사이클 형성 불가) 단계에서 선택된 간선들의 집합은? 포리스트를 구성 한 개의 트리를 구성 알고리즘 복잡도

Kruskal 알고리즘 알고리즘 복잡도는? Kruskal(g: graph) // 가정: g= (V, E) where |V| = n { E에 속한 모든 간선들을 가중치 기준으로 히프 트리 구성 T <- φ; // T는 신장트리에 포함된 간선들의 집합 while (|T| < n-1 and |E| > 0 ) { E에서 가중치가 가장 낮은 간선 (v, w)를 선택;//히프 트리 삭제 if ((v, w)가 T 상에서 사이클을 형성하지 않으면) then (v, w)를 T에 추가 else (v, w)를 버린다 end if } return T

Prim의 MST 알고리즘 알고리즘 복잡도는? T = {}; // 선택된 트리 간선들의 집합 TV = {0}; // 선택된 트리 정점들의 집합, 0은 시작 정점 While ( |TV| < n ) { // G = (V, E), |V| = n u ∈ TV이고 v ∈ TV인 최저비용 간선을 (u, v)라 함; if (그러한 간선 (u, v)가 존재하면) then add v to TV; add (u, v) to T; else { print “No spanning tree”; break; } end if end while

코드: Prim의 MST dist: 현재까지 알려진 정점들의 집합에서 다른 각 정점까지의 거리로 정의