제 6 장 그래프 6.1 그래프의 정의 6.2 용어 및 표현법 6.3 그래프의 표현 방법 6.4 그래프의 순회와 신장 트리 6.5 최 단 경 로 6.6 작업 네트워크

6.1 그래프의 정의 그래프는 퀘니스버그(Köenigsberg)의 다리문제를 해결하기 위하여 1736년 오일러(Euler)가 최초로 사용한 것으로 전해지고 있다. 흐르는 강에 두개의 섬과 강의 양쪽과 두 섬을 연결하는 다리가 7개 임의의 지역에서 출발하여 모든 다리를 단 한 번씩만 지나 지나 제자리에 돌아오는 문제 오일러 : 불가능 증명

각 지역의 정점 : A, B, C, D로 표현 지역과 섬을 연결하는 다리 : 간선 a, b, c, d, e, f, g로 표현 각 정점에 연결된 간선의 수 : 차수(degree) 불가능 : 홀수 개의 간선을 갖는 정점의 수는 0 또는 2이어야 한다 C A B D graph c d g f b a e c d g f b a e

그래프는 각 단위 정보를 정점으로 표현하고, 각 정점으로 표현하고, 각 정점을 간선으로 연결하여 구조화 시킨 자료 구조를 말한다 정점(node, vertex)들의 집합 V와 정점들을 연결하는 간선(edge)들의 집합 E로 구성 그래프 G=(V,E)와 같이 표기한다. 이때 그래프 G에서 정점들의 집합은 V(G)로, 간선들의 집합은 E(G)로 표기한다.

6.2 용어 및 표현법 ■ 무방향 그래프 정점들의 쌍으로 표현하는 간선은 (v1, v2)로 나타내며, 정점들 간에는 순서가 없어 (v1, v2) 는 (v2, v1)과 같은 간선을 말한다. ■ 방향 그래프 정점들의 쌍으로 표현하는 간선은 < v1, v2>로 나타내며, 정점들간의 순서가 매우 중요하다. 따라서 < v1, v2>과 < v2, v1>는 서로 다른 간선을 의미한다. 방향이 있는 간선 < v1, v2>의 정점 v1을 간선의 꼬리라 하고, 정점 v2를 간선의 머리라 한다.

v1 v1 (예) v2 v3 v2 v3 v4 v4 v5 v6 v7 (a) 무방향 그래프 G1 (b) 무방향 그래프 G2 v1 v1 v2 v3 v2 v4 v3 (d) 방향 그래프 G4 (c) 방향 그래프 G3

E(G1) = {(v1, v2),(v1, v3),(v1, v4),(v2, v3),(v2, v4),(v3, v4)} (a) 무방향 그래프 G1 v2 v3 v4 G1 = (V, E) V(G1) = { v1 , v2 , v3 , v4 } E(G1) = {(v1, v2),(v1, v3),(v1, v4),(v2, v3),(v2, v4),(v3, v4)}

E(G2) = {(v1, v2),(v1, v3),(v2, v4),(v2, v5),(v3, v6),(v3, v7)} (b) 무방향 그래프 G2 v2 v3 v4 v5 v6 v7 G2 = (V, E) V(G2) = { v1 , v2 , v3 , v4 , v5 , v6 , v7 } E(G2) = {(v1, v2),(v1, v3),(v2, v4),(v2, v5),(v3, v6),(v3, v7)}

E(G3) = {<v1, v2>, <v2, v1>, <v2, v3>} (c) 방향 그래프 G3 v1 v2 v3 G3 = (V, E) V(G3) = { v1 , v2 , v3 } E(G3) = {<v1, v2>, <v2, v1>, <v2, v3>}

v1 (d) 방향 그래프 G4 v2 v3 v4 G4 = (V, E) V(G4) = { v1 , v2 , v3 , v4 } E(G4) = {<v1, v3>,<v1, v4>,<v2, v1>,<v2, v3>,<v4, v2>,<v4, v3>}

그래프의 용어 (1) 인접과 부속 (2) 차수 간선(v1, v2)가 집합 E(G)에 속한다면, * 간선(v1, v2)는 정점 v1과 v2에 부속되었다 한다 (2) 차수 한 정점의 차수는 그 정점에 부속한 간선들의 수 방향 그래프의 경우 * 한 정점이 연결되는 간선의 고리가 되면 진출 차수 * 연결되는 간선의 머리가 되면 진입 차수

(3) 다중 그래프 같은 간선을 포함하는 그래프 v4 v1 v2 v3

