제 9 장 그래프.

Presentation on theme: "제 9 장 그래프."— Presentation transcript:

1 제 9 장 그래프

2 그래프는 인터넷, 도로, 운송, 전력, 상하수도망, 신경망, 화학성분 결합, 단백질 네트워크, 금융 네트워크, 소셜네트워크 분석(Social Network Analysis) 등의 광범위한 분야에서 활용되는 자료구조이다.

3 내용 그래프 용어 깊이우선탐색(DFS) 너비우선탐색(BFS) 위상정렬(Topological Sort)
최소신장트리(Minimum Spanning Tree) 최단경로(Shortest Paths)

4 9.1 그래프 9.1.1 그래프 용어 그래프는 정점(Vertex)과 간선(Edge)의 집합으로 하나의 간선은 두 개의 정점을 연결 그래프는 G=(V, E)로 표현, V=정점의 집합, E=간선의 집합 방향그래프(Directed Graph): 간선에 방향이 있는 그래프 무방향그래프(Undirected Graph): 간선에 방향이 없는 그래프 (a) 무방향그래프 (b) 방향그래프

5 정점 a와 b를 연결하는 간선을 (a, b)로 표현 정점 a에서 b로 간선의 방향이 있는 경우 <a, b>로 표현
차수(Degree): 정점에 인접한 정점의 수 방향그래프에서는 차수를 진입차수(In-degree)와 진출차수(Out-degree)로 구분 그림(a) 정점 a의 차수 = 3, 정점 e의 차수 = 2. 그림(b) 정점 g의 진입차수 = 3, 진출차수 = 1. (a) 무방향그래프 (b) 방향그래프

6 경로(Path)는 시작 정점 u부터 도착점 v까지의 정점들을 나열하여 표현
[a, c, b, e]: 정점 a로부터 도착점 e까지의 여러 경로들 중 하나 단순경로(Simple Path): 경로 상의 정점들이 모두 다른 경로 ‘일반적인’ 경로: 동일한 정점을 중복하여 방문하는 경우를 포함 [a, b, c, b, e]: 정점 a로부터 도착점 e까지의 경로 싸이클(Cycle): 시작 정점과 도착점이 동일한 단순경로 [a, b, e, d, c, a]

7 연결성분(Connected Component): 그래프에서 정점들이 서로 연결되어 있는 부분 아래의 그래프는 3개의 연결성분, [a, b, c, d, e], [f, g, h, i], [j]로 구성

8 가중치(Weighted) 그래프: 간선에 가중치가 부여된 그래프
가중치는 두 정점 사이의 거리, 지나는 시간이 될 수도 있다. 또한 음수인 경우도 존재 부분그래프(Subgraph): 주어진 그래프의 정점과 간선의 일부분(집합)으로 이루어진 그래프 부분그래프는 원래의 그래프에 없는 정점이나 간선을 포함하지 않음 트리(Tree): 싸이클이 없는 그래프 신장트리(Spanning Tree): 주어진 그래프가 하나의 연결성분으로 구성되어 있을 때, 그래프의 모든 정점들을 싸이클 없이 연결하는 부분그래프

9 9.1.2 그래프 자료구조 그래프를 자료구조로서 저장하는 방법
인접행렬(Adjacency Matrix) 인접리스트(Adjacency List) N개의 정점을 가진 그래프의 인접행렬은 2차원 NxN 배열에 저장 배열이 a라면, 정점들을 0, 1, 2,, N-1로 하여, 정점 i와 j 사이에 간선이 없으면 a[i][j] = 0, 간선이 있으면 a[i][j] = 1로 표현 가중치그래프는 1 대신 가중치 저장

10 인접행렬 인접리스트는 각 정점마다 1 개의 단순연결리스트를 이용하여 인접한 각 정점을 노드에 저장 인접리스트

11 Edge 클래스 Edge 객체는 간선의 다른 쪽 정점만을 가짐 인접리스트 adjList는 List배열로 선언 List의 각 원소는 LinkedList로 선언하여 단순연결리스트의 각 노드에 인접한 간선(다른 쪽 정점)을 가진 Edge 객체를 저장

12 인접리스트를 만드는 프로그램 인접리스트 adjList는 List배열로 선언 List의 각 원소는 LinkedList로 선언하여 단순연결리스트의 각 노드에 인접한 간선(다른 쪽 정점)을 가진 Edge 객체를 저장

13 실세계의 그래프는 대부분 정점의 평균 차수가 작은 희소그래프(Sparse Graph)이다.
희소그래프의 간선 수는 최대 간선 수인 N(N-1)/2보다 휠씬 작으므로 인접리스트에 저장하는 것이 매우 적절 무방향그래프를 인접리스트를 사용하여 저장할 경우 간선 1 개당 2개의 Edge 객체를 저장하고, 방향그래프의 경우 간선 1 개당 1개의 Edge 객체만 저장하기 때문 조밀그래프(Dense Graph): 간선의 수가 최대 간선 수에 근접한 그래프

14 9.2 그래프 탐색 그래프에서는 두 가지 방식으로 모든 정점을 방문 깊이우선탐색(DFS; Depth First Search)
너비우선탐색(BFS; Breadth First)

