쉽게배우는알고리즘 9장. 그래프알고리즘

Size: px

Start display at page:

Download "쉽게배우는알고리즘 9장. 그래프알고리즘"

칠 애
5 years ago
Views:

1 쉽게배우는알고리즘 장. 그래프알고리즘

2 장. 그래프알고리즘 수학은패턴의과학이다. 음악역시패턴들이다. 컴퓨터과학은추상화와패턴의형성에깊은관련이있다. 컴퓨터과학이다른분야들에비해특징적인것은지속적으로차원이 급상승한다는점이다. 미시적관점에서 거시적관점으로도약하는것이다. - 도널드크누스 - - 한빛미디어

3 학습목표 그래프의표현법을익힌다. 너비우선탐색과깊이우선탐색의원리를충분히이해하도록한다. 신장트리의의미와최소신장트리를구하는두가지알고리즘을이해한다. 그래프의특성에따라가장적합한최단경로알고리즘을선택할수있도록한다. 위상정렬을이해하고 DAG 의경우에위상정렬을이용해최단경로를구하는방법을이해한다. 강연결요소를구하는알고리즘을이해하고이알고리즘의정당성을확신할수있도록한다. 본문에서소개하는각알고리즘의수행시간을분석할수있도록한다. - - 한빛미디어

4 Graph 현상이나사물을정점 vertex 과간선 edge 으로표현한것 Graph G = (V, E) V: 정점집합 E: 간선집합 두정점이간선으로연결되어있으면인접하다고한다 인접 = adjacent 간선은두정점의관계를나타낸다 - - 한빛미디어

5 그래프의예 철수 영희 준호 승우 동건 재상 사람들간의친분관계를나타낸그래프 - - 한빛미디어

6 영희 철수 준호 승우 동건 재상 친밀도를가중치로나타낸친분관계그래프 - - 한빛미디어

7 철수 유향그래프 directed graph=digraph 영희 준호 승우 동건 재상 방향을고려한친분관계그래프 - - 한빛미디어

8 영희 철수 준호 승우 동건 재상 가중치를가진유향그래프 - - 한빛미디어

9 Graph 의표현 : Adjacency Matrix Adjacency matrix N: 정점의총수 NⅩN 행렬로표현 원소 (i, j) = : 정점 i 와정점 j 사이에간선이있음 원소 (i, j) = 0 : 정점 i 와정점 j 사이에간선이없음 유향그래프의경우 원소 (i, j) 는정점 i 로부터정점 j 로연결되는간선이있는지를나타냄 가중치있는그래프의경우 원소 (i, j) 는 대신에가중치를가짐 - - 한빛미디어

10 철수 0 0 영희 동건 준호 재상 승우 무향그래프의예 한빛미디어

11 영희 동건 철수 준호 재상 승우 가중치있는무향그래프의예 - - 한빛미디어

12 철수 0 0 영희 동건 준호 재상 승우 유향그래프의예 - - 한빛미디어

13 영희 동건 철수 준호 재상 승우 가중치있는유향그래프의예 - - 한빛미디어

14 유향그래프의다른예 - - 한빛미디어

15 가중치있는그래프의다른예 - - 한빛미디어

16 Graph 의표현 : Adjacency List Adjacency list N 개의연결리스트로표현 i 번째리스트는정점 i 에인접한정점들을리스트로연결해 놓음 가중치있는그래프의경우 리스트는가중치도보관한다 - - 한빛미디어

17 철수 영희 준호 승우 동건 재상 무향그래프의예 - - 한빛미디어

18 영희 철수 준호 승우 동건 재상 가중치있는그래프의예 - - 한빛미디어

19 Graph Traversal 대표적두가지방법 BFS (Breadth-First Search) DFS (Depth-First Search) 너무나중요함 그래프알고리즘의기본 DFS/BFS 는간단해보이지만제대로아는사람은매우드물다 DFS/BFS 는뼛속깊이이해해야좋은그래프알고리즘을만들수있음 - - 한빛미디어