(4) 정규 그래프 (5) 완전 그래프 모든 정점의 차수가 동일한 그래프 모든 정점의 차수가 k일 경우 k차 정규 그래프라고 부른다 (5) 완전 그래프 모든 정점들 사이에 간선이 존재하는 그래프 비방향성 그래프 경우 : 간선의 최대 수가 nC2 = n(n-1)/2 방향성 그래프의 경우 : 간선의 최대 수가 nP2 = n(n-1)

⑹ 부(분) 그래프 : 임의의 그래프 G에 대하여 V(G') ⊆ V(G)이고, E(G') ⊆ E(G)이며, 그래프 G'를 그래프 G의 부분 그래프 또는 부그래프라 한다. (a)무방향 그래프 G1의 몇 부분그래프

v1 v2 v4 v3 (b)방향 그래프 G4의 몇 부분그래프

(7)경로와 사이클 임의의 정점에서 다른 정점에 이르는 정점들의 순서 경로상에 포함된 간선의 수 : 경로의 길이 경로상에 포함된 간선의 수 : 경로의 길이 경로의 시작 정점과 도착정점이 같은 단순경로 : 사이클 사이클이 없는 그래프 : 비사이클 그래프 또는 트리 방향 그래프의 비사이클 그래프 : 대그(dag) v1 v2 v4 v3 v1 (a) v1에서 v3에 이르는 경로 : v1 v2 v4 v3 (길이는 3) (d) v4에서 v3에 이르는 경로 : v4 v2 v1 v3 (길이는 3) v1 v2 v3 v1 : (a)의 사이클 v2 v1v4 v2 : (d)의 사이클 v2 v3 v4 (a) (d) 이한출판사

H1 H2 ⑻ 연결성 무방향 그래프에서 모든 정점들의 쌍에 대하여 경로가 존재하면 그 그래프는 연결되었다 라고 한다. v1 연결되지 않은 그래프 G5

⑼ 연결 요소(connected component) 연결 요소란 무방향성 그래프에서 최대로 연결된 부분 그래프를 말한다. ⑽ 절단점 정점 v와 v에 부속된 모든 간선들을 모두 제거하면 그래프 G가 두 개 이상 연결 요소로 분리되는 정점 v를 절단점이라 한다. 이 때 절단점을 갖지 않는 연결 그래프를 이중 연결 그래프라 한다. 절단점 v0 v4 v6 v1 v3 v7 v5 v2

⑾ 강한 연결 그래프 방향 그래프 G에서 V(G)에 속하는 서로 다른 정점 vi, vj 의 모든 쌍에 대하여, vi에서 vj에 이르는 방향 경로와 vj에서 vi에 이르는 방향경로가 존재한다면, 이 그래프를 강한 연결 그래프라고 한다.

6.3 그래프의 표현 방법 ⑴인접 행렬 인접 행렬은 그래프의 구조를 표현하기 위해서 정점들 사이의 인접 관계를 정점 수만큼의 행과 열을 갖는 행렬을 이용하여 표현하는 방법이다. A= (aij) : n x n의 정방 배열 aij=1, 두 정점 사이에 간선이 존재하는 경우(vi와 vj가 인접한 경우) aij=0, 두 정점 사이에 간선이 존재하지 않는 경우

v1 v2 v3 v1 v2 v3 v1 0 1 0 v2 1 0 1 v3 0 0 0 인접행렬로 표현한G3

v1 v1 v2 v3 v4 v1 0 1 1 1 v2 1 0 1 1 v3 1 1 0 1 v4 1 1 1 0 v2 v3 v4 인접행렬로 표현한G1

⑵ 인접 리스트 그래프의 각각의 정점에 대해 인접한 정점들을 연결 리스트로 표현 그래프를 연결된 정점들만을 이용하여 표현하므로서 기억장소의 낭비를 줄일 수 있다. 반대로 간선의 수가 상대적으로 많은 경우 인접행렬을 사용할 때보다 기억장소 낭비가 심해질 수 있다. 정점에 연결된 노드의 수를 이용하여 쉽게 정점의 차수를 구할 수 있으나, 방향그래프의 경우 진입 차수를 구하기 매우 어렵다는 단점을 갖는다. (역 인접리스트 이용)

(a)그래프 G1 (b)그래프 G1의 인접 리스트 표현 헤드노드 정점링크 v1 v2 v4 v3 v1 v2 v3 v4 \ v2 v1 v3 v4 \ v3 v1 v2 v4 \ v4 v1 v2 v3 \ (a)그래프 G1 (b)그래프 G1의 인접 리스트 표현