15 9.2.1 깊이우선탐색(DFS) [핵심 아이디어] DFS는 실타래를 가지고 미로에서 출구를 찾는 것과 유사하다. 새로운 곳으로 갈 때는 실타래를 풀면서 진행하고, 길이 막혀 진행할 수 없을 때에는 실타래를 되감으며 왔던 길을 되돌아가 같은 방법으로 다른 경로를 탐색하여 출구를 찾는다. 그래프에서의 DFS는 임의의 정점에서 시작하여 이웃하는 하나의 정점을 방문하고, 방금 방문한 정점의 이웃 정점을 방문하며, 이웃하는 정점들을 모두 방문한 경우에는 이전 정점으로 되돌아 가서 탐색을 수행하는 방식으로 진행

16 DFS 클래스

17 Line 11: for-루프에서는 0부터 N-1까지의 정점에 대해 dfs() 메소드를 호출
Line 10: for-루프에서 visited 배열을 false로 초기화, 정점 i를 방문하면 visited[i] = true로 만들어 한번 방문한 정점을 다시 방문하는 것을 방지 - 단, 방문은 정점을 출력하는 것으로 가정 Line 11: for-루프에서는 0부터 N-1까지의 정점에 대해 dfs() 메소드를 호출 그래프가 여러 개의 연결성분으로 구성된 경우 정점 0으로부터 방문을 시작하여 계속해서 인접한 정점을 방문하다 보면 정점 0이 속한 연결성분의 정점들만 방문하고, 다른 연결성분의 정점들은 방문할 수 없기 때문 Line 13의 dfs() 메소드: line 14∼15에서 visited[i]를 true로 만들고 i를 출력 Line 16: for-루프는 방금 방문한 정점 i에 인접한 정점(w.adjvertex)이 아직 방문되지 않은 경우 line 18에서 dfs()를 재귀호출

18 DFS 수행 과정

19 DFS 클래스의 line 11에 있는 for-루프에서 i가 각각 1, 2, 3일 때 visited[i] = true이므로 dfs()가 호출되지 않음
그러나 i = 4일 때에는 visited[4] = false이므로, dfs(4)를 호출하면서 정점4는 7 번째로 방문되며 나머지 정점들도 차례로 방문

20 DFS 수행 결과

21 (a)의 DFS 방문순서대로 정점 0부터 위에서 아래방향으로 정점들을 그리면 (b)와 같은 트리가 만들어진다.
실선은 탐색하며 처음 방문할 때 사용된 간선이고, 점선은 뒷간선(Back Edge)으로서 탐색 중 이미 방문 된 정점에 도달한 경우를 나타낸다. 그래프가 1개의 연결성분으로 되어있을 때 DFS를 수행하며 만들어지는 트리를 깊이우선 신장트리(Depth First Spanning Tree)라고 한다. (a) (b)

22 수행시간 DFS의 수행시간은 탐색이 각 정점을 한번씩 방문하며, 각 간선을 한번씩만 사용하여 탐색하기 때문에O(N+M)

23 9.2.2 너비우선탐색 [핵심 아이디어] BFS는 연못에 돌을 던져서 만들어지는 동심원의 물결이 퍼져나가는 것 같이 정점들을 방문한다. BFS는 임의의 정점 s에서 시작하여 s의 모든 이웃하는 정점들을 방문하고, 방문한 정점들의 이웃 정점들을 모두 방문하는 방식으로 그래프의 모든 정점을 방문 BFS는 이진트리에서의 레벨순회와 유사

24 BFS클래스

25 Line 10: for-루프에서 visited 배열을 false로 초기화하고, 정점 i를 방문하면 visited[i]를 true로 만들어 한번 방문한 정점을 다시 방문하는 것을 방지 Line 11: for-루프는0부터 N-1까지의 정점에 대해 bfs() 메소드를 호출하여 그래프의 모든 정점 방문 Line 13의 bfs() 메소드: line 15∼16에서 visited[i]를 true로 만들고, i를 큐에 삽입 Line 17: while-루프는 큐가 empty가 되면 종료되고, 루프가 처음 시작하여 끝날 때까지 연속적으로 방문된 정점들이 1개의 연결성분 구성 Line 18∼19: 큐에서 다음 방문할 정점 j를 삭제한 후, j를 출력하고, line 20의 for-루프는 정점 j에 인접해 있지만 아직 방문 안된 정점들을 큐에 삽입

26 bfs(0)부터 BFS 클래스가 수행되며 첫번째 연결성분의 정점들을 모두 방문할 때까지 큐에 정점들이 삽입, 삭제되며 정점들이 출력(방문)될 때의 큐의 상태

27 BFS 수행과정

28 프로그램 수행결과

29 (a)의 그래프에서 BFS 방문순서대로 정점 0부터 위에서 아래방향으로 그려보면 (b)와 같은 트리가 만들어짐
실선은 탐색하며 처음 방문할 때 사용된 그래프의 간선이고, 점선은 교차간선(Cross Edge)으로서 탐색 중 이미 방문된 정점에 도달한 경우를 나타냄 그래프가 1개의 연결성분으로 되어 있을 때 BFS를 수행하며 만들어지는 트리: 너비우선 신장트리 (Breadth First Spanning Tree) (a) (b)

