Chap 6: Graphs

Size: px

Start display at page:

Download "Chap 6: Graphs"

한선 어금
5 years ago
Views:

1 5. 작업네트워크 (Activity Networks) 작업 (Activity) 부분프로젝트 (divide and conquer) 각각의작업들이완료되어야전체프로젝트가성공적으로완료 두가지종류의네트워크 Activity on Vertex (AOV) Networks Activity on Edge (AOE) Networks 6 장. 그래프 (Page 1)

2 5.1 AOV Network 몇가지정의들 : AOV Network: Digraph G (vertex = 작업, edge = 작업들간의선행관계 ) u 에서 v 까지방향경로 (directed path) 가존재할경우 u = predecessor of v, v = successor of u Immediate Predecessor (Successor): <u, v> Partial Order: transitive 이며 irreflexive 한선행관계 Topological Order: vertex 들간의선행관계를고려하여모든 vertex 의선형순서 (linear ordering) 를정의 Topological Sort 작업들간에는 partial order 만존재할수있으므로, topological order 는여러개존재가능 Topological sort: 그중하나의 topological order 생성 6 장. 그래프 (Page 2)

3 AOV Network 의예 과목번호 과목명 선수과목 C1 C언어 None C2 이산수학 None C3 자료구조 C1, C2 C4 미분적분 I None C5 미분적분 II C4 C6 선형대수 C5 C7 알고리즘분석 C3, C6 C8 어셈블리어 C3 C9 운영체제 C7, C8 C1 프로그래밍언어 C7 C11 컴파일러설계 C1 C12 인공지능 C7 C13 계산이론 C7 C14 병렬알고리즘 C13 C15 수치해석 C5 C1 C2 C4 C3 C5 C8 C7 C6 C15 C9 C1 C12 C13 C11 C14 (b) AOV network representing courses as vertices and edges as prerequisites (a) Courses needed for a computer science degree at a hypothetical university 6 장. 그래프 (Page 3)

4 Program 6.13: Topological Sort for ( i = ; i < n; i++) { if (every vertex has a predecessor) { fprintf (stderr, "Network has a cycle.\ n"); exit (1); } pick a vertex v that has no predecessors; output v; delete v and all edges leading out of v from the network; } 6 장. 그래프 (Page 4)

5 그림 6.39: Topological Sort 의동작 V 1 V 1 V 1 V V 2 V 4 V 2 V 4 V 2 V 4 V 3 V 5 V 3 V 5 V 5 (a) initial (b) V (c) V 3 V 1 V 1 V 4 V 4 V 4 V 5 (d) V 2 (e) V 5 (f) V 1 (g) V 4 생성된 topological order : V, V 3, V 2, V 5, V 1, V 4 6 장. 그래프 (Page 5)

6 AOV Network 의표현 임의의 vertex 가 predecessor 를갖는지조사 각 vertex 에대해 immediate predecessor 의수를나타내는 count field 저장 Vertex 와그에부속된모든 edge 들을삭제 AOV network 을인접리스트로표현 count link struct node { int vertex; struct node *link; }; typedef struct { int count; struct node *link; } hdnode; hdnode graph[max_vertices]; v v 1 v 2 v 3 v 4 v Null 2 Null Null 4 5 Null 5 4 Null 3 Null 6 장. 그래프 (Page 6)