(c) 방향 그래프 G6 (d) 방향 그래프 G6의 인접 리스트 표현 헤드노드 정점링크 v1 v1 v2 v4 \ v2 v3 v4 \ v2 v3 v3 v1 \ v4 v4 v3 \ (c) 방향 그래프 G6 (d) 방향 그래프 G6의 인접 리스트 표현

⑶ 역 인접 리스트 진입 차수를 구하기 어려운 문제를 해결하기 위해서, 방향성 그래프의 각 정점으로 들어오는 간선과 인접한 정점으로 구성한 것이 역 인접 리스트이다.

v1 v2 v3 v4 헤드노드 \ 정점링크 v1 v2 v3 v4 그래프 G6의 역 인접 리스트 표현

⑷ 인접 다중 리스트 인접 리스트에서 두 번 표현되는 간선을 한 개의 노드에 저장하여 연결 리스트를 구성하는 방법 인접 리스트가 갖고 있는 문제를 개선한 방법 M 필드는 임의의 간선이 두 번 나타나는 경우, 이미 조사되었음을 표시하기 위하여 사용 M 필드는 한 비트 크기의 마크 필드 M vi vj vi에 대한 연결 vj에 대한 연결 인접 다중 리스트의 노드 구성

N1 간선(v1, v2) v1 v2 N2 N4 v1 N2 간선(v1, v3) v1 v3 N3 N4 v2 N3 헤드노드 간선(v1, v2) v1 v2 N2 N4 v1 N2 간선(v1, v3) v1 v3 N3 N4 v2 N3 간선(v1, v4) v3 v1 v4 \ N5 N4 간선(v2, v3) v4 v2 v3 N5 N6 N5 간선(v2, v4) v2 v4 \ N6 N6 간선(v3, v4) v3 v4 \ \ 리스트 : 정점 v1 : N1→ N2→ N3 정점 v2 : N1→ N4→ N5 정점 v3 : N2→ N4 →N6 정점 v4 : N3→ N5→ N6

과제하기 v1 인접 행렬 인접 리스트 역인접리스트 인접 다중 리스트 v3 v2 v4 v5 v6 v7 v8 v9 v10

6.4 그래프의 순회와 신장 트리 ⑴ 그래프의 순회 무방향 그래프 G=(V,E)와 V(G)에 속해 있는 정점 v가 주어졌을 때 v로부터 도달할 수 있는 모든 정점을 한번씩 방문하는 것을 그래프의 순회라고 한다. 깊이 우선 탐색(DFS : Depth First Search) 너비 우선 탐색(BFS : Breadth First Search)

v1 v2 v3 v9 v7 v6 v5 v4 v8 그래프 순회를 위한 그래프 G7

깊이우선 탐색 (DFS) (트리의 전순위 운행을 그래프에 일반화) ① 출발 정점 i를 방문 ② i에 인접한 방문하지 않은 한 정점 j를 선정 j를 시작점으로 다시 깊이 우선 탐색 시작 ③ 인접한 정점 중에서 아직 방문하지 않은 정점 j가 없으면 제일 나중에 방문한 정점으로 되돌아가서 ②를 수행. ④ 만일 되돌아갈 정점이나 방문할 정점이 없으면 탐색 완료

스택을 이용한 깊이우선탐색(DFS) 알고리즘 ① 특정 정점을 시작 정점으로 선택 ② 선택된 정점을 방문했음을 나타내는 “방문” 표시 ③ 선택된 정점에 인접되어 연결된 다른 정점들을 검사 ④ 검사된 정점들 중에서 아직 방문하지 않은 정점이 있으면 그 정점을 새롭게 선택하고 원래 정점은 스택에 넣는다. ⑤ 만일 검사한 정점들 중에 방문하지 않은 정점이 하나도 없 으면 마지막으로 삽입된 정점을 꺼내 새로 선택 ⑥ 스택이 빌 때까지 ② - ⑤의 과정 반복

v1 v2 v3 v9 v7 v6 v5 v4 v8 방문 순서 : v1 v2 v4 v8 v5 v6 v3 v7 v9

[알고리즘] Depth First Search void DFS(v) struct graph_node *v; { int n; struct graph_node *w; visited[v] = TRUE; for(v에 인접한 각 정점 w) if(visited[w] == FALSE) DFS(w); }

2) 너비우선 탐색(BFS) ① 시작 정점 v를 선택하여 방문 ③ 방문한 정점들에 인접하면서 아직 방문하지 않은 정점에 대해 너비 우선 탐색 ④ 더 방문할 정점이 없을 때까지 위 과정이 반복