30 수행시간 BFS는 각 정점을 한번씩 방문하며, 각 간선을 한번씩만 사용하여 탐색하기 때문에O(N+M)의 수행시간이 소요
BFS와 DFS는 정점의 방문순서나 간선을 사용하는 순서만 다를 뿐이다.

31 DFS와 BFS로 수행 가능한 그래프 응용 DFS BFS 응용 신장트리, 연결성분, 경로, 싸이클 최소 선분을 사용하는 경로
 최소 선분을 사용하는 경로 위상정렬, 이중연결성분, 강연결성분 Strongly connected components --> DFS

32 9.3기본적인 그래프 알고리즘 9.3.1 위상정렬 위상정렬(Topological Sort)이란 싸이클이 없는 방향그래프(Directed Acyclic Graph, DAG)에서 정점을 선형순서(즉, 정점들을 일렬)로 나열하는 것 위상정렬 결과는 그래프의 각 간선 <u, v>에 대해 u가 v보다 반드시 앞서 나열되어야 함

33 [예제] (a)는 교과과정의 선수과목 관계도이고, (c)는 교과목 수강순서도이다.
(a) 선수과목 관계도 (b) 그래프 (c) 교과목 수강순서

34 주어진 그래프에 따라 여러 개의 위상정렬이 존재할 수 있음
주어진 그래프에 따라 여러 개의 위상정렬이 존재할 수 있음 일반적으로 작업(Task)들 사이에 의존관계가 존재할 때 수행 가능한 작업 순서를 도식화하는데에 위상정렬을 사용 위상정렬 찾기 그래프에서 진입차수가 0인 정점 v로부터 시작하여 v를 출력하고 v를 그래프에서 제거하는 과정을 반복하는 순방향 방법 진출차수가 0인 정점 v를 출력하고 v를 그래프에서 제거하는 과정을 반복하여 얻은 출력 리스트를 역순으로 만들어 결과를 얻는 역방향 방법

35 순방향 방법은 각 정점의 진입차수를 알아야 하므로 인접리스트를 각 정점으로 진입하는 정점들의 리스트로 바꾸어야
역방향 방법은 주어진 인접리스트를 입력에 대해 변형된 DFS를 수행하여 출력 리스트를 작성한 후에 리스트를 역순으로 만들어 위상정렬 결과를 얻음 [핵심 아이디어] DFS를 수행하며 각 정점 v의 인접한 모든 정점들의 방문이 끝나자마자 v 를 리스트에 추가한다. 리스트가 완성되면 리스트를 역순으로 만든다

36 “v의 인접한 모든 정점들의 방문이 끝나자마자 v 를 리스트에 추가한다”
따라서 리스트가 완성되어 이를 역순으로 만들면 위상정렬 결과를 얻음

37 TopologicalSort 클래스

38 Line 13의 tsort() 메소드: line 18의 dfs() 메소드를 호출하며, line 15∼16과 line 23을 제외하면 DFS 클래스와 거의 동일
단, DFS클래스에서는 Edge클래스를 사용하여 간선을 나타냈지만, 여기서는 단순히 간선을 인접한 정점(int)으로 나타냄

39 아래의 그래프에 대해 TopologicalSort 클래스의 주요 부분이 어떤 단계를 거쳐 수행되는지 살펴보자.
먼저 Line 14의 dfs(0)으로 시작하여, dfs(1), dfs(3), dfs(6), dfs(7)을 차례로 호출한 후에, dfs(8)이 호출 이때 정점 8에선 더 이상 인접한 정점이 없으므로 line 20의 for-루프가 수행되지 않고 바로 line 23의 sequence.add(8)이 수행되어 ‘8’이 sequence에 가장 먼저 저장 즉, 위상정렬순서의 가장 마지막 정점을 찾아서 sequence에 저장

40 sequence.add(8)이 수행된 후 dfs()메소드가 리턴된 뒤, 정점 7에 대해 line 20의 for-루프에서 정점 7의 인접한 모든 정점들을 이미 방문했으므로, line 23에서 ‘7’을 sequence에 추가 Line 20의 for-루프에서 더 이상 방문 안된 인접한 정점이 없으면 해당 정점을 sequence에 추가 최종적으로 line 15에서 sequence를 역순으로 만들어 line 16에서 위상정렬 결과 리턴

41 프로그램 수행 결과

42 수행시간 위상정렬 알고리즘의 수행시간은 DFS의 수행시간과 동일한 O(N+M)
기본적으로 DFS를 수행하며 추가로 소요되는 시간은 line 23에서 정점을 리스트에 저장하고, 모든 탐색이 끝나면 리스트를 역순으로 만드는 시간으로 이는 O(N) 따라서 위상정렬 알고리즘의 수행시간은 O(N+M) + O(N) = O(N+M)

43 9.4 최소신장트리 최소신장트리(Minimum Spanning Tree, MST): 하나의 연결성분으로 이루어진 무방향 가중치그래프에서 간선의 가중치의 합이 최소인 신장트리 MST를 찾는 대표적인 알고리즘은 Kruskal, Prim, Sollin 알고리즘 - 모두 그리디 (Greedy) 알고리즘 그리디 알고리즘은 최적해(최솟값 또는 최댓값)를 찾는 문제를 해결하기 위한 알고리즘 방식들 중 하나로서, 알고리즘의 선택이 항상 ‘욕심내어’ 지역적인 최솟값(또는 최댓값)을 선택하며, 이러한 부분적인 선택을 축적하여 최적해를 찾음