20 DFS(G) { DFS 깊이우선탐색 for each v V visited[v] NO; for each v V if (visited[v] = NO) then adfs(v); } adfs (v) { visited[v] YES; for each x L(v) } L(v) : 정점 v의인접리스트 if (visited[x] = NO) then adfs(u); ü 수행시간 : Θ( V + E ) 한빛미디어

21 BFS 너비우선탐색 BFS(G, v) { for each v V visited[v] NO; visited[s] YES; enqueue(q, s); while (Q Ф) { u dequeue(q); for each v L(u) if (visited[v] = NO) then visited[u] YES; enqueue(q, v); } } } ü 수행시간 : Θ( V + E ) - - 한빛미디어

22 동일한 Tree 를각각 DFS/BFS 로방문하기 DFS BFS - - 한빛미디어

23 BFS 의작동예 (a) (b) (c) (e) (d) - - 한빛미디어

24 DFS 의작동예 (a) (b) (c) (e) (d) - - 한빛미디어

25 DFS 의작동예 ( 계속 ) (f) (g) (i) (h) - - 한빛미디어

26 Minimum Spanning Trees 조건 무향연결그래프 연결그래프 connected graph : 모든정점간에경로가존재하는그래프 트리 싸이클이없는연결그래프 n 개의정점을가진트리는항상 n- 개의간선을갖는다 그래프 G 의신장트리 G 의정점들과간선들로만구성된트리 G 의최소신장트리 G 의신장트리들중간선의합이최소인신장트리 - - 한빛미디어

27 Prim Algorithm Prim (G, r) { S Ф ; 정점 r 을방문되었다고표시하고, 집합 S 에포함시킨다 ; while (S V) { S 에서 V-S 를연결하는간선들중최소길이의간선 (x,y) 를찾는다 ; (x S, y V-S) 정점 y 를방문되었다고표시하고, 집합 S 에포함시킨다 ; } } ü Prim 알고리즘은그리디 greedy 알고리즘의일종 ü 그리디알고리즘으로최적해를보장하는드문예 ü 수행시간 : O( E log V ) 힙이용 - - 한빛미디어

28 Prim Algorithm 의작동예 S (a) S 0 0 r 0 0 (d) 0 (b) 0 0 S 0 (c) 0 : 방금 S 에포함된정점 : 방금이완이일어난정점 - - 한빛미디어

29 (e) (f) S 0 S 0 (g) 0 0 (i) (h) S S - - 한빛미디어

30 Kruskal Algorithm Kruskal (G, r) { T Ф ; T : 신장트리단하나의정점만으로이루어진 n 개의집합을초기화한다 ; 모든간선을가중치가작은순으로정렬한다 ; while (T의간선수 < n-) { 최소비용간선 (u, v) 를제거한다 ; 정점 u와정점 v가서로다른집합에속하면 { 두집합을하나로합친다 ; T T {u, v)}; } } } ü 수행시간 : O( E log V ) 한빛미디어

31 Kruskal Algorithm 의작동예 (a) 0 (b) 0 (e) 0 (d) 0 (c) 0 : 방금고려한간선 : 성공적으로더해진간선 - - 한빛미디어

32 (f) 0 (g) 0 (i) (h) - - 한빛미디어

33 Topological Sorting 조건 싸이클이없는유향그래프 Topological Sorting 위상정렬 모든정점을일렬로나열하되 정점 x 에서정점 y 로가는간선이있으면 x 는반드시 y 보다앞에위치한다 일반적으로임의의유향그래프에대해복수의위상순서가존재한다 - - 한빛미디어

34 이그래프에대한위상정렬의예 개 - - 한빛미디어