[알고리즘] 큐를 이용한 BFS void BFS(char v) struct graph_node *v; { int n; struct graph_node *w; visited[v] = true; insert_queue(v); while(queue != NULL) delete_queue(v) for(v에 인접한 모든 정점w) if(visited[w] == false){ insert_queue(w); visited[w] = true; } }

v1 v2 v3 v9 v7 v6 v5 v4 v8 방문 순서 : v1 v2 v3 v4 v5 v6 v7 v8 v9

⑵ 신장트리(spanning tree) 1) 신장 트리의 정의 그래프 G의 간선들로만 구성 G의 모든 정점들이 포함된 트리 ▶ BFS, DFS 시 방문에 사용한 간선들의 집합과 동일 ▶ 신장 트리에 사용되지 않은 간선 중 임의의 간선을 신장 트리에 첨가하면 사이클이 만들어져 트리가 되지 않는다 깊이우선 신장트리 : DFS를 사용해 만들어진 신장 트리 너비우선 신장트리 : BFS를 사용해 만들어진 신장 트리

v1 v2 v4 v3 v1 v1 v1 v2 v3 v2 v3 v2 v3 v4 v4 v4 (a) 그래프 G1 (b) 신장 트리의 예

v1 v2 v3 v9 v7 v6 v5 v8 v4 v4 (a) DFS 신장 트리 (b) BFS 신장트리

2) 신장 트리의 성질 그래프의 모든 정점을 포함하면서 최소의 간선으로 연결되어 있는 최소 부분 그래프 정점이 n인 경우 최소 연결 부분 그래프로서 n-1 개의 간선을 지님 응용: * 통신 네트워크 설계 * 도시간의 네트워크 설계에서 최소의 링크 수를 구하는 데 사용

(예) n개의 도시를 연결하는 경우 간선이 n-1개 필요(최소) 연결하는 방법도 여러가지 가중치 그래프(네트워크) : 다양한 척도에 따라 간선들에게 가중치 부여 (ex 도로 건설비용, 거리, 건설 시간 등) 최소 비용으로 도시를 최단거리로 연결할 수 있는 도로를 선택 최소 비용 신장 트리( minimal cost spanning tree) : 각 간선에 가중치를 부여하여 가중치의 총합이 가장 적은 신장 트리 * 그래프 내에 포함되어 있는 간선들만을 포함 * 정점의 수가 n 일 때 n-1 개의 간선만 포함 * 사이클이 존재하지 않는 그래프

3) 최소 비용 신장 트리 구성방법 (a)가중치 그래프 (b) 최소 비용 신장 트리 v1 v3 v4 v2 v6 v5 1 2 3 최저의 비용을 갖는 신장 트리 그래프 G의 신장 트리에서 최소 비용 신장 트리를 구하는 방법 : 각 단계에서 최적의 해를 구하는 과정을 반복하여 문제 해결 그리드 알고리즘(greedy algorithm) * Kruskal 알고리즘 * Prim 알고리즘 * Sollin 알고리즘 (a)가중치 그래프 (b) 최소 비용 신장 트리 v1 v3 v4 v2 v6 v5 1 2 3 4 5 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6

prim 알고리즘 가중치 그래프 G =(V,E)에서 임의의 한 정점을 선택하여 시작 한번에 하나의 간선을 선택하여 최소 비용 신장 트리를 구성해 나가는 방식 ⒜ 현재 간선들 중에서 가중치가 가장 적은 간선을 선택. ⒝ 선택된 간선으로 두 정점을 연결했을 때 사이클이 생기면 간선을 버리고 그렇지 않으면 신장 트리에 삽입 ⒞ 기존의 신장 트리를 이루는 간선의 한 끝 정점에 연결된 간선들을 검사 ⒟ 검사한 간선들 중에서 아직 트리에 들어있지 않으면서 가중치가 가장 적은 간선을 선택 ⒠ 선택된 간선은 간선 리스트에서 제거 ⒡ 간선 리스트에 더 이상의 간선이 남지 않을 때까지 ⒝∼⒠를 반복

v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 (c)정점v1,v3에 연결된 간선 중에서 가중치 가장 작은 간선 선택 (b)가중치가 가장 작은 간선 선택 (a)가중치 그래프 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 (e)정점 v1,v3,v4,v6에 연결된 간선 중에서 가중치가 가장 작은 간선 선택 후 사이클을 만들지 않는 간선 선택 (d)정점v1,v3, v6에 연결된 간선 중에서 가중치가 가장 작은 간선 선택 (f)정점 v1,v2,v3,v4, v6에 연결된 간선 중에서 가중치가 가장 작은 간선 선택 후 사이클을 만들지 않는 간선 선택