44 어느 그래프가 신장트리일까? (b) (c) (d) (e)

45 9.4.1 Kruskal 알고리즘 간선들을 가중치가 감소하지 않는 순서로 정렬한 후 가장 가중치가 작은 간선을 트리에 추가하여 싸이클을 만들지 않으면 트리 간선으로 선택하고, 싸이클을 만들면 버리는 일을 반복하여 N-1개의 간선이 선택되었을 때 알고리즘을 종료 N은 그래프 정점의 수 Kruskal 알고리즘이 그리디 알고리즘인 이유: 남아있는 (정렬된) 간선들 중에서 항상 ‘욕심 내어’ 가중치가 가장 작은 간선을 가져오기 때문

46 Kruskal 알고리즘 [1] 가중치가 감소하지 않는 순서로 간선 리스트 L을 만든다.
[2] while (트리의 간선 수 < N-1) [3] L에서 가장 작은 가중치를 가진 간선 e를 가져오고, e를 L에서 제거 [4] if (간선 e가 T에 추가하여 싸이클을 만들지 않으면) [5] 간선 e를 T에 추가

47 [예제] 정렬된 L (4, 6) 1 (0, 1) 9 (2, 5) 2 (0, 2) 10 (1, 6) 3 (1, 3) 10
(0, 1) 9 (0, 2) 10 (1, 3) 10 (1, 4) 5 (1, 6) 3 (2, 3) 9 (2, 4) 7 (2, 5) 2 (3, 5) 4 (3, 6) 8 (4, 6) 1 (5, 6) 6 (4, 6) 1 (2, 5) 2 (1, 6) 3 (3, 5) 4 (1, 4) 5 (5, 6) 6 (2, 4) 7 (3, 6) 8 (0, 1) 9 (2, 3) 9 (0, 2) 10 (1, 3) 10 2 5 1 4 6 3 8 9 10 7

48

49

50 최소신장트리의 간선의 가중치의 합 = 1 + 2 + 3 + 4 + 6 + 9 = 25

51 Edge 클래스

52 KruskalMST클래스

53 간선들을 가중치로 정렬하는 대신에 line 07에서 Weight_Comparison 클래스를 선언하여mst() 메소드 내의 line 24에서 BY_WEIGHT라는 객체를 만들어 간선의 가중치를 기준으로 간선을 비교하여 line 27∼31에서 우선순위큐(최소힙)에 간선들을 저장 우선순위큐는 line 25에서 자바의 PriorityQueue를 사용하며 (M, BY_WEIGHT)에서 M은 우선순위큐의 크기(size)이고, BY_WEIGHT는 우선순위 비교기준을 의미

54 Kruskal 알고리즘에서 추가하려는 간선이 싸이클을 만드는 간선인지 검사하기 위해, Union-Find 클래스를 활용
이를 위해 line 20에서 UnionFind 객체를 생성, Line 37에서 UnionFind 클래스에 아래와 같이 선언된 isConnected() 메소드를 이용하여 간선의 양쪽 끝 정점들이 동일한 집합에 속해 있는지 검사

55 만약 양쪽 끝 정점이 다른 집합에 속하면, line 38에서 두 집합에 대해 union() 메소드를 호출하여 합집합을 수행하고, line 39에서 간선을 트리에 추가
만약 양쪽 끝 정점이 동일한 집합에 속할 경우, 추가하려는 간선은 무시되고, 다음의 루프 수행을 위해 line 33의 while-루프의 조건을 검사

56

57

58 프로그램 수행 결과

59 수행시간 간선을 정렬(또는 우선순위큐의 삽입과 삭제)하는데 소요되는 시간 O(MlogM) = O(MlogN)
신장트리가 만들어질 때까지 간선에 대해 isConnected()와 union()을 수행하는 시간 O((M+N)log*N) O(MlogN) + O((M+N)log*N) = O(MlogN) 4.4절의 상호배타적 집합을 위한 트리 연산의 [수행시간] 참조

60 9.4.2 Prim알고리즘 Prim 알고리즘은 임의의 시작 정점에서 가장 가까운 정점을 추가하여 간선이 하나의 트리를 만들고, 만들어진 트리에 인접한 가장 가까운 정점을 하나씩 추가하여 최소신장트리를 만든다. Prim의 알고리즘에서는 초기에 트리 T는 임의의 정점 s만을 가지며, 트리에 속하지 않은 각 정점과 T의 정점(들)에 인접한 간선들 중에서 가장 작은 가중치를 가진 간선의 끝점을 찾기 위해 배열 D를 사용

61 Prim 알고리즘 [1] 배열D를 ∞로 초기화한다. 시작정점 s의 D[s] = 0
[2] while (T의 정점 수 < N) [3] T에 속하지 않은 각 정점 i에 대해 D[i]가 최소인 정점 minVertex를 찾아 T에 추가 [4] for (T에 속하지 않은 각 정점 w에 대해서) [5] if (간선 (minVertex, w)의 가중치 < D[w]) [6] D[w] = 간선 (minVertex, w)의 가중치