35 위상정렬알고리즘 topologicalsort(g) { for to n { 진입간선이없는정점 u 를선택한다 ; A[i] u; 정점 u 와, u 의진출간선을모두제거한다 ; } 이시점에배열 A[ n] 에는정점들을위상정렬되어있다 } ü 수행시간 : Θ( V + E ) - - 한빛미디어

36 위상정렬알고리즘 의작동예 점화 점화 남비에물붓기 라면넣기 계란풀어넣기 남비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (a) 라면봉지뜯기 수프넣기 (b) 점화 점화 남비에물붓기 라면넣기 계란풀어넣기 남비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (d) 라면봉지수프넣기뜯기 (c) - - 한빛미디어

37 점화 점화 남비에물붓기 라면넣기 계란풀어넣기 남비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (e) 라면봉지뜯기 수프넣기 (f) 점화 남비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (g) - - 한빛미디어

38 위상정렬알고리즘 topologicalsort(g) { for each v V visited[v] NO; for each v V 정점의순서는아무순서나무관 if (visited[v] = NO) then DFS-TS(v) ; } DFS-TS(v) { visited[v] YES; } for each x L(v) L(v): v 의인접리스트 if (visited[x] = NO) then DFS-TS(x) ; 연결리스트 R 의맨앞에정점 v 를삽입한다 ; ü 수행시간 : Θ( V + E ) ü알고리즘이끝나고나면연결리스트 R에는정점들이위상정렬된순서로매달려있다. - - 한빛미디어

39 위상정렬알고리즘 의작동예 점화 점화 냄비에물붓기 라면넣기 계란풀어넣기 냄비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (a) 라면봉지뜯기 수프넣기 (b) 점화 점화 냄비에물붓기 라면넣기 계란풀어넣기 냄비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (d) 라면봉지뜯기 수프넣기 (c) - - 한빛미디어

40 - 0 - 한빛미디어 냄비에물붓기점화라면넣기라면봉지뜯기계란풀어넣기수프넣기냄비에물붓기점화라면넣기라면봉지뜯기계란풀어넣기수프넣기냄비에물붓기점화라면넣기라면봉지뜯기계란풀어넣기수프넣기 (e) (f) (g) 냄비에물붓기점화라면넣기라면봉지뜯기계란풀어넣기수프넣기 (h)

41 점화 점화 냄비에물붓기 라면넣기 계란풀어넣기 냄비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (i) 라면봉지뜯기 수프넣기 (j) - - 한빛미디어

42 Shortest Paths 조건 간선가중치가있는유향그래프 무향그래프는각간선에대해양쪽으로유향간선이있는유향그래프로생각할수있다 즉, 무향간선 (u,v) 는유향간선 (u,v) 와 (v,u) 를의미한다고가정하면된다 두정점사이의최단경로 두정점사이의경로들중간선의가중치합이최소인경로 간선가중치의합이음인싸이클이있으면문제가정의되지않는다 - - 한빛미디어

43 단일시작점최단경로 단일시작점으로부터각정점에이르는최단경로를구한다 Ø 다익스트라알고리즘 음의가중치를허용하지않는최단경로 Ø 벨만 - 포드알고리즘 음의가중치를허용하는최단경로 Ø 싸이클이없는그래프의최단경로 모든쌍최단경로 모든정점쌍사이의최단경로를모두구한다 Ø 플로이드 - 워샬알고리즘 - - 한빛미디어

44 Dijkstra Algorithm Dijkstra(G, r) G=(V, E): 주어진그래프 r: 시작으로삼을정점 { S Ф ; S : 정점집합 for each u V d u ; d r 0 ; while (S V){ n회순환된다 u extractmin(v-s, d) ; S S {u}; for each v L(u) L(u) : u로부터연결된정점들의집합 if (v V-S and d v <d u +w u,v ) then d v d u +w u,v ; } } extractmin(q, d) { 집합 Q에서 d값이가장작은정점 u를리턴한다 ; } 모든간선의가중치는음이아니어야함 이완 (relaxation) ü 수행시간 : O( E log V ) 힙이용 - - 한빛미디어