[알고리즘] void prim() { T = {}/* 신장 트리*/ E(G)로부터 최소 비용 간선 (v, w) 선택; while(T가 n-1보다 적은 수의 간선을 포함 && (E(G) != EMPTY)){ E(G)에서 간선(v, w) 제거; if(v, w)가 신장트리 T에서 사이클을 만들지 않음) (v, w)를 T에 추가; 정점 v, w를 W에 추가; else (v, w)를 버림; E(G)로부터 W 내의 정점과 최소 비용으로 연결된 간선 (v, w) 선택; }

kruskal 알고리즘 n개의 정점으로 이루어진 그래프 G=(V,E)에서 각 단계에서 가장 적은 가중치의 간선을 선택 신장 트리의 간선을 선택해 나가는 방식 ⒜ 현재 간선들 중에서 가중치가 가장 적은 간선을 선택. ⒝ 선택된 간선으로 두 정점을 연결했을 때 사이클이 생기면 간선을 버리고 그렇지 않으면 신장 트리에 삽입 ⒞ 선택된 간선은 간선 리스트에서 제거 ⒟ 간선 리스트에 더 이상의 간선이 남지 않을 때까지 ⒜∼ ⒞를 반복

v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 (c) 간선 중에서 가중치 가장 작은 간선 선택 (a)가중치 그래프 (b) 간선 중에서 가중치가 가장 작은 간선 선택 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 (d) 간선 중에서 가중치가 가장 작은 간선 선택 (e) 간선 중에서 가중치가 가장 작은 간선 선택 (f) 간선 중에서 가중치가 가장 작은 간선 선택

[알고리즘] void kruskal() { T = /* 신장 트리*/ while(T가 n-1보다 적은 수의 간선을 포함 && (E(G) != EMPTY)){ E(G)로부터 최소 비용 간선 (v, w) 선택; E(G)에서 간선(v, w) 제거; if(v, w)가 신장트리 T에서 사이클을 만들지 않음) (v, w)를 T에 추가; else (v, w)를 버림; }

sollin 알고리즘 각 단계에서 여러 개의 간선이 선택되는 방식 ⒜ 각 정점에 연결된 간설들 중에 최소 가중치를 가지는 간선들을 선택 ⒝ 선택된 간선들 중 중복된 간선들을 제거 ⒞ 나머지 간선들 중에서 최소 가중치를 간선을 선택 ⒟ 선택한 간선이 사이클을 이루면 그 간선을 버림 ⒠ 선택한 간선이 사이클을 이루지 않으면 트리에 삽입

v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 (c) 간선 (v2,v5) 중복 제거 (a)가중치 그래프 (b) 각 정점에 연결된 간선 중에서 최소 가중치 간선 선택, 트리에 삽입 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 v1 v3 v4 v2 v6 v5 1 2 3 4 5 v1 v3 v4 v2 v6 v5 1 2 3 4 5 6 (d) 남은 간선들 중 최소 가중치 간선(v2,v3) 선택간선(v1,v4),(v3,v4)는 사이클이 되므로 제거 (f) 그래프G의 모든 간선 선택 트리에 삽입하거나 제거되어 최소 비용 신장 트리 생성 (e) 남은 간선들 중 최소 가중치 간선(v1,v2),(v3,v5), (v5,v6)는 사이클이 되므로 제거

6.5 최단 경로 개념 -한 지점에서 임의의 지점에 이르기 위한 가중치의 합이 최소가 되는 신장 트리 - MST(최소비용 신장 트리)는 그래프 전체에 대한 최소경비, 최단경로는 특정 지점에서의 최소경비라는 측면에서 다르다. 그래프 내에서 MST는 여러 개 있을 수 있으나, 최단경로는 하나뿐이다.

최단경로 알고리즘 ·하나의 시작점에서의 최단경로 Dijkstra algorithm : 시작 정점 v1으로부터 최단거리가 결정된 정점들의 집합 S와 최단거리를 찾기 위하여 남은 정점들의 집합T를 이용하여 최단거리를 구하는 알고리즘 ·Greedy algorithm 의 일종 기본 idea ·어떤 정점에 대한 최단경로를 확정하면, 더 이상의 최단경로는 없다고 본다.(greedy algorithm) ·최단경로가 확정되지 않은 정점에 대하여, 지금까지 알려진 경로보다 더 짧은 경로가 밝혀지면 갱신한다.