62 Prim 알고리즘의 step [3]∼[6] (a) 트리에 가장 가까운 정점 minVertex를 찾아(트리 밖에 있는 정점들의 배열 D의 원소들 중에서 최솟값을 찾아) (b) 트리에 추가한 후, 정점 minVertex에 인접하면서 트리에 속하지 않은 각 정점의 D 원소가 이전 값보다 작으면 갱신 (a) (b)

63 [예제] 10 √ 10 10 2 2 7 2 ∞ 4 4 ∞ 5 5 1 9 9 9 5 ∞ 6 6 6 4 ∞ 3 8 1 3 √ 9 1 3 10 10 10 10 10 2 2 √ 5 √ 1 4 4 √ ∞ 6 5 5 1 9 √ 3 6 6 6 8 √ ∞ 8 1 3 9 1 3

64 7 √ 2 √ 2 2 7 2 4 4 6 5 5 6 6 6 4 8 4 √ 8 1 3 1 3 2 2 2 4 4 5 5 9 1 6 6 6 4 4 4 3 1 3 1 3

65 Edge 클래스

66

67 Line 14: 배열 previous를 선언하여 최소신장트리의 간선을 저장
즉, previous[i] = j라면 간선 (i, j)가 트리의 간선 Line 12∼21: 배열 선언 및 초기화 Line 23의 for-루프: N개의 정점을 트리에 추가한 뒤 종료 Line 23∼31: 트리에서 가장 가까운 정점 minVertex를 찾고 Line 33∼43: minVertex에 인접하면서 트리에 속하지 않은 정점의 D 원소 갱신 Line 38∼39: D 원소를 갱신하고 minVertex를 previous 배열의 해당 원소에 저장 마지막으로 배열 previous를 line 44에서 리턴

68 프로그램 수행 결과

69 수행시간(1) Prim 알고리즘은 N번의 반복을 통해 minVertex를 찾고 minVertex에 인접하면서 트리에 속하지 않은 정점에 해당하는 D 의 원소 값을 갱신 PrimMST 클래스에서는 minVertex를 배열 D에서 탐색하는 과정에서 O(N) 시간이 소요되고, minVertex에 인접한 정점들을 검사하여 D의 해당 원소를 갱신하므로 O(N) 시간이 소요된다. 따라서 총 수행시간은 Nx(O(N) +O(N)) = O(N2)

70 수행시간(2) minVertex 찾기 위해 이진힙(Binary Heap)을 사용하면 각 간선에 대한 D의 원소를 갱신하며 힙 연산을 수행해야 하므로 총 O(MlogN) 시간이 필요 M은 그래프 간선의 수, 이진힙은 각 정점에 대응되는 D원소를 저장하므로 힙의 최대 크기는 N 또한 가중치가 갱신되어 감소되었을 때의 힙 연산(decrease_key)에는 O(logN) 시간이 소요 입력그래프가 희소그래프라면, 예를 들어, M = O(N)이라면, 수행시간이 O(MlogN) = O(NlogN)이 되어 이진힙을 사용하는 것이 매우 효율적

71 minVertex 찾기에 7.3.4절에서 배운 피보나치힙(Fibonacci Heap) 자료구조를 사용하면 O(NlogN + M) 시간에 Prim 알고리즘 수행
피보나치힙은 복잡하고 구현도 쉽지 않아서 이론적인 자료구조임

72 9.4.3 Sollin 알고리즘 Sollin 알고리즘은 각 정점을 독립적인 트리로 간주하고, 각 트리에 연결된 간선들 중에서 가장 작은 가중치를 가진 간선을 선택한다. 이때 선택된 간선은 2 개의 트리를 1개의 트리로 만든다. 같은 방법으로 한 개의 트리가 남을 때까지 각 트리에서 최소 가중치 간선을 선택하여 연결 Sollin 알고리즘은 병렬알고리즘(Parallel Algorithm)으로 구현이 쉽다는 장점을 가짐

73 Sollin 알고리즘 [1] 각 정점은 독립적인 트리이다. [2] repeat
[3] 각 트리에 닿아 있는 간선들 중에서 가중치가 가장 작은 간선을 선택하여 트리를 합친다. [4] until (1개의 트리만 남을 때까지)

74 [예제] 2 5 2 5 2 3 2 3 2 7 2 4 7 4 5 1 10 5 9 5 1 9 10 6 5 6 6 4 6 5 4 8 4 8 1 7 1 7 3 3 5 2 3 2 3 7 4 7 4 5 5 9 10 5 9 10 6 6 6 6 5 5 4 8 1 7 1 7

75 수행시간 Sollin 알고리즘에서 repeat-루프가 예제와 같이 각 쌍의 트리가 서로 연결된 간선을 선택하는 경우 최대 logN번 수행 루프 내에서는 각 트리가 자신에 닿아 있는 모든 간선들을 검사하여 최소 가중치를 가진 간선을 선택하므로 O(M) 시간이 소요 따라서 알고리즘의 수행시간은 O(MlogN)

76 9.5 최단경로 알고리즘 Dijkstra 알고리즘 Bellman-Ford Floyd-Warshall 알고리즘