45 Dijkstra Algorithm 의작동예 한빛미디어

46 한빛미디어 0 0

47 Bellman-Ford Algorithm 음의가중치를허용한다 BellmanFord(G, r) { for each u V d u ; d r 0; for i to V - for each (u, v) E if (d u + w u,v < d v ) then d v d u + w u,v ; } 이완 (relaxation) ü 수행시간 : Θ( E V ) - - 한빛미디어

48 Bellman-Ford Algorithm 의작동예 (a) 0 (b) i = (e) i = 0 (d) i = (c) i = 한빛미디어

49 (f) i = - 0 (g) i = (i) (h) i = 한빛미디어

50 DP 로본 Bellman-Ford 알고리즘 d tk : 중간에최대 k 개의간선을거쳐정점 r로부터정점 t에이르는최단거리 목표 : d n- t ü 재귀적관계 d vk = min {d u k- + w u, v }, k > 0 for 모든간선 (u, v) d 0 r = 0 d 0 t =, t r 한빛미디어

51 Floyd-Warshall Algorithm 모든정점들간의상호최단거리구하기 응용예 Road Atlas 네비게이션시스템 네트웍커뮤니케이션 - - 한빛미디어

52 Floyd-Warshall Algorithm FloydWarshall(G) { for i to n for j to n d 0 ij w ij ; for k to n 중간정점집합 {,,, k} for i to n i : 시작정점 for j to n j : 마지막정점 d k ij min {d k- ij, d k- ik + d k- kj}; } ü d k ij : 중간정점으로정점집합 {,,, k} 만을사용하여정점 i 에서정점 j 에이르는최단경로 ü 수행시간 : Θ( V ) - - 한빛미디어

53 d k ij 관련 k i j 중간정점들이모두 {,,, k} 에속함 - - 한빛미디어

54 싸이클이없는 Graph 의 Shortest Path 싸이클이없는유향그래프를 DAG 라한다 DAG: Directed Acyclic Graph DAG 에서의최단경로는선형시간에간단히구할수있다 - - 한빛미디어

55 DAG-ShortestPath(G, r) { for each u V d u ; d r 0; G 의정점들을위상정렬한다 ; for each u V ( 위상정렬순서로 ) for each v L(u) L(u) : 정점 u 로부터연결된정점들의집합 if (d u + w u,v < d v ) then d v d u + w u,v ; } ü 수행시간 : Θ( V + E ) - - 한빛미디어

56 DAG-ShortestPath 의작동예 (a) - - (b) - - (c) r 한빛미디어

57 (d) (e) (f) 한빛미디어

58 (g) (h) (i) 한빛미디어

59 Strongly Connected Components 강하게연결됨 그래프의모든정점쌍에대해서양방향으로경로가존재하면강하게연결되었다고한다 강하게연결된부분그래프를강연결요소 Strongly connected component 라한다 임의의그래프에서강연결요소들을찾는다 - - 한빛미디어

60 SCC 구하기알고리즘 stronglyconnectedcomponent(g) {. 그래프에대해 DFS 를수행하여각정점 v 의완료시간 f v 를계산한다 ;. G R 을만든다 ;. DFS 를수행하되시작점은 에서구한 f v 가가장큰정점으로잡는다 ;. 에서만들어진분리된트리들각각을강연결요소로리턴한다 ; } ü 수행시간 : Θ( V + E ) 한빛미디어

61 stronglyconnectedcomponent 의작동예 G (a) G G (b) 0 (c) 0 G R 0 (d) - - 한빛미디어

62 0 G R 0 G R 0 G R (e) (f) (g) G R G R 0 0 (i) (h) - - 한빛미디어

63 Thank you - - 한빛미디어

Chap 6: Graphs

Chap 6: Graphs 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page ) 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v]