딕스트라(dijstra) 알고리즘 ① 정점 v1을 시작으로 정점들의 집합 S와 T를 정의 ② 시작 정점 v1과 연결된 정점vi의 가중치(거리)를 dist[i](1≤ i ≤n)로 정의하면, dist[1]=0으로 초기화하고, 나머지 정점들 (v2 ∼ vn)의 dist[i]는 ∞로 초기화 ③ 시작 정점v1을 집합 S에 포함 ④ 정점vn을 마지막으로 모든 정점들이 집합 S에 포함될 때까지 다음의 과정을 반복 ⒜ 집합 S에 최근 포함된 정점 v을 주축으로 연결된 집합 T의 정점, w의 가중치(거리) cost(v,w)와 dist[v]의 합을 dist[w]의 값과 비교하여 작은 값을 dist[w]의 값으로 다시 정의 dist[w]=min(dist[w],dist[v]+cost(v,w)) ⒝ S에 포함되지 않은 정점들(집합 T의 정점) 중에서 가장 작은 dist[] 값을 갖는 정점을 선택하여 S에 포함 시킨다. 이 정점을 w라 하자.

9 v1 v3 v7 v6 v8 v5 v4 v2 10 17 3 8 12 14 15 2 v1 v2 v3 v4 v5 v6 v7 v8 v1 0 2 15 ∞ ∞ ∞ ∞ ∞ v2 ∞ 0 10 9 ∞ 14 ∞ ∞ v3 ∞ ∞ 0 ∞ 12 ∞ ∞ ∞ v4 ∞ ∞ ∞ 0 ∞ 10 ∞ ∞ v5 ∞ ∞ ∞ ∞ 0 ∞ 8 10 v6 ∞ ∞ ∞ ∞ ∞ 0 ∞ 17 v7 ∞ ∞ ∞ ∞ ∞ ∞ 0 3 v8 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 그래프와 비용 인접 행렬

v1 : dist[2]=min(dist[2],dist[1]+cost(1,2))=min(∞,0+2)=min(∞,2)=2 【1단계】 v1 : dist[2]=min(dist[2],dist[1]+cost(1,2))=min(∞,0+2)=min(∞,2)=2 dist[3]=min(dist[3],dist[1]+cost(1,3))=min(∞,0+15)=min(∞,15)=15 dist[4]=min(dist[4],dist[1]+cost(1,4))=min(∞,0+∞)=min(∞,∞)=∞ dist[5]=min(dist[5],dist[1]+cost(1,5))=min(∞,0+∞)=min(∞,∞)=∞ dist[6]=min(dist[6],dist[1]+cost(1,6))=min(∞,0+∞)=min(∞,∞)=∞ dist[7]=min(dist[7],dist[1]+cost(1,7))=min(∞,0+∞)=min(∞,∞)=∞ dist[8]=min(dist[8],dist[1]+cost(1,8))=min(∞,0+∞)=min(∞,∞)=∞ 【2단계】 v2 : dist[3]=min(dist[3],dist[2]+cost(2,3))=min(15,2+10)=min(15,12)=12 dist[4]=min(dist[4],dist[2]+cost(2,4))=min(∞,2+9)=min(∞,11)=11 dist[5]=min(dist[5],dist[2]+cost(2,5))=min(∞,2+∞)=min(∞,∞)=∞ dist[6]=min(dist[6],dist[2]+cost(2,6))=min(∞,2+14)=min(∞,6)=16 dist[7]=min(dist[7],dist[2]+cost(2,7))=min(∞,2+∞)=min(∞,∞)=∞ dist[8]=min(dist[8],dist[2]+cost(2,8))=min(∞,2+∞)=min(∞,∞)=∞

v4 : dist[3]=min(dist[3],dist[4]+cost(4,3))=min(12,11+∞)=min(12,∞)=12 【3단계】 v4 : dist[3]=min(dist[3],dist[4]+cost(4,3))=min(12,11+∞)=min(12,∞)=12 dist[5]=min(dist[5],dist[4]+cost(4,5))=min(∞,11+∞)=min(∞,∞)=∞ dist[6]=min(dist[6],dist[4]+cost(4,6))=min(16,11+10)=min(16,21)=16 dist[7]=min(dist[7],dist[4]+cost(4,7))=min(∞,11+∞)=min(∞,∞)=∞ dist[8]=min(dist[8],dist[4]+cost(4,8))=min(∞,11+∞)=min(∞,∞)=∞ 【4단계】 v3 : dist[5]=min(dist[5],dist[3]+cost(3,5))=min(∞,12+12)=min(∞,24)=24 dist[6]=min(dist[6],dist[3]+cost(3,6))=min(16,12+∞)=min(16,∞)=16 dist[7]=min(dist[7],dist[3]+cost(3,7))=min(∞,12+∞)=min(∞,∞)=∞ dist[8]=min(dist[8],dist[3]+cost(3,8))=min(∞,12+∞)=min(∞,∞)=∞