77 9.5.1 Dijkstra 알고리즘 최단경로(Shortest Path) 찾기는 주어진 가중치그래프에서 출발점으로부터 도착점까지의 최단경로를 찾는 문제 Dijkstra 알고리즘: 출발점으로부터 각 정점까지의 최단거리 및 경로를 계산 Dijkstra 알고리즘은Prim의 MST 알고리즘과 매우 유사 차이점 Dijkstra 알고리즘은 출발점이 주어지지지만 Prim알고리즘에서는 출발점이 주어지지 않는다는 것 Prim 알고리즘에서는 배열 D의 원소에 간선의 가중치가 저장되지만, Dijkstra 알고리즘에서는 D의 원소에 출발점으로부터 각 정점까지의 경로의 길이가 저장된다는 것

78 Dijkstra 알고리즘

79 Step [7]의 간선완화(Edge Relaxation)는 minVertex가 step [3]에서 선택된 후에 s로부터 minVertex를 경유하여 정점 w까지의 경로의 길이가 현재의 D[w]보다 더 짧아지면 짧은 길이로 D[w]를 갱신하는 것을 의미 그림은 D[w]가 minVertex 덕분에 40에서 35로 완화된 것을 나타냄

80 [핵심 아이디어] 그리디하게 정점을 선택하여 방문하고, 선택한 정점의 방문 안된 인접한 정점들에 대한 간선완화를 수행한다. 한번 방문된 정점의 D원소 값은 변하지 않는다.

81 [예제] 1 6 7 5 4 3 2 9

82 1 6 7 5 4 3 2 9 출발점 minVertex 1 2 √ 1 3 2 √ 1 3 √ √ 6 1 5 4 4 1 5 2 2 1 2 9 7 6 1

83 1 2 2 1 3 3 minVertex 1 3 1 3 √ √ minVertex 6 1 5 6 4 4 1 5 4 4 1 √ √ 1 5 2 √ 5 2 √ 2 2 1 2 1 9 2 9 7 6 6 1 7 1

84 2 2 1 1 3 3 1 3 1 3 6 5 6 1 1 5 4 4 4 4 minVertex 1 1 5 2 5 2 2 2 1 1 2 9 2 9 √ 7 6 √ 7 6 1 1 √ √ minVertex

85 2 2 1 1 3 3 1 3 1 3 6 6 1 5 1 5 4 4 4 4 √ 1 1 5 2 5 2 √ 2 2 minVertex 2 1 2 1 9 9 7 6 7 6 1 1 minVertex

86 minVertex 6 3 1 7 5 4 2 9

87 Edge 클래스

88

89

90

91 프로그램 수행 결과

92 DijkstraSP 클래스의 line 12∼20은 배열 선언 및 초기화
Line 21: for-루프는 N개의 정점을 방문한 후 종료 Line 22∼29: 출발점에서 아직 방문 안된 정점들 중에서 가장 가까운 정점 minVertex를 찾고, Line 31∼40: minVertex에 인접하면서 방문 안된 정점에 대해 간선완화 수행 Line 37: D의 원소가 갱신될 때 minVertex를 previous의 원소에 저장해둔 뒤, 나중에 최단 경로 추출에 이용 마지막으로 배열 D를 line 42에서 리턴

93 수행시간(1) Dijkstra 알고리즘은 N번의 반복을 거쳐 minVertex를 찾고 minVertex에 인접하면서 방문되지 않은 정점들에 대한 간선완화를 시도 이후 배열 D에서 minVertex를 탐색하는데 O(N) 시간이 소요되고, minVertex에 인접한 정점들을 검사하여 D의 원소들을 갱신하므로 추가로 O(N) 시간이 소요 따라서 총 수행시간은 Nx(O(N) +O(N)) = O(N2)

94 수행시간(2) minVertex를 찾기 위해 이진힙(Binary Heap)을 사용하면 각 정점의 D의 원소를 힙에 저장하므로 힙 크기는 N 또한 minVertex찾기는 delete_min연산으로 수행하고, 간선완화는 decrease_key 연산을 수행한다. 이때 각 연산에 O(logN) 시간이 소요 알고리즘은 minVertex를 N번 찾고, 최대 M번의 간선완화를 수행하므로 총 O(NlogN+MlogN) = O((M+N)logN) 시간이 필요 만약 입력그래프가 희소그래프라면, 예를 들어, M = O(N)이라면, 수행시간이 O(MlogN) = O(NlogN)이 되어 이진힙을 사용하는 것이 매우 효율적 minVertex를 찾기 위해 피보나치힙(Fibonacci Heap)을 사용하면 O(NlogN + M) 시간에 Dijkstra 알고리즘을 수행 Dijkstra알고리즘과Prim알고리즘은 동일한 수행시간을 가짐

95 Dijkstra 알고리즘은 입력그래프에 음수가중치가 있으면 최단경로 찾기에 실패하는 경우가 발생
(a) 출발점 0 방문 (b) 정점 1 방문 (c) 정점 2 방문 (d) 최적해

