그래프 추상 데이타 타입(1/9) 개요 Koenigsberg 다리 문제 차수(degree) : 정점에 연결된 간선의 수 오일러 행로(Eulerian walk) .. g c C d A D e D A C B c a d b e g f Kneiphof B f a b (a) Koenigsberg의 Pregal강의 일부 (b) 오일러의 그래프

그래프 추상 데이타 타입(2/9) 정의 그래프 G : 2개의 집합 V와 E로 구성 무방향그래프(undirected graph) V : 공집합이 아닌 정점(vertex)의 유한집합 E : 간선(edges)이라고 하는 정점 쌍들의 집합 표기 : G=(V,E) 무방향그래프(undirected graph) 간선을 나타내는 정점의 쌍에 순서 없음 방향 그래프(directed graph) 방향을 가지는 정점의 쌍 <u, v>로 표시 (u는 꼬리(tail), v는 머리(head)) <v, u>와 <u, v>는 서로 다른 간선

그래프 추상 데이타 타입(3/9) 예제 그래프 V(G1)={0,1,2,3} E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} V(G2)={0,1,2,3,4,5,6) E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)} V(G3)={0,1,2} E(G3)={<0,1>,<1,0>,<1,2>} 1 2 1 2 1 3 3 4 5 6 2 G1 G2 G3

그래프 추상 데이타 타입(4/9) 정의 그래프의 제한 사항 자기 간선(self edge) 또는 자기 루프(self loop) 없음 동일 간선의 중복 없음(다중그래프(multigraph))는 이 제한이 없음 1 1 3 2 2 자기 간선을 가진 그래프 다중 그래프 완전 그래프(complete graph) : n개의 정점과 n(n-1)/2개의 간선을 가진 그래프 (u,v)가 E(G)의 한 간선이라면 u와 v는 인접(adjacent)한다 간선 (u,v)는 정점 u와 v에 부속(incident)된다 그래프 G의 부분그래프(subgraph) : V(G')  V(G) 이고 E(G')  E(G)인 그래프 G'

그래프 추상 데이타 타입(5/9) 정점 u로부터 정점 v까지의 경로(path) 경로의 길이(length) 그래프 G에서 (u,i1), (i1,i2), ..., (ik,v)를 E(G)에 속한 간선들이라 할 때, 정점열 u, i1, i2, ..., ik, v를 말함 경로의 길이(length) 경로상에 있는 간선의 수 단순 경로(simple path) 경로상에서 처음과 마지막을 제외한 모든 정점들이 서로 다름 단순 방향 경로(simple directed path) 사이클(cycle) 처음과 마지막 정점이 같은 단순 경로

그래프 추상 데이타 타입(6/9) G1 G1의 서브그래프 G3 G3의 서브그래프 1 2 3 1 2 3 2 1 (i) (ii) 3 2 1 G1 1 2 3 (i) (ii) (iii) (iv) G1의 서브그래프 2 1 G3 1 2 (i) (ii) (iii) (iv) G3의 서브그래프

그래프 추상 데이타 타입(7/9) 연결 요소(connected component) : 최대 연결 부분 그래프(maximal connected subgraph) 강력 연결(strongly connected) : 방향그래프에서 V(G)에 속한 서로 다른 두 정점 u, v의 모든 쌍에 대해서, u에서 v로, 또한 v에서 u로의 방향 경로(directed path)가 존재 강력 연결 요소(strongly connected component) : 강하게 연결된 최대 부분그래프 두 개의 연결요소를 갖는 그래프

그래프 추상 데이타 타입(8/9) 차수(degree) : 정점에 부속한 간선들의 수 진입차수(in-degree) G3의 강력 연결요소 1 2 차수(degree) : 정점에 부속한 간선들의 수 진입차수(in-degree) 임의의 정점 v가 머리가 되는 간선들의 수 진출차수(out-degree) v가 꼬리가 되는 간선들의 수 간선의 수 다이그래프(digraph) : 방향 그래프 (n개의 정점과 e개의 간선을 가진 그래프)

그래프 추상 데이타 타입(9/9) ADT Graph < 그래프 추상 데이타 타입 > objects: 공집합이 아닌 정점의 집합과 무방향 간선의 집합으로 각 간선은 정점의 쌍이다. functions: for all graph ∈ Graph, v, v1, and v2 ∈ Vertices Graph Create() ::= return an empty graph Graph InsertVertex(graph, v) ::= return a graph with v inserted v has no incident edges Graph InsertEdge(graph, v1, v2) ::= return a graph with a new edge between v1 and v2 Graph DeleteVertex(graph, v) ::= return a graph in which v and all edges incident to it are removed Graph DeleteEdge(graph, v1, v2) ::= return a graph in which the edge(v1, v2) is removed Leave the incident nodes in the graph Boolean IsEmpty(graph) ::= if(graph = = empty graph) return TRUE else return FALSE List Adjacent(graph, v) ::= return a list of all vertices that are adjacent to v < 그래프 추상 데이타 타입 >