v6 : dist[5]=min(dist[5],dist[6]+cost(6,5))=min(24,16+∞)=min(24,∞)=16 【5단계】 v6 : dist[5]=min(dist[5],dist[6]+cost(6,5))=min(24,16+∞)=min(24,∞)=16 dist[7]=min(dist[7],dist[6]+cost(6,7))=min(∞,116+∞)=min(∞,∞)=∞ dist[8]=min(dist[8],dist[6]+cost(6,8))=min(∞,16+17)=min(∞,33)=33 【6단계】 v5 : dist[7]=min(dist[7],dist[5]+cost(5,7))=min(∞,24+8)=min(∞,32)=∞ dist[8]=min(dist[8],dist[5]+cost(5,8))=min(∞,24+10)=min(33,34)=33 【7단계】 v7 :dist[8]=min(dist[8],dist[7]+cost(7,8))=min(33,32+2)=min(33,34)=33 【8단계】 v8을 집합 S에 포함 시키고, T는 공집합이 된다. 따라서 알고리즘의 수행을 마친다.

최단 경로를 구하는 과정 집합 S 집합 T 배열 dist[i] 반복단계 W [1] [2] [3] [4] [5] [6] [7] [8] 초기 { } {v1,v2,v3,v4,v5,v6,v7,v8} − ∞ 1 {v1} {v2,v3,v4,v5,v6,v7,v8} v1 2 15 {v1,v2} {v3,v4,v5,v6,v7,v8} v2 12 11 16 3 {v1,v2,v3} {v4,v5,v6,v7,v8} v3 4 {v1,v2,v3,v4} {v5,v6,v7,v8} v4 24 5 {v1,v2,v3,v4,v5} {v6,v7,v8} v5 33 6 {v1,v2,v3,v4,v5,v6} {v7,v8} v6 32 7 {v1,v2,v3,v4,v5,v6,v7} {v8} v7 8 v8