96 (a) 출발점이 방문되어 visited[0] = true
이후 D[1] = 4, previous[1] = 0 그리고 D[2] = 5, previous[1] = 0으로 각각 갱신 (b) D[1]이 최솟값이므로 정점 1이 방문되고, D[2] = 1, previous[1] = 1로 갱신 (c) 마지막으로 방문되지 않은 정점 2가 방문되고 알고리즘이 종료 그러나 (d)를 보면 출발점 0에서 정점 1까지 최단경로는 [0- 2-1]이고, 경로의 길이는 2 [이러한 문제점이 발생한 이유] Dijkstra 알고리즘이 D의 원소 값의 증가 순으로 minVertex를 선택하고, 한번 방문된 정점의 D 원소를 다시 갱신하지 않기 때문

97 9.5.2 Bellman-Ford 알고리즘 Dijkstra 알고리즘은 음수가중치를 가진 그래프에서 최단경로를 찾지 못함
단, 입력그래프에 싸이클 상의 간선들의 가중치 합이 0보다 작은 음수싸이클(Negative Cycle)이 없어야 만약 어떤 경로에 음수싸이클이 존재한다면, 음수싸이클을 반복할 수록 경로의 길이가 더 짧아지는 모순이 발생하기 때문

98 [핵심 아이디어] 입력그래프에 음수싸이클이 없으므로 출발점에서 각 정점까지 최단경로 상에 있는 간선의 수는 최대 N-1개 이다.

99 [1] 배열 D를 ∞로 초기화한다. 단, D[s] = 0, s는 출발점
[2] for (k = 0; k < N-1; k++) [3] 각 (i, j)에 대하여 [4] if (D[j] > (D[i] + (i, j)의 가중치)) [5] D[j] = D[i] + (i, j)의 가중치 // 간선완화 [6] previous[j] = i; 배열 D를 ∞로 초기화, D[s] = 0 Step [2]의 for-루프는 N-1번 수행되는데, 루프 내에서 각 간선의 양끝 정점에 대한 간선완화를 수행 previous[j] = i는 출발점 s로부터 정점 j까지의 경로상에서 정점 i가 j의 직전 정점이라는 뜻

100 [예제] [0] [0] 출발점 2 2 1 √ √ 1 [0] -2 1 -2 2 √ 3 ∞ ∞ 3 1 1 [0] √ 6 6 1 -1 1 -1 4 4 4 4 ∞ ∞ 1 ∞ 1 ∞ 5 2 ∞ 5 2 ∞ 4 4 -1 -1 2 2 3 3 7 6 7 6 1 1 ∞ ∞ ∞ ∞ 초기화 k = 0

101 [0] [0] 2 2 1 1 1 [0] [0] -2 -1 √ 1 -2 -1 3 3 1 1 [1] √ [1] 6 6 -1 1 -1 1 4 4 4 4 √ √ 1 [3] -2 [3] √ 7 1 7 1 5 2 5 [1] 5 [1] √ √ √ 5 2 √ [1] 4 [1] 4 -1 -1 2 2 3 3 7 6 7 6 1 1 ∞ ∞ 7 [2] 5 [4] √ √ √ √ k = 1 k = 2

102 [0] [0] 2 2 1 1 1 [0] 1 [0] -2 -1 -2 -1 3 3 1 1 [1] [1] 6 6 1 -1 1 -1 4 4 4 4 √ √ -2 [3] √ -2 [3] 7 1 7 1 5 2 4 [6] 5 2 1 [6] [1] 4 [1] 4 -1 -1 2 2 3 3 7 6 7 6 1 1 6 [6] 2 [4] 3 [6] 2 [4] √ √ √ √ k = 3 k = 4

103 [0] [0] 2 2 1 1 1 [0] 1 [0] -2 -1 -2 -1 3 3 1 1 [1] [1] 6 6 1 -1 1 -1 4 4 4 4 √ -2 [3] -2 [3] 6 1 6 1 5 2 1 [6] 5 2 1 [6] √ [7] 4 [7] 4 -1 -1 2 2 3 3 7 6 7 6 1 1 3 [6] 2 [4] 3 [6] 2 [4] k = 5 k = 6

104

105 Bellman-Ford 클래스에서 line 17의 for-루프는 N-1회 반복 수행
Line 21∼22: 각 정점에 대해 if-조건이 만족되면 간선완화 수행 Line 23: 갱신될 때 정점 i를 previous[j]에 저장 Line 30 이후는 결과 출력을 위한 메소드 생략

106 [improvement] 1. k-loop에서 dist[]값이 모두 변화가 없으면 terminate algo 2. dist[v]값이 변한 점v들을 (이미 queue없는 경우) queue에 넣어서, 이 점들에 대해서만 dist값을 다음 iteration에서 수행한다

107 프로그램 수행 결과

108 수행시간 Bellman-Ford알고리즘은 그래프의 인접행렬을 사용하여 N-1번의 반복을 통해 각 간선 <i, j>에 대해 D[j]를 계산하므로 총 수행시간은 (N-1) x N x O(N) = O(N3) 인접리스트를 사용하면 (N-1) x O(M) = O(NM)의 수행시간이 소요

109 9.5.3 Floyd-Warshall 알고리즘 Floyd-Warshall 알고리즘은 모든 정점 쌍 사이의 최단경로 계산
모든 쌍 최단경로(All Pairs Shortest Paths) 알고리즘으로도 불린다. 지도에서 도시간 거리를 계산한 표를 볼 수 있는데, Floyd- Warshall 알고리즘을 사용하면 얻을 수 있음