그래프 표현법 인접행렬 (Adjacency Matrix) G=(V,E)는 정점의 수가 n(n≥1)인 그래프 간선 (vi, vj)E(G)  a[i][j]=1 간선 (vi, vj)E(G)  a[i][j]=0 필요 공간 : n2 비트 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 2 3 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 2 3 0 1 2 0 1 0 1 0 1 0 0 0 1 2 G1 의 인접행렬 G3 의 인접행렬 G4 의 인접행렬 무방향 그래프: 어떤 정점 i의 차수는 그 행의 합 : 방향 그래프: 행의 합은 진출차수, 열의 합은 진입차수 인접행렬의 수행 시간 : 최소한 O(n2) 희소 그래프(sparse graph) : O(e+n)

인접리스트(1/4) 인접리스트 (Adjacency Lists) 인접행렬의 n행들을 n개의 chains으로 표현 n개의 정점, e개의 간선의 무방향 그래프 n개의 헤드노드, 2e개의 리스트 노드가 필요 방향그래프 : e개의 리스트 노드 연결 리스트 노드의 순차적 저장 : 배열 node[] node[i] = 정점 i에 대한 리스트의 시작 지점 Node[n] = n + 2e – 1 정점 i와 인접한 정점  node[i], … , node[i+1]-1에 저장 (0≤i≤n) 역인접리스트(inverse adjacency lists) 리스트가 표현하는 정점에 인접한 각 정점에 대해 하나의 노드를 둠