[알고리즘] void shortest_path(int v, int cost[][], int dist[], int n) { int I, w, u; char s[]; /* 부울 변수*/ for(i=1; i<n; I++){ s[i] = FALSE dist[i]=cost[v][i] /* 시작정점 v에서 정점 I 까지 최단 경로 길이 */ } s[v]=TRUE; dist[v] = 0; for(i=1; i<n-2; I++){ u=choose(n) ; /* s[w[가 false인 모든 w에 대해 dist[u] = minimun dist[u]의 u를 변환*/

s[u] = TRUE; for(w=1; w<n; w++){ if(s[w] ==FALSE) if(dist[u]+cost[u][w]<dist[w]) dist[w] = dist[u] + cost[u][w]; }

과제하기 1 1. 최소 비용 신장 트리 구하기 Prim 알고리즘 Kruskal 알고리즘 Solin 알고리즘 v1 v2 v3 16 v1 v2 21 11 6 v3 6 v4 19 14 33 10 v5 18 v6

과제하기 2 2. 다음 그래프를 탐색 DFS BFS v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

과제하기 3 3. 다음 그래프의 신장 트리 구하기 v1 v2 v3 v4 v5 v6 v7 v8 v9

과제하기 4 4. 최단 경로 구하기 비용 인접 행렬 단계별 과정 과정 표 작성 v5 v4 v3 v6 v2 v1 v8 v7 1500 v4 1200 250 800 v3 1000 v6 v2 1400 300 1000 900 v1 1700 v8 1000 v7

6.6 작업 네트워크 프로젝트를 수행하는 과정을 작업들의 관계로 표현한 방향 그래프 위상정렬과 AOV 네트워크 임계 경로와 AOE 네트워크

q위상 정렬 사이클이 없는 방향성 그래프의 정점 Vi가 정점 Vj를 선행하는 것을 만족하는 모든 정점들을 선형적인 순서로 나열하는 것 qAOV(Activity On Vertex) 네트워크 선형적인 순서의 작업들 관계를 이용하여 프로젝트의 수행과정을 나타낸 그래프 cf) AOE(Activity On Edge) 네트워크 q위상 정렬 알고리즘 ①선행자를 갖지 않는 정점을 기록 ②기록된 정점에서부터 나오는 간선제거 ③모든 정점이 다 기록되도록 ①,② 를 반복

v1 v4 v3 v6 v7 v5 v2 (a)방향 그래프 G v4 v3 v6 v7 v5 v2 (b)선행자 없는 정점 v1제거 v1에서 나가는 간선제거

v5 v4 v7 v3 v6 v5 v4 v7 v6 (c) 선행자 없는 정점 v2 제거 v2에서 나가는 간선 제거 (d)선행자 없는 정점 v3 제거 v3에서 나가는 간선 제거 v6

v5 v7 v7 v6 v6 (e)선행자 없는 정점 v4 제거 v7 (h)선행자 없는 정점 v7 제거 (f)선행자 없는 정점 v5 제거 v5에서 나가는 간선 제거 v7 (h)선행자 없는 정점 v7 제거 (g)선행자 없는 정점 v6 제거 v6에서 나가는 간선 제거 위상 순서 : v1, v2, v3, v4, v5, v6, v7

adj_head adj_head count link vertex link v2 v3 v4 v1 \ v2 v4 1 v5 \ v3 v4 1 v6 \ v4 3 v5 v6 \ v5 v7 2 \ v6 2 v7 \ v7 2 \ 방향그래프 G의 헤드 노드와 인접 리스트

[알고리즘]

q AOE(Activity On Edge) 네트워크 프로젝트의 수행을 위한 작업들을 방향 간선으로 표현하고 공정을 나타내는 네트워크이다 즉 간선으로 표시된 작업은 간선의 꼬리에 있는 정점의 공정이 완료되지 않은 한 시작되지 못하는 것이다 q 임계경로 AOE 네트워크에서 각 작업들은 병행하여 수행될 수 있으므로, 그 프로젝트를 완료하는 최소시간은 출발점에서 완료점까지의 최장경로에 대한 수행시간의 합, 즉 길이가 된다. 이 때 이러한 가장 긴 경로(longest path) 를 임계경로(critical path) 라고 한다.

AOE 네트워크 v2 a4=1 a7=9 v7 a1=6 a10=2 v5 a8=7 v1 v3 v9 a5=1 a2=4 v8 a11=4 a3=5 v4 v6 a9=4 a6=2 * 임계 경로 : v1, v2, v5, v7, v9 * 길이의 합 : 6+1+9+2=18 * 프로젝트 시작 정점인 v1과 완료를 나타내는 v9 사이에는 한 개 이상의 임계 경로가 존재 : v1, v2, v5, v8, v9

임계 경로상의 정점 공정(event) 해 석 프로젝트 수행 과정 v1 프로젝트의 시작을 말함 v2 해 석 v1 프로젝트의 시작을 말함 v2 작업(activity) a1의 완료를 뜻함 v5 작업(activity) a4, a5의 완료를 뜻함 v7 작업(activity) a7의 완료를 뜻함 v9 프로젝트의 완료를 뜻함 프로젝트 수행 과정 작업 a1, a2 그리고 a3는 프로젝트의 시작 이후 병행되어 수행될 수 있음을 의미 작업 a4, a5는 공정을 나타내는 v2, v3가 완료되기 전에는 수행될 수 없으며 작업 a6는 공정 v4가 완료된 후 수행되는 작업임을 말한다. 작업 a7, a8은 공정 v5가 완료된 후 병행 수행되고, 작업 a9는 공정 v6가 완료된 후 수행될 수 있는 것이다 작업 a7와 a8을 공정 v5와 v6이 끝난 후에 수행되도록 하고자 하는 경우에는 간 선< v6, v5 >을 추가하고 작업 a12= 0의 가짜 작업을 삽입함으로써 이루어 짐

AOE 네트워크의 중요한시간 earliest time : 공정 vi가 완료될수 있는 시간을 의미, 프로젝트의 시작정점 v1에서 정점 vj까지의 최장 경로길이 earliest start time : 어떤 공정이 완료될 수 있는 earliest time 에 의해 결정되는 시간으로 그 정점에서 나오는 간선으로 표현된 작업들의 시작시간 latest time : 작업 ai가 가장 늦게 시작될 수 있는 시간을 의미 e(6) = 5, l(6) = 8, e(7) = 7, l(7) = 7 earliest timer과 latest time과의 차 ㅣ(i) – e(i) : 어떤 작업 ai의 임계도 어떤 작업의 임계도 : 그 프로젝트 전체를 종료하는데 필요로 하는 시간에 영향을 주지 않는 여유 시간을 나타냄

earliest time, latest time, 임계도 작업(activity) earliest time(e) latest time(l) 임계도(l-e) a1 a2 2 a3 3 a4 6 a5 4 a6 5 8 a7 7 a8 a9 10 a10 16 a11 14