110 모든 쌍 최단경로 찾기는 출발점을 0에서 N-1까지 바꿔가며 Dijkstra 알고리즘을 각각 수행하는 것으로 모든 쌍에 대한 최단경로를 찾을 수 있음
이때 인접행렬을 사용하면 수행시간은 O(N3) Floyd-Warshall 알고리즘의 수행시간도 O(N3)이지만 Floyd-Warshall 알고리즘은 Dijkstra 알고리즘에 비해 훨씬 알고리즘이 간단하고, 음수가중치 그래프에서도 최단경로를 찾을 수 있다는 장점을 가짐

111 [핵심 아이디어] 입력그래프의 정점들에 0, 1, 2, , N-1로 ID를 부여하고, 정점 ID를 증가시키며 간선완화를 수행

112 [예제] D 1 2 3 4 5 ∞ -2 -3 k=0 D 1 2 3 4 5 ∞ -2 -3

113 k=1 D[0,4]= 8, due to 0 → 1 → 4 D[4,2]=-2, due to 4 → 1 → 2 D 1 2 3 4 5 8 ∞ -2 -3

114 k=2 k=3 D 1 2 3 4 -2 -1 -3 D 1 2 3 4 -1 -2 -3 D 1 2 3 4 -1 -2 -3 k=4

115 Floyd-Warshall 알고리즘 [1] for (i = 0; i < N; i++)
[2] for (j = 0; j < N; j++) [3] D[i][j] = adjMatrix[i][j]; [4] for (k = 0; k < N; k++) [5] for (i = 0; i < N; i++) [6] for (j = 0; j < N; j++) [7] if (D[i][j] > D[i][k] + D[k][j]) [8] D[i][j] = D[i][k] + D[k][j]; 초기화 // 간선완화

116 [1]∼[3]에서 입력그래프의 인접행렬 adjMatrix를 모든 쌍 최단거리를 저장할 배열 D에 복사
[4]의 for-루프는 경유하는 정점 ID를 0부터 N-1까지 수행 모든 쌍 i와 j에 대하여 [5]∼[6]의 이중 for-루프가 i와 j를 각각 0부터 N-1까지 증가시키며, [7]∼[8]에서 간선완화를 수행

117 수행시간 Floyd-Warshall 알고리즘의 수행시간은 [1]∼[3]의 배열 복사에 O(N2)이 소요되고, 이후 for-루프가 3개가 중첩되므로 O(N3)이 소요 따라서 O(N2) + O(N3) = O(N3)

118 Bellman-Ford의 최단경로 알고리즘과 Floyd-Warshall의 최단경로 알고리즘: 동적계획(Dynamic Programming) 알고리즘
동적계획 알고리즘은 작은 부분문제(Subproblem)들의 해를 먼저 계산하고 그 해들을 바탕으로 그 다음으로 큰 부분문제들을 해결하면서 주어진 문제의 해를 계산 반면에 Dijkstra의 최단경로 알고리즘은 그리디 알고리즘으로 입력 전체를 고려하지 않고 지역적인 입력에 대해 그리디하게 선택하며 이를 축적하여 해를 얻음

119 요약 그래프를 자료구조로서 저장하기 위해 인접행렬과 인접리스트가 주로 사용
그래프를 자료구조로서 저장하기 위해 인접행렬과 인접리스트가 주로 사용 그래프는 깊이우선탐색(DFS)과 너비우선탐색(BFS)으로 그래프의 모든 정점들을 방문하며, DFS는 스택을사용하고, BFS는 큐 자료구조를 사용 위상정렬 알고리즘은DFS를 수행하며 각 정점 v의 인접한 모든 정점들의 방문이 끝나자마자 v 를 리스트에 추가한다. 리스트의 역순이 위상정렬이다.

120 Kruskal 알고리즘은 간선들을 가중치로 정렬한 후에, 가장 가중치가 작은 간선이 트리에 싸이클을 만들지 않으면 트리 간선으로 선택하고, 만들면 버리는 일을 반복하여 N-1개의 간선을 선택 Prim 알고리즘은 트리에 인접한 가장 가까운 정점을 하나씩 추가하여 최소신장트리를 만든다. Sollin 알고리즘은 각 트리에서 트리에 연결된 간선들 중에서 가장 작은 가중치를 가진 간선을 선택한다. 이때 선택된 간선은 두 개의 트리를 하나의 트리로 합친다. 이와 같은 방식으로 하나의 트리가 남을 때까지 각 트리에서 최소 가중치 간선을 선택하여 연결

121 Dijkstra 알고리즘은 출발점으로부터 방문 안된 정점들 중에서 가장 가까운 거리의 정점을 방문하고 방문한 정점을 기준으로 간선완화를 수행하여 최단경로를 계산
Bellman-Ford 알고리즘은 음수가중치 그래프에서도 최단경로를 찾을 수 있다. 각 정점에 대한 간선완화를 N-1번 수행 Floyd-Warshall 알고리즘은 모든 정점 쌍 사이의 최단경로를 찾는 알고리즘이다. 입력그래프의 정점들을 0, 1, 2, , N-1로 ID를 부여하고, 정점 ID를 증가시키며 간선완화를 수행