그래프알고리즘 14 장. 그래프알고리즘 위상정렬, 최소신장트리, 최단경로, 이행폐쇄, 이중연결, 유니언파인드, 네트워크플로우 학습목표 그래프관련용어를이해한다. 그래프를표현하기위한두가지자료구조를이해한다. 신장트리, 최소신장트리알고리즘들을이해한다. 이행폐쇄, 최단경로알고리즘들을이해한다. 이중연결, 유니언파인드, 네트워크플로우알고리즘들을이해한다. 1
Section 01 그래프 - 그래프 유관한사물 (Object) 또는개념 (Concepts) 을연결. 연결망 (Connection Network 또는 Network). 프로젝트단위작업 (Task) 사이의순서, 분자연결구조, 전자부품연결구조. 전산학, 이산수학의연구주제 Graph Vertices Edges 통신전화, 컴퓨터광섬유케이블 전기전자회로칩, 콘덴서, 저항선 기계이음새스프링, 빔, 막대 급수시스템저수지, 정화시설배관 교통교차로, 공항고속도로, 항로 일정표단위작업선결조건 소프트웨어시스템함수함수호출 인터넷웹페이지하이퍼링크 게임말의위치허용된움직임 분자구조분자화학적연결 사회적관계사람친구관계 경제주식, 현금거래 [ 표 14-1] 정점과간선 2
그래프용어 G = 정점 (Vertex, Node) 의집합 V + 간선 (Edge) 의집합 E 서브그래프 G (Subgraph) 인접 (Adjacency) [ 그림 14-1] 그래프예시 (1) 3
그래프용어가중치그래프 (Weighted Graph) 무방향그래프, 방향그래프 (Directed Graph, Undirected Graph) 경로 (Path) 단순경로 (Simple Path) 사이클 (Cycle) 단순사이클 (Simple Cycle) [ 그림 14-1] 그래프예시 (1) 4
그래프용어 연결그래프 (Connected Graph), 절단그래프 (Disconnected Graph) 완전그래프 (Complete Graph) 트리 (Tree) : 연결된, 사이클없는 (Directed Acyclic) 그래프 V 개의정점, 항상 (V-1) 개의간선그보다많으면사이클, 그보다적으면절단그래프포리스트 (Forest): 트리의집합 [ 그림 14-2] 그래프예시 (2) 5
Section 02 추상자료형그래프 - 추상자료형그래프 Create: Destroy: InsertVertex: InsertEdge: DeleteVertex: DeleteEdge: RetrieveVertex: IsAdjacent: IsEmpty: 새로운그래프를만들기사용되던그래프를파기하기새로운정점을삽입하기새로운간선을삽입하기기존정점을삭제하기기존간선을삭제하기키에의해정점레코드를검색하기인접해있는지확인하기비어있는그래프인지확인하기 6
Section 03 그래프표현방법 - 그래프표현인접행렬 (Adjacency Matrix) 2차원행렬 : 2차원배열직접연결된간선이있으면해당값을 1(True) 대각선요소는무의미. 0 또는 1. [ 그림 14-3] 인접행렬 7
그래프표현인접행렬 (Adjacency Matrix) 가중치그래프 : 간선의가중치가중치 : 정점사이를이동하는데필요한비용이나거리인접하지않은정점 : 비용무한대 [ 그림 14-4] 가중치그래프의인접행렬 8
그래프표현인접행렬 무방향그래프의인접행렬은대각선을중심으로대칭메모리절약을위해배열의반쪽만을사용할수있음. 방향성그래프의인접행렬은일반적으로대칭이아님. 배열의인덱스는정점을의미정점 ID를배열인덱스로매핑시키는테이블이필요 Vertex 배열인덱스 a 0 b 1 c 2 d 3 e 4 [ 표 14-2] 심볼테이블 9
그래프표현정적배열에의한인접행렬 필요한정점의수를예측. int AdjacencyMatrix[Max][Max]; 라고선언스택메모리 동적배열에의한인접행렬 힙메모리 미리배열크기를결정할필요가없음 10
동적배열에의한인접행렬정수공간 typedef int * ptrtype; ptrtype p = malloc(sizeof(int)); *p = 20; [ 그림 14-5] 단일변수 연속된정수공간 ptrtype p = malloc(ncol * sizeof(int)); NCol 개의정수가들어갈수있는공간. 이변수공간을마치배열처럼사용포인터기호또는배열기호에의해접근가능 [ 그림 14-6] 연속변수 11
동적배열에의한인접행렬 행렬 : NRow * NCol 개의정수공간 [ 그림 14-7] 포인터배열을가리키는포인터 12
동적배열에의한인접행렬 코드 14-1: 동적배열에의한행렬 int ** InitMatrix(int NRow, int NCol, int Value) Value는초기값 { int **m; m = malloc(nrow * sizeof(int *)); NRow개의포인터배열을만듦 for (int i = 0; i < NRow; i++) 포인터배열의각요소가 m[i] = malloc(ncol * sizeof(int)); NCol개의정수배열을가리킴 for (int i = 0; i < NRow; i++) 모든행에대해서 for (int j = 0; j < NCol; j++) 모든열에대해서 m[i][j] = Value; Value 값으로초기화 return m; 포인터의포인터를리턴값으로 } 13
동적배열에의한인접행렬코드 14-2: 동적배열의공간반납 void FreeMatrix(**m) 동적배열 m의파기 { for (int i = 0; i < NRow; i++) 포인터배열각각에대해 free(m[i]); 가리키는전체공간을반납 free(m); 포인터배열공간을반납 } 그래프표현 정방형인접행렬 (Square Adjacency Matrix) 정점및간선개수를추적그래프자료구조는구조체와그구조체를가리키는포인터로선언 14
그래프표현 typedef struct { int V; 그래프내부정점의수 int E; 그래프내부간선의수 int **M; 인접행렬을가리키는포인터 } graphtype; typedef graphtype *graphptr; 그래프를가리키는포인터 graphptr InitGraph(int V) 함수프로토타입 void InsertEdge(graphPtr g, int V1, int V2) 함수프로토타입 [ 그림 14-8] 인접행렬에의한그래프자료구조 15
그래프함수 코드 14-4: Graph.c #include <GraphByMatrix.h> graphptr InitGraph(int V) 정점 V개가들어갈수있는그래프생성 { graphptr G = malloc(sizeof(graphtype)); 그래프구조체를동적으로생성 G->V = V; 정점의수를 V개로확정 G->E = 0; 생성시의간선수 0 G->M = InitMatrix(V, V, 0); 크기 V 제곱인동적배열만들고 0으로초기화 return G; } void InsertEdge(graphPtr g, int V1, int V2) 정점 V1, V2를연결하는간선삽입 { if (g->m[v1][v2] = = 0) 인접행렬값이 0이면 { g->e++; 간선의수를늘리고 g->m[v1][v2] = 1; V1->V2를 1로바꿈 g->m[v2][v1] = 1; 무방향그래프이면 V2->V1도 1로바꿈 } } 16
그래프표현인접리스트 (Adjacency List) 하나의정점에인접한모든노드를연결리스트형태로표시경로에관한정보가아님. 가중치정보를표시하려면노드에가중치필드를추가. 연결리스트를가리키는포인터배열 [ 그림 14-9] 인접리스트 17
인접리스트인접리스트 무방향그래프 : 하나의간선에대해두개의노드가나타남. 인접리스트의노드수는간선수 E의 2배 인접리스트와인접행렬 정점 i와정점 j가인접해있는가 : 인접행렬이유리정점 i 에인접한모든노드를찾아라 : 인접리스트가유리공간면에서인접행렬은 V 2 개의공간, 인접리스트는 2E 개의공간이필요 희소그래프, 조밀그래프 간선수가적은그래프를희소그래프 ( 稀少, Sparse Graph) 간선수가많은그래프를조밀그래프 ( 稠密, Dense Graph) 조밀그래프라면인접행렬이유리희소그래프라면인접리스트가유리 18
인접리스트 코드 14-5: GraphbyLinkedList.h typedef struct { int Data; node* Next; } node; typedef node* Nptr; 정점의 ID 번호다음노드를가리키는포인터 typedef struct { int V; 그래프내부정점의수 int E; 그래프내부간선의수 node **L; 포인터배열을가리키는포인터 } graphtype; typedef graphtype *graphptr; 그래프를가리키는포인터 graphptr InitGraph(int V) void InsertEdge(graphPtr g, int V1, int V2) 함수프로토타입함수프로토타입 19
인접리스트코드 14-6: GraphbyLinkedList.c #include <GraphbyLinkedList.h> graphptr InitGraph(int V) 정점 V개가들어갈수있는그래프생성 { graphptr G = malloc(sizeof(graphtype)); 구조체공간을동적으로생성 G->V = V; 정점의수를 V개로확정 G->E = 0; 생성시에간선수 0 G->L = malloc(v * sizeof(node *)); V개정수포인터배열을동적으로생성 for (int i = 0; i < V; i++) 배열내모든포인터값을 G->L[i] = NULL; 널로초기화 return G; 포인터의포인터를리턴값으로 } void InsertEdge(graphPtr g, int V1, int V2) 정점 V1, V2를연결하는간선삽입 { Nptr temp = malloc(sizeof(node)); 새로운노드를만들고 temp->data = V2; 거기에 V2의 ID 번호를넣음 temp->next = g->l[v1]; 새노드가현재첫노드를가리키게 g->l[v1] = temp; L[V1] 이새로만든노드를가리키게 } 무방향그래프이면 V2에도 V1을삽입. 20
Section 04 그래프순회 - 그래프순회 깊이우선탐색 (DFS) 과너비우선탐색 (BFS) 깊이우선탐색은스택과, 너비우선탐색은큐와직접연관트리의전위순회를일반화한것이깊이우선탐색트리의레벨순회를일반화한것이너비우선탐색 두가지모두방문된노드로는가지않음 확인을위한자료구조가필요배열값이 TRUE 이면방문된상태미방문상태로초기화하기위해 FALSE 를쓰는작업. 방문될때마다 TRUE 를쓰는작업. 따라서 O(2V) 번의작업이필요. [ 그림 14-10] 방문상태를나타내는배열 21
인접행렬 그래프순회의효율 주어진노드에인접한모든노드를찾기위해서그노드를행번호로하는행전체를스캔 O(V). 모든행을스캔 O(V 2 ). 탐색의효율은 O(2V + V2) = O(V 2 ) 인접리스트 현재노드가 A 일때, A 를헤드로해서 B 가방문되었는지확인하기위해리스트스캔 O(E). 나중에현재노드가 B 일때, B 를헤드로해서 A 가이미방문되었는지확인하기위해서한번더읽음 O(E). 탐색의효율은 O(2V+2E) = O(V+E). 희소그래프에서는 (V+E) 가작음. 조밀그래프에서는 V 2 이작음. [ 그림 14-11] 인접리스트탐색효율 22
Section 04 위상정렬 - 위상정렬 AOV 네트워크 (Activity on Vertex Network) 정점에단위공정을표시방향성그래프의간선은일의순서를의미 A->B는 A 공정이완료되어야 B 공정을수행할수있음을의미수강신청을위한선수과목이수개념과동일함. 어떤공정이어떤공정보다앞서야하는지가문제위상정렬 : 먼저수행해야될공정부터시작해서일렬로모든공정을나열 23
위상정렬 AOV 네트워크 (Activity on Vertex Network) 정렬결과가유일하지는않음. 첫번째위상정렬결과는 A, C, D, F, B, E, G 순서로일을진행. 결과화살표는노드를건너뛸수는있으나오른쪽으로가는것만허용. A-D-E-G 로가든 A- C-D-B-E-G 로가든무방 전제조건 : 사이클이존재하면서로어떤것이먼저인지판별하기가불가능. 사이클이없는방향그래프를대그 (DAG: Directed Acyclic Graph) 라고함. [ 그림 14-12] 위상정렬 24
싱크 소스, 싱크 마지막공정은그공정다음에오는공정이없음. 싱크 (Sink, 가라앉는곳 ) 그노드로들어가는간선은있어도, 거기서나가는간선은없는노드 소스첫공정은그공정에앞서오는공정이없음. 소스 (Source, 떠오르는곳 ) 그노드로부터나가는간선은있어도, 그리고들어오는간선이없는노드 진입차수, 진출차수진입차수 ( 進入, In-Degree): 어떤노드로들어가는간선의수진출차수 ( 進出, Out-Degree): 노드에서나가는간선의수싱크는진출차수가 0 인노드, 소스는진입차수가 0 인노드. 25
싱크제거에의한위상정렬 싱크제거에의한위상정렬 싱크인 G 를제거하고 G 와연결된간선들을모두제거. 결과그래프의싱크는 E 와 F. E 와거기에연결된간선들을제거. 순차적으로제거된싱크를연결리스트의맨처음에삽입 연결리스트를처음부터끝까지따라가면그순서가위상정렬순서 ( A, C, D, F, B, E, G) [ 그림 14-13] 순차적인싱크제거 26
싱크제거에의한위상정렬코드 14-7: 싱크제거에의한위상정렬 TopologicalSort(G) { for (step =1 through N) N은전체노드의개수 { Select a Sink T; 싱크가여럿이면아무거나 L.Insert(1, T); 연결리스트의맨앞에삽입 Remove the Sink T and Edges Connected to It: 싱크및연결된간선을삭제 } } 27
깊이우선탐색에의한위상정렬 깊이우선탐색에의한위상정렬 소스에서출발하여방향성간선 (Directed Edge) 을계속따라가면그순서가바로위상정렬순서 마지막노드인싱크로부터백트랙하는작업이바로싱크를제거하는작업에해당 [ 그림 14-14] 깊이우선탐색에의한위상정렬 28
유의점 깊이우선탐색에의한위상정렬 깊이우선탐색의순서는 A-D-B-E-G-F-C 백트랙이발생한순서대로기록. 탐색순서 A-D-B-E-G-F-C 에서가장먼저백트랙이발생한곳은 G. 이후 G, E, B. 이후가정먼저백트랙이발생한곳은 F. [ 그림 14-14] 깊이우선탐색에의한위상정렬 29
깊이우선탐색에의한위상정렬 코드 14-8: 깊이우선탐색에의한위상정렬 TopologicalSort(V) { for All Nodes T Adjacent to V 안가본모든노드에대해 if (T Is Unvisited) 더이상갈곳이없을때까지 TopologicalSort(T); 재귀호출 L.ListInsert(1, V); 재귀호출끝나면리스트맨처음에삽입 } 30
트리 연결된 (Connected), 사이클없는 (Acyclic) 그래프 신장트리 Section 06 신장트리 - 트리 주어진그래프 G 의신장트리는 G 의서브그래프로서 G 의모든정점과트리를이루기에충분할만큼만의간선으로구성. 주어진연결그래프에서사이클을없앰으로써얻을수있는트리. 정점수 N 개일때, 간선수 (N-1) 이면트리 신장트리의모습은유일하지는않다 [ 그림 14-15] 그래프의신장트리 31
깊이우선탐색에의한신장트리깊이우선탐색트리 (Depth First Search Tree) A에서시작해서 A-B-C-D-G-E-F-H-I 로가는탐색순서 B에서시작해서 B-A-F-G-D-C-E-H-I로가는탐색순서 아래에서위로가는화살표 지나온노드이기때문에새로방문하지는않지만보이기는보임. 화살표에해당하는간선을제거하면신장트리 [ 그림 14-16] DFS Trees 32
Section 07 최소신장트리 - 최소신장트리전철망의설계 모든역을서로직접연결하면가장이상적장애물이있을때에는직접연결이가능한곳이제한됨 [ 그림 14-17] 수도권전철네트워크 (www.seoulsubway.co.kr) 33
최소신장트리모든역사이에서로갈수있는길이있는가. 다른역을거쳐서가도됨. 연결그래프이어야함. 선로가설비용을최소화하라. 사이클이존재한다면그것을제거함으로써가설비용을줄임 연결성은그대로유지. 따라서신장트리만들면됨. 선로마다가설비용이다른데, 어떤간선을제거해야하는것이전체가설비용을최소화하는가. 즉, 어떤신장트리가가장경제적인가의문제 34
최소신장트리 최소신장트리 (MST: Minimum Spanning Tree) 최소비용신장트리. 신장트리중전체가중치의합이최소가되는것 최소신장트리가설 그래프의정점들을두개의그룹으로나누었을때, 두그룹사이를연결하는간선들중에서가장가중치가작은간선은반드시최소신장트리에포함되어야한다. {A, B, C, D} 와 {E, F, G, H} 그룹. 사이를잇는것은 B-E, C-E, D-E, D-F, A-F, A-D 등 6 개의다리. 2 개의다리를모두트리에포함시키면사이클. 다리중하나만선택. 가중치가가장작은 D-F 를선택해야전체가중치가작아짐. 주어진그래프를어떤식으로분할하여그룹화하던간에가설이성립해야함. [ 그림 14-18] 최소신장트리가설 35
프림알고리즘 (Prim's Algorithm) 우선순위우선탐색 (PFS: Priority First Search) 가중치가작을수록우선순위가높다고정의 적용예 프림알고리즘 어떤노드에서출발해도무관. A 에서출발하는예 A 와인접한세개의노드 G, B, F 중가장가중치가작은것이 B 간선 A-B 를트리에포함. 이트리의정점 A 와 B 에인접한모든노드를대상으로가중치를비교. B-C, A-G, A-F 중가장작은것은 B-C 간선 B-C 를트리에포함현재연결된트리내부의모든정점에인접한간선중최소가중치간선을선택함. 단, 사이클을유발하는간선은피함. 우선순위큐를사용하여구현 A 를제거하는대신 A 에인접한 G, B, F 를우선순위큐에삽입. 우선순위가높은 B 를삭제하는대신, B 에인접한 C, E, D 를삽입. 36
프림알고리즘 프림알고리즘 [ 그림 14-19] 프림알고리즘 37
크루스칼알고리즘 크루스칼방법 (Kruskal's Method) 가장작은가중치 1 을지닌간선네개중임의로 A-B 를선택 나머지그래프에서가장작은가중치역시 1 이므로이번에는 G-E 를선택 분리된두개의트리 ( 포리스트 ) 가생성 매단계마다그상태에서가장작은가중치를가진간선을선택해서두개의정점또는트리사이를잇는방식. 단사이클을유발하는간선은피함. 탐욕알고리즘 (Greedy Algorithm) 일단가설비용이제일싼것부터먼저건설하고보자 당장눈앞에보이는이득을추구하는것이나중에전체적으로도크게봐도이득이된다 는접근방식 최소신장트리에는이러한접근방법이해결책이됨. 38
크루스칼알고리즘 크루스칼알고리즘 [ 그림 14-20] 크루스칼알고리즘 39
솔린알고리즘 솔린알고리즘 (Sollin's Algorithm) 트리에인접한최소가중치간선을사용 두개의서로다른트리를연결 1 단계에서그래프의모든정점이각각트리를형성 트리에인접한간선중, 가장가중치가작은것을선택하여화살표로표시 트리별로간선을따라다른트리와연결 다시각각의트리에인접한간선들중가장가중치가작은것을선택 단계별로각각의트리에서뻗어나가는최소가중치간선을선택하고, 이를선택하여서로다른트리를이어감. 단사이클을유발하는간선은피함. 트리에인접한간선중에서최소가중치를지닌간선을선택한다는점에서프림알고리즘과유사. 포리스트를놓고작업한다는점에서는크루스칼알고리즘과유사. 40
솔린알고리즘 솔린알고리즘 [ 그림 14-21] 솔린알고리즘 41
Section 08 최단경로 - 최단경로 주어진도시에서다른도시로가기위해서어떤경로로가는것이가장적은비용이되는가 [ 그림 14-22] 노스웨스턴의항공망 (www.nwa.com) 42
최단경로 최단경로 [ 그림 14-23] 비행기예약 43
다이익스트라알고리즘최단경로의문제 (Shortest Path Problem) 여러곳을거쳐서간다면전체비용은구간별요금을합산최소비용다이익스트라알고리즘 (Dijkstra Algorithm) 출발노드가주어졌을때나머지모든노드로가는최소비용및경로 i j A B C D E F A 0 1 5 2 B 0 2 C 0 1 D 1 0 E 1 0 F 0 [ 그림 14-24] 입력그래프 [ 표 14-3] 인접행렬표현 44
다이익스트라알고리즘 다이익스트라알고리즘수행하기 도표의 1 단계행 (Row) 을채우기위해서는인접행렬정보를사용 정점중하나를선택하여선택정점칼럼에추가 선택정점은현재의비용중가장작은것, 즉비용 1 을지닌 B. 정점이선택된다는것은해당정점으로가는최소비용이확정된다는것을말함 만약 A 에서다른곳을거쳐서 B 로간다면 C, D, E, F 중하나를거침. 그런데그곳까지가는비용이이미 1 보다크기때문에그곳을거쳐온들이비용보다작을수없음 단계수 선택정점 비용 [B] 비용 [C] 비용 [D] 비용 [E] 비용 [F] 1 B 1 5 2 2 F 3 B 2 3 C 3 B 4 E 4 C 5 D 5 E [ 표 14-4] 다이익스트라알고리즘 45
다이익스트라알고리즘 다이익스트라알고리즘수행하기 2 단계에서는나머지 C, D, E, F 를처리 B 로가는최소비용이확정되었으니, B 를거쳐서해당정점으로가는비용이현재비용보다더작지않은가를확인비용 [C]: 1 단계에서 5 원에갈수있음. 그런데 A-B 1 원에간다고확정되었고, 인접행렬을참조하면 B-C 는 2 원에갈수있으니 3 원이면 A-B-C 로갈수있음. 이값은현재 5 원보다작으니 3 으로바꿈. 인접행렬을참조하면나머지 D, E, F 는 B 에서가는길이없으니 1 단계값들이그대로내려옴. 최소값인정점 F 를선택 3 단계에서는 F 를거쳐서 C, D, E 가는비용을확인. 인접행렬을보면 F 에서 C, D, E 로가는것은없으므로 2 단계값들이그대로내려오고, 그들중최소값 3 을지닌정점 C 를선택 단계수선택정점비용 [B] 비용 [C] 비용 [D] 비용 [E] 비용 [F] 1 B 1 5 2 2 F 3 B 2 3 C 3 B 4 E 4 C 5 D 5 E [ 표 14-4] 다이익스트라알고리즘 46
다이익스트라알고리즘 다이익스트라알고리즘수행하기 4 단계에서는방금선택된 C 를거쳐서가는길을확인. 3 단계에서 A-C 를최소비용 3 원에가고, 다시 C-E 를 1 원에가면 4 원. 이값은현재 A 에서 C 가는데드는최소비용인무한대보다작음. 따라서해당값을 4 원으로변경. 정점 E 를선택. 5 단계에서는정점 D 로가는최소비용이확정됨 경로를찾아내기위해서비용이갱신될때마다거쳐온직전노드를표시. 5 단계에서비용 [D] 가 5 원으로갱신된이유는 A-E + E-D = 4 + 1 = 5 이었기때문. D 직전에 E 를거쳐온것이므로도표의해당엔트리에 E 를표시하여역추적 단계수 선택정점 비용 [B] 비용 [C] 비용 [D] 비용 [E] 비용 [F] 1 B 1 5 2 2 F 3 B 2 3 C 3 B 4 E 4 C 5 D 5 E [ 표 14-4] 다이익스트라알고리즘 47
다이익스트라알고리즘 도표의행은해당단계에서최소비용 3 단계에서는 D 까지가는비용은현재까지계산된바로는무한대가장작은비용 단계가거듭될수록점차최적화 동적프로그램기법 (Dynamic Programming) 문제가너무커서해결할수없을때 간단한사실하나를알아내는데주력 알려진사실을바탕으로해서하나씩새로운사실을추가하여알려진사실의범위를점차로확대 48
방향그래프의정점 X 에서정점 Y 로가는길이있는가 Y 가 X 에연결되어있는가하는연결성의문제 가는길이있다면정점 X 에서정점 Y 로직접가는간선을추가 이후질문에즉답이가능 이행폐쇄 (Transitive Closure) Section 09 이행폐쇄 - 이행폐쇄 거쳐서갈수있는모든곳을직접가는간선으로연결한그래프 간선의추가에의해서, 대부분의노드들이인접노드로바뀜. 인접행렬로표현하는것이유리 [ 그림 14-25] 이행폐쇄 49
깊이우선탐색 이행폐쇄 A 로부터시작하는 ACBDGF 라는경로 A 와 CBDGF 가연결되어있음을의미 H 에서출발하면 A 로갈수있으나이연결정보는위경로에포함안됨. 모든노드에서출발하는깊이우선탐색을별도로실행모든정점에서출발하는깊이우선탐색 인접리스트로구현하면 O(V*(V+E)), 인접행렬로구현하면 O(V*V 2 ) [ 그림 14-26] DFS 입력 50
와샬알고리즘 와샬알고리즘 [ 그림 14-26] DFS 입력 A B C D E F G H A 0 0 1 0 0 1 0 0 B 1 0 0 1 0 0 C 0 1 0 0 0 [ 표 14-5] 인접행렬표현 0 1 0 1 0 0 0 0 D 0 0 0 0 0 0 1 0 E 0 0 1 0 0 0 0 1 F 0 0 0 1 0 0 0 0 G 0 0 0 0 0 1 0 0 H 0 0 0 0 1 0 0 0 51
와샬알고리즘 왼쪽에서오른쪽, 그리고위에서아래순서로 A[B][A] = 1 은 B 에서 A 가는길이있다는의미 이는 A 에서갈수있는모든곳을 B 에서갈수있다는의미. 왜냐하면 B 에서 A 를거쳐가면되기때문. A 행을보면현재 C, F 가 A 에서갈수있는곳. 따라서표의 A[B][C], A[B][F] 값을 1 로바꿈. 스캔할때마다 0 이아닌엔트리에주목하되, 이는이전에 0 이었다가 1 로변한것도포함. 다시말해알고리즘실행결과는누적됨. 효율면에서와샬알고리즘은 O(V 3 ). 인접행렬의모든엔트리에대해서스캔을가하여야하므로 V 2. 각각의엔트리에대해서하나의행을탐색하기위해 V 시간이소요. B 에서 C 로갈수있으면 C 에서갈수있는모든곳을찾기위해 C 행을모두탐색 52
Section 10 모든쌍의최단경로 - 플로이드알고리즘플로이드알고리즘 (Floyd's Algorithm) 모든정점으로부터다른모든곳으로가는최단경로. 모든쌍의최단경로다이익스트라 : 주어진정점으로부터다른모든곳으로가는최단경로와샬알고리즘의변형 53
A[A][B] = 1 플로이드알고리즘 A 에서 B 로갈수있으므로 B 에서갈수있는모든곳을 A 에서갈수있음 B 에서갈수있는모든곳은도표의 B 행에표시 비용 2 에 C 로갈수있음. 따라서 A-B + B-C = 1 + 2 = 3. 이비용은현재 A 에서 C 로가는값 A[A][C] 인 5 보다작으므로변경 A[D][B] = 1 D 에서 B 를거쳐 C 로가는 D-B-C 의비용은 D-B + B-C = 1 + 2 = 3 이값은현재도표의 A[D][C] 인무한대보다작으므로값을 3 으로변경 도표에는항상지금까지알아낸최소값이기록됨 A B C D E F A 0 1 5 3 4 2 B 0 2 3 C 0 1 D 1 3 0 E 1 0 F 0 [ 표 14-7] 플로이드초반 54
Section 11 이중연결그래프 - 이중연결그래프 이중연결그래프 (Biconnected Graph) 서울 - 경주 - 포항이라는철로. 경주역에장애가발생. 서울에서다른곳을거쳐서포항을갈수있도록설계해야함. 모든정점쌍을연결하는경로가두개이상인그래프. 관절점 (AP: Articulation Point) 만약그것이사라지면그래프가두개이상의그룹으로분리되는그러한정점. 만약이런정점이존재한다면한그룹에서다른그룹으로건너가려면반드시그정점을통과해야함. 관절점이없어야이중연결그래프 [ 그림 14-27] 관절점 55
이중연결그래프 깊이우선탐색트리에의한관절점판단 B 가지워지면두개의서브트리로분리. 오른쪽서브트리의자식노드중 G 가 B 의상위노드를가리킴. 왼쪽서브트리는어떤자식노드도 B 의상위노드를가리키는것이없음. B 의삭제는왼쪽서브트리그룹의분리로이어지고, 결과적으로 B 는관절점 C 가없어져도자식인 D 가 C 의상위노드를가리키므로 C 는관절점이아님. 서브트리가하나일경우에는그서브트리에단하나라도삭제된노드의상위노드를향하는연결이있으면그정점은관절점이아님. 루트가 2 개이상의서브트리로나뉜다면루트를삭제했을때서브트리가분리되므로루트가관절점. 루트에하나의서브트리만있다면그루트는관절점이아님. [ 그림 14-28] 깊이우선탐색트리와관절점 56
유니언파인드 Section 12 유니언파인드 - 유니언파인드 주어진원소들이서로같은집합에속하는가를알아내고 (Find) 만약에그렇지않으면같은집합에속하도록추가하라 (Union) 깊이우선탐색 배열첫요소는노드 A 에서출발한것으로서 BFDE 가탐색결과 D 가 A 와같은집합에속하는가라고질문하면이요소를검색하여답함. 이방법은집합의원소가고정된 ( 정적상황에알맞은 ) 방법 수시로새로운원소가그래프에추가되는동적상황에서는매번깊이우선탐색을가하는데따른시간적비효율이발생 [ 그림 14-29] 깊이우선탐색 57
유니언파인드알고리즘 동적상황에유리 유니언파인드 집합 A 에 E 를추가하는것은간선 A-E 를연결함을의미 A-E 삽입명령이들어오면 A 를루트로그아래 E 를연결 A-B 삽입명령의결과 A 는두개의자식노드를거느림 B-D 삽입은직접 B 에다 D 를연결하지않고 B 의루트아래에 D 의루트를연결 [ 그림 14-30] 유니언파인드 58
자료구조로배열을사용 유니언파인드 A-E 가삽입되면표의 * 표시한곳에기록. E 의루트가 A 라는의미 B-D 의삽입은 D 의루트를 B 의루트에삽입. D 의루트는 C 이고, B 의루트는 A 이므로 C 를 A 에삽입. C 의루트가 A 가되어야하므로 C 칼럼에 A 가기록. 노드의루트를발견하기위해서는 while (A[i] Empty) i = A[i]; M 과 N 이같은집합인가 M 의루트와 N 의루트가일치하는가의문제. 불일치시에는 M-N 삽입 1 A B C D E A-E 삽입 *A A-B 삽입 A C-D 삽입 C B-D 삽입 **A [ 그림 14-30] 유니언파인드 [ 표 14-9] 루트찾기배열 59
효율 D-E 삽입, C-E 삽입, B-E 삽입 유니언파인드 E 의루트를찾기위한반복문실행에많은시간. 최악의경우표의모든엔트리를참조. 효율은 O(V). 가중치유니언 (Union by Weighting) 자식노드가더많은루트를최종루트로하는방법 (a) 의 J-D 를추가하는작업에서 J 의루트인 J 가 D 의루트인 C 에붙는다. [ 그림 14-31] 유니언파인드알고리즘의개선 60
경로압축 (Path Compression) 유니언파인드 루트를찾는과정에서나타나는모든노드를직접최종루트아래로. K 의루트인 L 을찾는과정에서만나는것은 K, A, M 2 단계의작업 : 루트를찾으면서나타나는모든노드에표시. 나중에루트를찾으면그노드를모두찾아가서부모노드를변경 분할 (Halving) 단일패스에경로를단축 : 루트노드를찾아가면서단축작업 방문된노드의자식노드를방문된노드의부모노드에붙이는방법 61
Section 12 네트워크플로우 - 네트워크플로우방향성그래프 G의가중치에유량 ( 流量, Flow) 을할당 유량을최대화하는문제상하수도배관이수용하는범위내에서가능한많은유량통신선로대역폭이수용할수있는범위내에서가능한많은정보도로가수용할수있는범위내에서가능한많은교통량 네트워크플로우 (Network Flow) 어떤정점에서다른정점으로갈수있는흐름을최대화어떤간선이수용할수있는용량이초과되면역류가발생역류를일으키지않으면서유량을최대화하라는문제 62
네트워크플로우 네트워크플로우 [ 그림 14-32] 배관네트워크플로우 63
네트워크플로우 네트워크플로우 노드 S 는소스, 노드 T 는싱크를나타냄. 가중치 5/3 은최대용량 (Capacity) 5 에현재유량 (Flow) 3 을흘림을의미 개념적간선 S->M->N->T 를잡으면이방향은실제간선의방향과일치. 이를순방향간선 (Forward Edge) 이라부름. 최대용량에서현재유량을뺀차이를슬랙 (Slack, 느슨한정도 ) 이라함. S-M 사이의슬랙은 5-3 = 2 보강경로 (Augmenting Path, Alternating Path) 각노드사이의슬랙은 2, 4, 1 최소슬랙 1만큼을더흘릴수있음. 개선의여지가있는경로를보강경로라함. 64
순방향흐름분석 네트워크플로우 S-M-N-T 의순방향흐름은모두최대 N-T 사이가최대용량으로서슬랙이 0 S-Q-P-T 역시최소슬랙 0 소스에서나가는양은 5 + 3 + 5 = 13, 싱크로들어오는양은 3 + 7 + 3 = 13 어떤노드로들어오는유량과나가는유량의합은같아야한다. 들어오는양이상으로나갈수없고, 나가는양이상으로들어오면역류가발생. [ 그림 14-33] 순방향간선 65
역방향간선 (Backward Edge) 네트워크플로우 개념적인간선의방향을 S-M-N-P-T 로. N-P 사이의개념적흐름은실제흐름과반대. S-M-N 사이의최소슬랙은 2. 소스에 2 를더부르면 S-M 이 7/5 로, M-N 이 4/4 로증가. 그런데이렇게되면노드 N 이문제. 2 만큼더들어오니그만큼더나가거나, 아니면다른곳에서 2 만큼덜들어오면됨. P-N 사이를보자. N 으로들어오는양을 4/1 로줄이면 2 만큼덜들어오니 N 으로서는무리가없음. 이제 N 의제약이 P 의제약으로바뀜. P 로서는 2 만큼덜내보내야하니그만큼덜들어오든가아니면다른곳으로 2 만큼더내보내면됨. P-T 사이에 6/3 을 2 만큼올려서 6/5 로늘리면이문제는해결됨. 소스에 2 만큼더부어도됨. [ 그림 14-34] 역방향간선 66
보강경로이론 만약에그래프내에어떠한보강경로도없다면그흐름은최대이다. 어떤그래프에서더이상의보강경로가없는지를어떻게증명하는가? 67
커트 커트 (Cut) 는소스와싱크를분리하는간선의집합 첫째그림은 S, A, M 을소스그룹으로, 나머지정점을싱크그룹으로분리. 소스와싱크를분리하는간선은 A-B, A-N, M-N, M-P, S-Q 등다섯개가존재 둘째그림은 S, M, Q 를소스그룹으로, 나머지를싱크그룹으로분리. 그룹을분리하는간선은 S-A, M-N, M-P, Q-P 등세개가존재한다. 자르는방법에따라서그래프내에는수많은커트가존재한다 [ 그림 14-35] 커트 68
맥스플로우민커트이론 최대유량은최소커트와같다 각그룹을하나의노드로바라보면그래프는두개의노드와그노드를잇는커다란배관. 두노드를잇는배관의크기는각커트의최대용량 (Capacity) 의합과같음. 여러가지방법으로커트를만들수있으나어떻게자르던최대용량은커트를초과할수없음. 커트용량 첫째커트의최대용량의합은 (4 + 3 + 4 + 1 + 6) = 18. 둘째커트는 (5 + 4 + 1 + 5) = 15. 이두가지를종합하면최대유량은일단 15 를초과할수없음. 다른커트방법을감안해야함. 최소커트는병목현상에있어서병목에해당 69
Thank you 70