7 Program 6.14: topsort() void topsort(hdnodes graph[], int n) { int i, j, k, top; struct node *ptr; top = -1; // Predecessor가없는 vertex들의 stack 구성 for (i = ; i < n; i++) if (!graph[i].count) { graph[i].count = top; top = i; } for (i = ; i < n; i++) if (top == -1) { fprintf(stderr, "Network has a cycle.\ n"); exit(1); } else { j = top; top = graph[top].count; // Stack에서제거 printf("v%d, ", j); for (ptr = graph[j].link; ptr!= NULL; ptr = ptr->link) { k = ptr->vertex; // Successor vertex들의 count 감소 graph[k].count--; if (!graph[k].count) { // 새로운 vertex를 stack에삽입 graph[k].count = top; top = k; } } } } 6 장. 그래프 (Page 7)

8 5.2 AOE Network AOE Network 의정의 Edge: 작업 Vertex: 사건 (event) vertex 로들어오는모든작업이완료할때발생 vertex 에서나가는작업은사건이발생하기전까지는시작될수없다. start v a = 6 a 2 = 5 a 1 = 4 v 1 v 2 v 3 a 3 = 1 v 4 a 4 = 1 a 5 = 2 v 5 a 6 = 8 a 7 = 6 v 6 v 7 a 8 = 4 a 9 = 2 v 8 a 1 = 4 finish event v v 1 v 4 v 7 v 8 interpretation start of project completion of activity a completion of activity a 3 and a 4 completion of activity a 7 and a 8 completion of project (b) Interpretation of some of the events in the activity graph of (a) (a) AOE Network. Activity graph of a hypothetical project 6 장. 그래프 (Page 8)

9 AOE Network 에서 Critical Path 임계경로 (Critical Path) 시작 vertex 에서종료 vertex 까지가장긴경로 병목현상의원인이됨. Event v i 의 Earliest Time, earliest(i) 시작 vertex v 에서 v i 까지가는가장긴경로의길이 earliest(4) = 7 early(i): 작업 a i 의가장빠른시작시간 a i 가 <k, l> 일경우, early(i) = earliest(k) early(6) = 7 작업 a i 의 Latest Time, late(i) 프로젝트기간을증가시키지않으면서작업이시작될수있는가장나중시간 early(5) = 5 & late(5) = 7, early(7) = 7 & late(7) = 7 임계작업 (Critical Activity) early(i) = late(i) 인작업 a i 6 장. 그래프 (Page 9)

10 Earliest Time 의계산 작업 a i 가 edge <k, l> 로표현된다고가정 early(i) = earliest[k] late(i) = latest[l] duration of a i earliest[j] 의계산 topsort 알고리즘을이용하여시작 vertex 부터 AOE network 를순회 earliest[] = earliest[j] = max{earliest[i] + duration of <i, j>} for i {immediate predecessors of j} 아래문장을 topsort() 함수의 else 절마지막에추가 if (earliest[k] < earliest[j] + ptr->duration) earliest[k] = earliest[j] + ptr->duration 6 장. 그래프 (Page 1)

11 그림 6.42: 그림 6.41 의인접리스트 count link vertex dur link V NULL V NULL V NULL V NULL V NULL V NULL V NULL V NULL V 8 2 NULL 장. 그래프 (Page 11)

12 그림 6.42: earliest 의계산 Earliest [] [1] [2] [3] [4] [5] [6] [7] [8] Stack initial [] output V [3, 2, 1] output V [5, 2, 1] output V [2, 1] output V [1] output V [4] output V [7, 6] output V [6] output V [8] output V 8 6 장. 그래프 (Page 12)

13 Latest Times 의계산 마지막 vertex 부터 topsort 알고리즘을이용하여 AOE network 을역방향으로순회 latest[n-1] = earliest[n-1] latest[j] = min{latest[i] duration of <j, i>} for i {immediate successors of j} 역인접리스트 (inverse adjacency list) 를이용 아래문장을 topsort() 함수의 else 절마지막에추가 if (latest[k] > latest[j] ptr->duration) latest[k] = latest[j] ptr->duration 6 장. 그래프 (Page 13)

14 그림 6.43: 그림 6.41 의역인접리스트 count link vertex dur link V 3 NULL V 1 1 V 2 1 V 3 1 V 4 2 V 5 1 V 6 1 V 7 1 V 8 6 NULL 4 NULL 5 NULL NULL 4 8 NULL NULL 5 4 NULL 7 4 NULL 장. 그래프 (Page 14)

15 그림 6.43: latest 의계산 Earliest [] [1] [2] [3] [4] [5] [6] [7] [8] Stack initial [8] output V [7, 6] output V [5, 6] output V [3, 6] output V [6] output V [4] output V [2, 1] output V [1] output V [] 6 장. 그래프 (Page 15)

16 작업 a i 의 Early(i) 와 Late(i) 계산 작업 a i 가 edge <k, l> 로표현된다고가정 early(i) = earliest[k] late(i) = latest[l] duration of a i Activity Early Late Late Early Critical a a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a Yes No No Yes No No Yes Yes No Yes Yes 6 장. 그래프 (Page 16)

Chap 6: Graphs

Chap 6: Graphs AOV Network 의표현 임의의 vertex 가 predecessor 를갖는지조사 각 vertex 에대해 immediate predecessor 의수를나타내는 count field 저장 Vertex 와그에부속된모든 edge 들을삭제 AOV network 을인접리스트로표현 count link struct node { int vertex; struct node