Chap 6: Graphs

Size: px

Start display at page:

Download "Chap 6: Graphs"

윤조 곽
5 years ago
Views:

1 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 v 3 v 4 v Null Null 1 4 Null 4 5 Null 5 4 Null 3 Null 6 장. 그래프 (Page 61)

2 Program 6.14: topsort() void topsort(hdnode 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 6)

3 연습문제 아래그래프에서가능한 topological order 를모두나열하시오. A P B F E T D K 6 장. 그래프 (Page 63)

4 5. AOE Network AOE Network 의정의 Edge: 작업 Vertex: 사건 (event) vertex 로들어오는모든작업이완료할때발생 vertex 에서나가는작업은사건이발생하기전까지는시작될수없다. start v a = 6 a = 5 a 1 = 4 v 1 v v 3 a 3 = 1 v 4 a 4 = 1 a 5 = v 5 a 6 = 8 a 7 = 6 v 6 v 7 a 8 = 4 a 9 = 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 64)

5 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 65)

6 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 66)

7 그림 6.4: 그림 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 NULL 장. 그래프 (Page 67)

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

9 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 69)

10 그림 6.43: 그림 6.41 의역인접리스트 count link vertex dur link V 3 NULL V 1 1 V 1 V 3 1 V 4 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 7)

11 그림 6.43: latest 의계산 Earliest [] [1] [] [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 [, 1] output V [1] output V [] 6 장. 그래프 (Page 71)

12 작업 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 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 7)

Chap 6: Graphs

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