인접리스트(2/4) G1 인접 리스트 G3 인접 리스트 G4 인접 리스트 [0] [1] [2] [3] [0] [1] [2] adjLists data link [0] [1] [2] [3] 3 1 2 2 3 1 3 1 2 G1 인접 리스트 adjLists [0] [1] [2] 1 2 G3 인접 리스트 adjLists [0] [1] [2] [3] 2 1 3 3 1 2 [4] [5] [6] [7] 5 6 4 5 7 6 G4 인접 리스트 (

인접리스트(3/4) int nodes[n + 2*e +1]; 그래프 G4의 순차 표현 G3의 역인접리스트 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 그래프 G4의 순차 표현 G3의 역인접리스트

인접다중리스트 (Adjacency Multilists) 간선(u,v)는 두 개의 엔트리로 표현 : u를 위한 리스트, v를 위한 리스트에 나타남 새로운 노드 구조 m vertex 1 vertex 2 list 1 list 2 1 N1 N3 N0 edge (0,1) 2 N2 edge (0,2) 3 N4 edge (0,3) N5 edge (1,2) edge (1,3) edge (2,3) adjNodes [0] [1] [2] [3] The lists are vertex 0: N0 → N1 → N2 vertex 1: N0 → N3 → N4 vertex 2: N1 → N3 → N5 vertex 3: N2 → N4 → N5 G1에 대한 인접 다중리스트

가중치 간선(Weighted Edges) 그래프의 간선에 가중치(weights) 부여 인접행렬 : 행렬 엔트리에 a[i][j]의 가중치 정보 저장 인접리스트 : 노드 구조에 weight 필드를 추가 네트워크(network) : 가중치 간선을 가진 그래프

그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문 (2) v에 인접하고 방문하지 않은 한 정점 w를 선택 (3) w를 시작점으로 다시 깊이 우선 탐색 시작 (4) 모든 인접 정점을 방문한 정점 u에 도달하면, 최근에 방문한 정점 중 아직 방문을 안한 정점 w와 인접하고 있는 정점으로 되돌아감 (5) 정점 w로부터 다시 깊이 우선 탐색 시작 (6) 방문을 한 정점들로부터 방문하지 않은 정점으로 더 이상 갈 수 없을 때 종료

깊이 우선 탐색(1/3) #define FALSE 0 #define TRUE 1 short int visited[MAX_VERTICES]; void dfs (int v) {/* 그래프의 정점 v에서 시작하는 깊이 우선 탐색 */ nodePointer w; visited[v] = TRUE; printf(“%5d”, v); for (w = graph[v]; w; w = w → link) if (!visited [w→vertex]) dfs (w→vertex); } 깊이-우선 탐색

깊이 우선 탐색(2/3) 예제 6.1 0, 1, 3, 7, 4, 5, 2, 6 순으로 방문 [0] [1] [2] [3] [4] 1 2 3 4 5 6 7 adjLists ( a) [0] [1] [2] [3] [4] [5] [6] [7] 1 2 3 4 5 6 1 7 1 7 2 7 2 7 3 4 5 6 (b) 그래프 G와 그 인접리스트

깊이 우선 탐색(3/3) DFS의 분석 탐색을 끝내는 시간 O (e) v에 인접한 모든 정점들을 찾는데 O (n)의 시간

너비 우선 탐색(1/2) 너비 우선 탐색(BFS; Breadth-First Search) 예제 6.2 시작 정점 v를 방문 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문 예제 6.2 0, 1, 2, 3, 4, 5, 6, 7 순으로 방문 1 2 3 4 5 6 7

너비 우선 탐색(2/2) BFS의 분석 전체 시간 O(n2) 인접 리스트 표현 : 전체 비용 O(e) void bfs(int v) {/* 정점 v에서 시작하는 너비 우선 탐색. 전역배열 visited는 0으로 초기화됨} node_pointer w; queue_pointer front, rear; front = rear = NULL; /* 큐의 초기화 */ printf(“%5d”, v); visited[v] = TRUE; addq(&front, &rear, v); while (front){ v = deleteq(&front); for (w=graph[v]; w; w=w→link) if (!visited[w→vertex]) { printf(“%5d”, w→vertex); addq(&front, &rear, w→vertex); visited[w→vertex] = TRUE; } BFS의 분석 전체 시간 O(n2) 인접 리스트 표현 : 전체 비용 O(e)

연결요소 연결요소(connected component) Component의 분석 방문하지 않은 정점 v에 대해 DFS(v) 또는 BFS(v)를 반복 호출로 구함 void connect(void) { /* 그래프의 연결 요소 결정 */ int i; for (i=0; i<n; i++) if (!visited[i]) { dfs(i); printf(“\n”); } Component의 분석 인접리스트로 표현: 모든 연결요소들 생성 시간은 O(n+e) 인접행렬로 표현 : O(n2)

신장트리(1/2) 신장트리(spanning tree) : G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리 깊이-우선 신장트리(depth-first spanning tree) 너비-우선 신장트리(breadth-first spanning tree) 완전 그래프와 이 그래프의 세 신장트리 1 2 1 2 3 4 5 6 3 4 5 6 7 7 (a) DFS(0) 신장 트리 (b) BFS(0) 신장 트리

신장트리(2/2) 예제 6.2 [회로 등식의 생성] 신장트리는 G의 최소부분 그래프(minimal subgraph) 전기 네트워크에 대한 신장트리 구함 비트리 간선을 신장트리에 한번에 하나씩 도입 Kirchoff의 제2 법칙 이용하여 회로 등식 얻음 신장트리는 G의 최소부분 그래프(minimal subgraph) G'로서 V(G') = V(G)이고 G'는 연결되어 있음 신장트리는 n-1개의 간선 가짐

이중결합요소(1/6) 단절점(articulation point) 이중 결합 그래프(biconnected graph) 그래프의 정점들중 이 정점과 이 정점에 부속한 모든 간선들 삭제시, 최소한 두 개의 연결요소를 만들게 하는 정점 이중 결합 그래프(biconnected graph) 절점이 없는 연결 그래프 이중 결합 요소(biconnected component) 최대 이중결합 부분그래프(maximal biconnected subgraph) 1 2 3 4 5 7 6 8 9 1 2 3 4 5 9 6 7 8 연결 그래프 이중 결합 요소

이중결합요소(2/6) 연결 무방향 그래프의 이중결합요소 깊이-우선 신장 트리를 이용 연결 그래프 1 2 3 4 5 8 6 7 9 4 9 8 9 8 1 2 3 4 5 9 6 7 8 3 1 7 7 5 2 2 3 5 4 6 1 6 연결 그래프 루트를 3으로 하는 깊이-우선 신장 트리

이중결합요소(3/6) 백 간선(back edge) 교차 간선(cross edge) low (w) 1 2 3 4 5 6 7 8 u가 v의 조상이거나 v가 u의 조상인 비트리 간선(u,v) 교차 간선(cross edge) 백 간선이 아닌 비트리 간선 low (w) w의 후손들과 많아야 하나의 백 간선으로 된 경로를 이용해 w로부터 도달할 수 있는 가장 적은 깊이 우선번호 low(w) = min{dfn(w), min{low(x) | x는 w의 자식}, min{dfn(x) | (w,x)는 백 간선}} Vertex 1 2 3 4 5 6 7 8 9 dfn 10 low 신장 트리에 대한 dfn 값과 low 값

이중결합요소(4/6) #define MIN2(x, y) ((x) < (y) ? (x) : (y)) short int dfn[MAX_VERTICES]; short int low[MAX_VERTICES]; int num; void dfnlow (int u, int v) /* compute dfn and low while performing a dfs search beginning at vertex u, v is the parent of u (if any) */ nodePointer ptr; int w; dfn[u] = low[u] = num++; for (ptr = graph[u]; ptr; ptr = ptr→link) { w = ptr → vertex; if (dfn[w] <0) { /* w is an unvisited vertex */ dfnlow(w,u); low[u] = MIN2(low[u], low[w]); } else if (w != v) low[u] = MIN2(low[u], dfn[w]); Dfn 과 low 의 계산

이중결합요소(5/6) void init(void) { int i; for (i=0; i<n; i++) { visited[i] = FALSE; dfn[i] = low[i] = -1; } num = 0; dfn과 low의 초기화 void bicon (int u, int v) {/* compute dfn and low, and output the edges of G by their biconnected components, v is the parent (if any) of u in the resulting spanning tree. It is assumed that all entries of dfn[] have been initialized to -1, num is initially to 0, and the stack is initially empty */ nodePointer ptr; int w, x, y; dfn[u] = low[u] = num++;

이중결합요소(6/6) for (ptr = graph[u]; ptr; ptr = ptr→link) { w = ptr → vertex; if (v!= w && dfn[w] < dfn[u]) push(u, w); /* add edge to stack */ if (dfn[w] <0) { /* w has not been visited */ bicon(w, u); low[u] = MIN2(low[u], low[w]); if (low[w] >= dfn[u]) { printf(“New biconnected component : ”); do { /* delete edge from stack */ pop(&x, &y); printf(“ <%d, %d>”, x, y); } while (!((x = = u) && (y = = w))); printf(“\n”); } else if (w!=v) low[u] = MIN2(low[u], dfn[w]); 그래프의 이중결합 요소

최소비용 신장트리 최소비용 신장트리(minimum-cost spanning tree) 최저의 비용을 갖는 신장트리 Kruskal, Prim, Sollin 알고리즘 갈망법(greedy method) 최적의 해를 단계별로 구한다 각 단계에서는 몇 개의 판단 기준에 따라 최상의 결정을 내린다 한번 내려진 결정은 뒤에 번복이 불가능하므로 각각의 결정이 가능한 해를 도출해낼 수 있는 지 확인 신장트리의 제한 조건 (1) 그래프내에 있는 간선들만을 사용 (2) 정확하게 n-1개의 간선만을 사용 (3) 사이클을 생성하는 간선을 사용 금지

Kruskal 알고리즘(1/3) 알고리즘 한번에 하나씩 T에 간선을 추가해가면서 최소비용 신장트리 T를 구축 G는 연결되어 있고 n>0개의 정점을 가지므로 정확하게 n-1개의 간선만이 T에 포함됨.

Kruskal 알고리즘(2/3) 예제 6.3 Kruskal 알고리즘의 각 단계 28 10 1 10 10 1 1 1 14 5 5 28 10 1 10 10 1 1 1 14 5 5 16 5 5 6 2 24 6 6 2 2 6 2 25 4 4 18 4 4 12 12 3 22 3 3 3 ( d) ( a) ( b) ( c) 10 10 10 10 1 1 1 1 14 14 14 14 5 16 5 16 5 5 16 6 6 6 6 2 2 2 2 25 4 4 4 4 12 12 12 12 22 3 22 3 3 3 ( g) ( h) ( e) ( f) Kruskal 알고리즘의 각 단계

Kruskal 알고리즘(3/3) T = { }; while ((T가 n-1개 미만의 간선을 포함) && (E가 공백이 아님)) { E에서 최소 비용 간선 (v,w) 선택; E에서 (v,w)를 삭제; if (v,w)가 T에서 사이클을 만들지 않으면 add (v, w) to T; else discard (v,w); } if (T가 n-1개 미만의 간선을 포함) cout << "신장 트리 없음" << endl; Kruskal 알고리즘 정리 6.1 G를 무방향 연결 그래프라 하자. Kruskal 알고리즘은 최소비용 신장트리를 생성한다.

Prim 알고리즘(1/3) 알고리즘 한번에 한 간선씩 최소 비용 신장 트리를 구축 각 단계에서 선택된 간선의 집합은 트리 하나의 정점으로 된 트리 T에서 시작 최소 비용 간선 (u,v)를 구해 T U {(u,v)}이 트리가 되면 T에 추가 T에 n-1개의 간선이 포함될 때까지 간선의 추가 단계를 반복 추가된 간선이 사이클을 형성하지 않도록 각 단계 에서 간선 (u,v)를 선택할 때 u 또는 v중 오직 하나만 T에 속한 것을 고른다.

Prim 알고리즘(2/3) Prim 알고리즘 T = { }; TV ={0}; /* 정점 0으로 시작. 간선은 비어 있음.*/ while(T의 간선수가 n-1보다 적음) { u ∈ TV이고 v ∈ TV인 최소 비용 간선을 (u, v)라 함; if (그런 간선이 없음) break; v를 TV에 추가; (u, v)를 T에 추가; } if (T의 간선수가 n-1보다 적음) printf ("신장트리 없음\n“); Prim 알고리즘

Prim 알고리즘(3/3) Prim 알고리즘의 진행 단계 10 1 10 1 10 1 5 5 5 6 6 6 2 2 2 25 25 10 1 10 1 10 1 5 5 5 6 6 6 2 2 2 25 25 4 4 4 22 3 3 3 (a) (b) (c) 10 1 10 1 10 1 14 16 16 5 5 5 6 6 6 2 2 2 25 25 25 4 4 4 12 12 12 22 22 22 3 3 3 (d) (e) (f) Prim 알고리즘의 진행 단계

Sollin 알고리즘 알고리즘 각 단계에서 여러개의 간선을 선택 각 단계에서는 포리스트에 있는 각 트리에 대해 하나의 간선을 선택 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용 간선 선택된 간선은 구축중인 신장트리에 추가 오직 하나의 트리만이 존재 or 더 이상 선택할 간선이 없을 때 종료 10 1 10 1 14 14 16 5 5 6 6 2 2 25 4 4 12 12 22 22 3 3 (a) (b) Sollin 알고리즘의 단계들

최단경로와 이행적 폐쇄 단일 시발점/모든 종점: 음이 아닌 간선 비용 문제 : 시발 정점 v에서부터 G의 모든 다른 정점까지의 최단경로를 구하는 것 45 50 10 경로 길이 1 2 1) 0, 3 10 30 2) 0, 3, 4 25 10 20 15 20 35 3) 0, 3, 4, 1 45 4) 0, 2 45 3 4 5 15 3 (a) 그래프 (b) 0에서부터의 최단 경로 그래프와 정점 0에서 모든 종점까지의 최단경로

하나의 출발점/모든 목표점: 음이 아닌 간선 비용(1/3) ShortestPath 함수 : 최단 경로의 길이의 결정 ShortestPath의 분석 n개의 정점을 가진 그래프에 대한 수행시간은 O (n2) void shortestPath(int v, int cost[][MAX_VERTICES]), int distance[], int n, short int found[]) {/* distance[i] represents the shortest path from vertex v to I, found[i] is 0 if the shortest path from i has not been found and a 1 if it has, cost is the adjacency matrix */ int i, u, w; for (i=0; i<n; i++) { found[i] = FALSE; distance[i] = cost[v][i]; } found[v] = TRUE; distance[v] = 0; for (i=0; i<n-2; i++) { u = choose(distance, n, found); found[u] = TRUE; for (w=0; w<n; w++) if (!found[w]) if (distance[u] + cost[u][w] < distance[w]) distance[w] = distance[u] + cost[u][w];

하나의 출발점/모든 목표점: 음이 아닌 간선 비용(2/3) 예제 6.5 Boston 4 1500 Chicago San Francisco 1200 3 250 800 1 2 1000 Denver 300 5 New York 1000 1400 1700 7 Los Angeles 900 New Orleans 1000 6 Miami (a) 방향 그래프 0 1 2 3 4 5 6 7 1 300 2 1000 800 3 1200 4 1500 250 5 1000 900 1400 6 1000 7 1700 (b) 길이-인접 행렬

하나의 출발점/모든 목표점: 음이 아닌 간선 비용(3/3) 반복 선택된 정점 거 리 LA SF DEN CHI BOST NY MIA NO [0] [1] [2] [3] [4] [5] [6] [7] 초기 ---- ¥ ¥ ¥ 1500 250 ¥ ¥ 1 5 ¥ ¥ ¥ 1250 250 1150 1650 2 6 ¥ ¥ ¥ 1250 250 1150 1650 3 3 ¥ ¥ 2450 1250 250 1150 1650 4 7 3350 ¥ 2450 1250 250 1150 1650 5 2 3350 3250 2450 1250 250 1150 1650 6 1 3350 3250 2450 1250 250 1150 1650 방향그래프에 대한 ShortestPath의 작동

하나의 출발점/모든 목표점:일반적 가중치(1/3) 음수 길이 사이클이 존재할 경우 최단 길이 경로가 존재하지 않는다. 1 2 5 7 -5 음의 길이 간선을 가진 방향 그래프 1 2 -2 음의 길이 사이클을 가진 방향 그래프 동적 프로그래밍 방법 : 모든 u에 대해 distn-1[u]를 구함 distk[u] = min{distk-1[u], min{distk-1[i] + length[i][u]}} i

하나의 출발점/모든 목표점:일반적 가중치(2/3) 예제 6.5 1 2 3 4 6 5 -2 -1 ( a) 방향 그래프 (b) distk 음의 길이 간선을 가진 최단 경로

하나의 출발점/모든 목표점:일반적 가중치(3/3) Bellman과 Ford 알고리즘 void BellmanFord(int n, int v) { /* single source all destination shortest paths with negative edge lengths. */ for (int I =0; i<n; i++) dist[i] = length[v][i]; /* initialize dist */ for (int k =2; k <= n-1; k++) for (each u such that u != v and u has at least one incoming edge) for (each <i, u> in the edge) if (dist[u] > dist[i] + length[i][u]) dist[u] = dist[i] + length[i][u]; } 최단 경로를 계산하는 Bellman과 Ford 알고리즘 BellmanFord의 분석 인접행렬 O(n3), 인접 리스트 O(ne)

모든 쌍의 최단경로(1/3) uv인 모든 정점의 쌍 u와 v간의 최단경로를 구하는 것 연속적으로 A-1, A0, A1, A2, …, An-1을 생성하는 것 인덱스가 K보다 큰 정점을 통과하지 않는 i에서 j까지의 최단 경로가 인덱스가 k인 정점을 통과하지 않으면 그 길이는 Ak-1[i][j]가 된다. 최단 경로가 k를 통과한다고 하면 경로는 i에서 k까지의 경로와 k에서 j까지의 경로로 구성. 이러한 i에서 k까지 또, k에서 j까지의 부분 경로 둘 다 k-1보다 큰 인덱스를 가진 정점을 통과하지 않음. 이 경로들이 길이는 Ak-1[i][k], Ak-1[k][j]가 된다. Ak[i][j] = min{Ak-1[i][j], Ak-1[i][k] + A k-1[k][j]}, k  0 A-1[i][j] = length[i][j]

모든 쌍의 최단경로(2/3) uv인 모든 정점의 쌍 u와 v간의 최단경로를 구하는 것 Ak[i][j] = min{Ak-1[i][j], Ak-1[i][k] + A k-1[k][j], k  0 A-1[i][j] = length[i][j] void allcosts (int cost[][MAX_VERTICES], int distance[][MAX_VERTICES], int n) { /* 각 정점에서 다른 모든 정점으로의 거리 계산, cost는 인접 행렬, distance는 거리값의 행렬 */} int i, j, k; for (i=0; i<n; i++) for (j=0; j<n; j++) distance[i][j] = cost[i][j]; for (k=0; k<n; k++) if distance[j][k] + distance[k][j] < distance[i][j]) distance[i][j] = distance[i][k] + distance[k][j]; } 모든 쌍의 최단경로 AllLengths의 분석 전체 시간은 O(n3)

모든 쌍의 최단경로(3/3) 예제 6.6 모든 쌍의 최단 경로 문제의 예 A 1 2 A 1 2 1 4 11 4 11 1 6 2 -1 1 2 A 1 2 1 4 11 4 11 4 11 2 1 6 2 1 6 2 3 2 2 3 2 3 7 (a) 방향그래프 (b) A-1 (c) A0 A 1 1 2 A 2 1 2 4 6 4 6 1 6 2 1 5 2 2 3 7 2 3 7 (d) A1 (e) A2 모든 쌍의 최단 경로 문제의 예

이행적 폐쇄(1/2) 이행적 폐쇄 행렬(A+) 반사 이행적 폐쇄 행렬(A*) i에서 j로의 경로 길이 0  A+[i][j] = 1 인 행렬 반사 이행적 폐쇄 행렬(A*) i에서 j로의 경로 길이 0  A*[i][j] = 1 인 행렬 0 1 2 3 4 1 1 1 2 1 1 2 3 4 3 1 4 1 ( a) 방향 그래프 G ( b) 인접행렬 A 0 1 2 3 4 0 1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 3 1 1 1 3 1 1 1 4 1 1 1 4 1 1 1 ( c) A + ( d) A *

이행적 폐쇄(2/2) A+ A* : A+의 대각선에 있는 항을 모두 1로 설정 전체 시간은 O(n3) 간선 <i, j>  G  length[i][j] = 1, otherwise, length[i][j] = LARGE All Lengths 종료시 length[i][j]  +  A+[i][j]=1 A* : A+의 대각선에 있는 항을 모두 1로 설정 전체 시간은 O(n3)

작업 네트워크 AOV(activity on vertex) 네트워크 : 정점이 작업을, 간선이 작업간의 선행 관계를 나타내는 방향그래프 G C1 C2 C4 C5 C6 C3 C7 C8 C15 C9 C10 C12 C13 C11 C14 (a) 가상적인 대학에서 컴퓨터 과학 학위에 필요한 과목들 (b) 과목은 정점으로, 선수과목은 간선으로 포현한 AOV 네트워크 An activity-on-vertex(AOV) 네트워크

AOV 네트워크(1/6) 정의 정점 i로부터 정점 j로의 방향 경로 존재하면 정점 i를 정점 j의 선행자(predecessor) 간선 <i, j>가 존재하면 정점 i를 정점 j의 직속 선행자(immediate predecessor) i가 j의 선행자 → j는 i의 후속자(successor) i가 j의 직속 선행자 → j는 i의 직속 후속자(immediate successor) 모든 세 쌍 i, j, k에 대해 I  j 이고 j  k → I  k 가 성립하면 관계는 이행적(transitive) S에 속한 모든 원소 x에 대해 x  x가 성립하지 않으면 관계는 집합 S상에서 비반사적(irreflexive) 부분 순서(partial order) : 이행적, 비반사적인 선행 관계 위상순서(topological order) : 임의의 두 정점 i, j에 대해 네트워크에서 i가 j의 선행자이면 선형순서에서도 i가 j 앞에 있는 그래프 정점의 선형 순서

AOV 네트워크(2/6) 위상 정렬 알고리즘의 설계 AOV 네크워크를 입력. n을 정점의 수라 함. for(int i = 0; i < n; i++) // 정점들을 출력 { if(모든 정점이 선행자가 있음) return; /* 네크워크에 사이클이 있어 수행 불가능. */ 선행자가 없는 정점 v를 선택; cout << v; 정점 v와 v에서 나온 모든 간선들을 네트워크에서 삭제; } 위상 정렬 알고리즘의 설계

AOV 네트워크(3/6) (a) 초기 (b) 정점 0 삭제 (c) 정점 3 삭제 (d) 정점 2 삭제 (e) 정점 5 삭제 1 1 1 2 4 2 4 2 4 3 5 3 5 5 (a) 초기 (b) 정점 0 삭제 (c) 정점 3 삭제 1 1 4 4 4 5 (d) 정점 2 삭제 (e) 정점 5 삭제 (f) 정점 1 삭제 생성된 위상 순서 : 0, 3, 2, 5, 1, 4

AOV 네트워크(4/6) 위상 정렬 알고리즘에 의해 사용되는 내부 표현 count first data link [0] 1 1 2 1 3 [1] 4 1 [2] 1 4 1 5 [3] 1 5 1 4 [4] 3 [5] 2 위상 정렬 알고리즘에 의해 사용되는 내부 표현

AOV 네트워크(5/6) TopologicalOrder의 분석 점근적 계산 시간 O (e+n) void topSort (hdnodes graph[], int[]) { int i, j, k, top; nodePointer ptr; /* create a stack of vertices with no predecessors */ top = -1; for (i=0; i<n; i++) if (!graph[i].count = top); graph[i].count = top; top = i; } if (top = = -1) { fprintf(stderr, “\nNetwork has a cycle. Sort terminated. \n”); exit (EXIT_FAILURE); else { j = top; /* unstack a vertex */

AOV 네트워크(6/6) 위상 정렬 top = graph[top].count; printf (“v%d, ”, j); for (ptr = graph[j].link; ptr; ptr = ptr → link) { /* decrease the count of the successor vertices of j*/ k = ptr→vertex; graph[k].count --; if (!graph[k].count) { /* add vertex k to the stack */ graph[k].count = top; top = k; } 위상 정렬

AOE 네트워크(1/8) AOE(activity on edge) 네트워크 방향 간선 : 프로젝트에서 수행되어야 할 작업 정점 : 사건(event) (사건은 어떤 작업의 완료를 알림) 정점에서 나오는 간선이 의미하는 작업은 그 정점에서의 사건이 발생할 때까지 시작될 수 없다.

AOE 네트워크(2/8) (a) 가상 프로젝트의 작업 네트워크 사 건 의 미 (b) 네트워크 (a)의 몇몇 사건의 의미 1 4 2 3 5 4 8 7 6 a = 6 start finish a = 1 a = 9 a = 2 10 a = 4 11 a = 7 a = 4 9 a = 2 a = 5 (a) 가상 프로젝트의 작업 네트워크 사 건 의 미 프로젝트의 시작 작업 a1의 종료 1 4 작업 a4와 a5의 종료 작업 a8와 a9의 종료 7 프로젝트의 종료 8 (b) 네트워크 (a)의 몇몇 사건의 의미

AOE 네트워크(3/8) 임계경로(critical path) 가장 이른 시간(earliest time) e(i) 시작 정점에서 종료 정점까지의 최장 경로(longest path) 가장 이른 시간(earliest time) e(i) 시작 정점 0에서 정점 i 까지의 최장 경로 길이 가장 늦은 시간(latest time) l(i) 프로젝트 기간을 지연시키지 않으면서 가장 늦게 작업을 시작할 수 있는 시간 임계작업(critical activity) : e(i) = l(i) 인 작업 임계경로 분석의 목적 임계작업들을 식별해내어 가용 자원을 집중시킴으로써 프로젝트 완료 시간을 단축

AOE 네트워크(4/8) 가장 이른 작업 시간과 가장 늦은 작업 시간 가장 이른 시간의 계산 e(i)= ee[k] (ee[k] : 가장 이른 사건 발생 시간) l(i) = le[l] - 작업 ai의 기간 (le[l] : 가장 늦은 사건 발생 시간) 가장 이른 시간의 계산 ee[j] = max { ee[i] + <i, j>의 시간 } (P(j)는 j의 직속 선행자의 집합) 전진단계 iP(j) if (earliest[k] < earliest[j] + ptr → duration) earliest[k] = earliest[j] + ptr → duration);

AOE 네트워크(5/8) (a) 인접리스트 (b) ee의 계산 1 2 6 4 3 5 9 7 8 [0] [1] [2] [3] 1 2 6 4 3 5 9 7 8 [0] [1] [2] [3] [4] [5] [6] [7] [8] count first vertex dur link (a) 인접리스트 (b) ee의 계산

AOE 네트워크(6/8) 가장 늦은 시간의 계산 le[j] = min { le[i] - <j, i>의 기간 } (S(j)는 j의 직속 후속자들의 집합) iP(j) le[8]=ee[8]=18 le[6]=min{le[8]-2}=16 le[7]=min{le[8]-4}=14 le[4]=min{le[6]-9, le[7]-7}=7 le[1]=min{le[4]-1}=6 le[2]=min{le[4]-1}=6 le[5]=min{le[7]-4}=10 le[3]=min{le[5]-2}=8 le[0]=min{le[1]-6, le[2]-4, le[3]-5}=0 AOE 네트워크에 대한 le의 계산

AOE 네트워크(7/8) 작업 e 1 1 – e 1 – e = 0 a Yes a 2 2 No a 3 3 No a 6 6 Yes 이른 시작 시간 가장 높은 시간 임계도 임계성 작업 e 1 1 – e 1 – e = 0 a Yes 1 a 2 2 No 2 a 3 3 No 3 a 6 6 Yes 4 a 4 6 2 No 5 a 5 8 3 No 6 a 7 7 Yes 7 a 7 7 Yes 8 a 7 10 3 No 9 a 16 16 Yes 10 a 14 14 Yes 11 이른, 늦은 임계도 값

AOE 네트워크(8/8) a1 a4 a10 a7 a8 a11 a5 a1 a7 a3 a6 a2 a4 start 4 8 finish a8 a11 7 모든 비임계 작업을 삭제한 후의 그래프 a5 1 4 5 a1 a7 a3 a6 3 a2 a4 2 도달 불가능한 작업을 가진 AOE 네트워크