7. 그래프 그래프 그래프 (graph) 선형자료구조나트리자료구조로표현하기어려운多 : 多의관계를가지는원소들을표현하기위한자료구조 그래프 G 객체를나타내는정점 (vertex) 과객체를연결하는간선 (edge) 의집합 G = (V, E) 그래프의예 V는그래프에있는정점들의집합 E는정점을연결하는간선들의집합 -2-
그래프 그래프의종류 무방향그래프 (undirected graph) 두정점을연결하는간선의방향이없는그래프 정점 Vi와정점 Vj을연결하는간선을 (Vi, Vj) 로표현 (Vi, Vj) 와 (Vj, Vi) 는같은간선을나타낸다. V(G1)={A, B, C, D V(G2)={A, B, C E(G1)={(A,B), (A,D), (B,C), (B,D), (C,D) E(G2)={(A,B), (A,C), (B,C) 그래프 방향그래프 (directed graph), 다이그래프 (digraph) 간선이방향을가지고있는그래프 정점 Vi에서정점 Vj를연결하는간선즉, Vi Vj를 <Vi, Vj> 로표현 Vi를꼬리 (tail), Vj를머리 (head) 라고한다. <Vi, Vj> 와 <Vj, Vi> 는서로다른간선 V(G3)={A, B, C, D V(G4)={A, B, C E(G3)={<A,B>, <A,D>, <B,C>, <B,D>, <C,D> E(G4)={<A,B>, <A,C>, <B,A>, <B,C> -3- -4-
그래프 완전그래프 (complete graph) 각정점에서다른모든정점을연결하여가능한최대의간선수를가진그래프정점이 n개인무방향그래프에서최대의간선수 : n(n-1)/2 개정점이 n개인방향그래프의최대간선수 : n(n-1) 개 완전그래프의예 G5 는정점의개수가 4 개인무방향그래프이므로완전그래프가되려면 4(4-1)/2=6 개의간선연결 G6 은정점의개수가 4 개인방향그래프이므로완전그래프가되려면 4(4-1)=12 개의간선연결 그래프 부분그래프 (subgraph) 원래의그래프에서일부의정점이나간선을제외하여만든그래프그래프 G와부분그래프 G' 의관계 V(G') V(G), E(G') E(G) 그래프 G1에대한부분그래프의예 -5- -6-
그래프 가중그래프 (weight graph), 네트워크 (network) 정점을연결하는간선에가중치 (weight) 를할당한그래프 그래프 그래프관련용어 그래프에서두정점 Vi과 Vj를연결하는간선 (Vi, Vj) 가있을때, 두정 점Vi와Vj를인접 (adjacent) 되어있다고하고, 간선 (Vi, Vj) 는정점Vi와Vj에부속 (incident) 되어있다고한다. 그래프 G1 에서정점 A 와인접한정점은 B 와 D 이고, 정점 A 에부속되어 있는간선은 (A,B) 와 (A,D) 이다. 차수 (degree) 정점에부속되어있는간선의수 그래프 G1 에서정점 A 의차수는 2, 정점 B 의차수는 3 방향그래프의정점의차수 = 진입차수 + 진출차수 방향그래프의진입차수 (in-degree) : 정점을머리로하는간선의수 방향그래프의진출차수 (out-degree) : 정점을꼬리로하는간선의수 방향그래프 G3에서정점 B의진입차수는 1, 진출차수는 2 정점 B의전체차수는 ( 진입차수 + 진출차수 ) 이므로 3이된다. -7- -8-
그래프 경로 (path) 그래프에서간선을따라갈수있는길을순서대로나열한것즉, 정점 Vi에서 Vj까지간선으로연결된정점을순서대로나열한리스트 그래프 G1 에서정점 A 에서정점 C 까지는 A-B-C 경로와 A-B-D-C 경로, A-D-C 경로, 그리고 A-D-B-C 경로가있다. 경로길이 (path length) 경로를구성하는간선의수 단순경로 (simple path) 모두다른정점으로구성된경로 그래프 G1 에서정점 A 에서정점 C 까지의경로 A-B-C 는단순경로이고, 경로 A-B-D-A-B-C 는단순경로가아니다. 사이클 (cycle) 단순경로중에서경로의시작정점과마지막정점이같은경로 그래프 G1 에서단순경로 A-B-C-D-A 와그래프 G4 에서단순경로 A-B-A 는사이클이된다. 그래프 DAG(directed acyclic graph) 방향그래프이면서사이클이없는그래프 연결그래프 (connected graph) 서로다른모든쌍의정점들사이에경로가있는그래프즉, 떨어져있는정점이없는그래프 그래프에서두정점 Vi 에서 Vj 까지의경로가있으면정점 Vi 와 Vj 가연결 (connected) 되었다고한다. 트리는사이클이없는연결그래프이다. -9- -10-
그래프의구현 인접행렬 인접행렬 (adjacent matrix) 행렬에대한 2차원배열을사용하는순차자료구조방법 그래프의두정점을연결한간선의유무를행렬로저장 n 개의정점을가진그래프 : n x n 정방행렬 행렬의행번호와열번호 : 그래프의정점 행렬값 : 두정점이인접되어있으면 1, 인접되어있지않으면 0 무방향그래프의인접행렬 행 i 의합 = 열 i 의합 = 정점 i 의차수 방향그래프의인접행렬 행 i 의합 = 정점 i 의진출차수 열 i 의합 = 정점 i 의진입차수 그래프의구현 인접행렬 -11- -12-
그래프의구현 인접행렬 인접행렬표현의단점 n개의정점을가지는그래프를항상 n x n개의메모리사용정점의개수에비해서간선의개수가적은희소그래프에대한인접행렬은희소행렬이되므로메모리의낭비발생 그래프의구현 인접행렬프로그램 인접행렬 C 프로그램 그래프 G1, G2, G3, G4를인접행렬로구현한프로그램 실행결과 > -13- -14-
#include <stdio.h< stdio.h> #define MAX_VERTEX 30 typedef struct graphtype{ int n; int adjmatrix[max_vertex][max_vertex]; ]; graphtype; void creategraph(graphtype* * g) { int i, j; g->n = 0; for(i=0; i<max_vertex; i++) { for(j=0; j<max_vertex; j++) g->adjmatrix[i][j]=0; ]=0; void insertvertex(graphtype* * g, int v) { if(((g->n)+1)>max_vertex){ printf(" n 그래프정점의개수를초과하였습니다!"); return; g->n++; void insertedge(graphtype* * g, int u, int v) { if(u>=g >=g->n >n v>=g->n) >n) { printf(" n 그래프에없는정점입니다!"); return; g->adjmatrix[u][v] ] = 1; void print_adjmatrix(graphtype* * g) { int i, j; for(i=0; i<(g->n);i n);i++){ printf(" n t t"); "); for(j=0; j<(g->n);j n);j++) printf("%2d", g->adjmatrix[i][jg adjmatrix[i][j]); ]); void main() { int i; graphtype *G1, *G2, *G3, *G4; G1 = (graphtype( *)malloc(sizeof(graphtype malloc(sizeof(graphtype)); G2 = (graphtype( *)malloc(sizeof(graphtype malloc(sizeof(graphtype)); G3 = (graphtype( *)malloc(sizeof(graphtype malloc(sizeof(graphtype)); G4 = (graphtype( *)malloc(sizeof(graphtype malloc(sizeof(graphtype)); creategraph(g1); creategraph(g2); creategraph(g3); creategraph(g4); for(i=0; i<4; i++) insertvertex(g1, i); insertedge(g1, 0, 3); insertedge(g1, 0, 1); insertedge(g1, 1, 3); insertedge(g1, 1, 2); insertedge(g1, 1, 0); insertedge(g1, 2, 3); insertedge(g1, 2, 1); insertedge(g1, 3, 2); insertedge(g1, 3, 1); insertedge(g1, 3, 0); printf(" n G1 의인접행렬 "); print_adjmatrix(g1); for(i=0; i<3; i++) insertvertex(g2, i); insertedge(g2, 0, 2); insertedge(g2, 0, 1); insertedge(g2, 1, 2); insertedge(g2, 1, 0); insertedge(g2, 2, 1); insertedge(g2, 2, 0); printf(" n n G2 의인접행렬 "); print_adjmatrix(g2); for(i=0; i<4; i++) insertvertex(g3, i); insertedge(g3, 0, 3); insertedge(g3, 0, 1); insertedge(g3, 1, 3); insertedge(g3, 1, 2); insertedge(g3, 2, 3); printf(" n n G3 의인접리스트 "); print_adjmatrix(g3); for(i=0; i<3; i++) insertvertex(g4, i); insertedge(g4, 0, 2); insertedge(g4, 0, 1); insertedge(g4, 1, 2); insertedge(g4, 1, 0); printf(" n n G4 의인접행렬 "); print_adjmatrix(g4); -15- -16-
그래프의구현 인접리스트 인접리스트 (adjacent matrix) 각정점에대한인접정점들을연결하여만든단순연결리스트 각정점의차수만큼노드를연결 리스트내의노드들은인접정점에대해서오름차순으로연결 인접리스트의각노드정점을저장하는필드와다음인접정점을연결하는링크필드로구성 정점의헤드노드 정점에대한리스트의시작을표현 그래프의구현 인접리스트 n개의정점과 e개의간선을가진무방향그래프의인접리스트헤드노드배열의크기 : n 연결하는노드의수 : 2e 각정점의헤드에연결된노드의수 : 정점의차수 n개의정점과 e개의간선을가진방향그래프의인접리스트헤드노드배열의크기 : n 연결하는노드의수 : e 각정점의헤드에연결된노드의수 : 정점의진출차수 -17- -18-
그래프의구현 인접리스트 그래프 G1, G2, G3, G4 에대한인접리스트 그래프의구현 인접리스트프로그램 인접리스트 C 프로그램 그래프 G1, G2, G3, G4를인접리스트로구현한프로그램 그래프의정점 A, B, C, D 대신에 0, 1, 2, 3의번호를사용하여연산하고, 출력할때 A, B, C, D 문자로표시 간선의삽입은항상인접리스트의첫번째노드로삽입하기 -19- -20-
그래프의구현 인접리스트프로그램 실행결과 > #include <stdio.h< stdio.h> #define MAX_VERTEX 30 typedef struct graphnode{ int vertex; struct graphnode* * link; graphnode; typedef struct graphtype{ int n; graphnode* adjlist_h[max_vertex]; graphtype; void creategraph(graphtype* * g) { int v; g->n = 0; for(v=0; v<max_vertex; v++) g->adjlist_h[v]=null; void insertvertex(graphtype* * g, int v) { if(((g->n)+1)>max_vertex){ printf(" n 그래프정점의개수를초과하였습니다!"); return; g->n++; void insertedge(graphtype* * g, int u, int v) { graphnode* * node; if(u>=g >=g->n >n v>=g->n) >n) { printf(" n 그래프에없는정점입니다!"); return; node = (graphnode( *)malloc(sizeof(graphnode malloc(sizeof(graphnode)); node->vertex = v; node->link = g->adjlist_h[ug adjlist_h[u]; g->adjlist_h[u] ] = node; void print_adjlist(graphtype* * g) { int i; graphnode* * p; for(i=0; i<g->n; i++){ printf(" n t t 정점 %C 의인접리스트 ", i+65); p= g->adjlist_h[ig adjlist_h[i]; while(p){ printf(" -> > %c", p->vertex p +65); // 정점 0~4 를 A~D 로출력 p = p->link; p -21- -22-
void main() { int i; graphtype *G1, *G2, *G3, *G4; G1 = (graphtype( *)malloc(sizeof(graphtype malloc(sizeof(graphtype)); G2 = (graphtype( *)malloc(sizeof(graphtype malloc(sizeof(graphtype)); G3 = (graphtype( *)malloc(sizeof(graphtype malloc(sizeof(graphtype)); G4 = (graphtype( *)malloc(sizeof(graphtype malloc(sizeof(graphtype)); creategraph(g1); creategraph(g2); creategraph(g3); creategraph(g4); for(i=0; i<4; i++) insertvertex(g1, i); insertedge(g1, 0, 3); insertedge(g1, 0, 1); insertedge(g1, 1, 3); insertedge(g1, 1, 2); insertedge(g1, 1, 0); insertedge(g1, 2, 3); insertedge(g1, 2, 1); insertedge(g1, 3, 2); insertedge(g1, 3, 1); insertedge(g1, 3, 0); printf(" n G1 의인접리스트 "); print_adjlist(g1); for(i=0; i<3; i++) insertvertex(g2, i); insertedge(g2, 0, 2); insertedge(g2, 0, 1); insertedge(g2, 1, 2); insertedge(g2, 1, 0); insertedge(g2, 2, 1); insertedge(g2, 2, 0); printf(" n n G2 의인접리스트 "); print_adjlist(g2); for(i=0; i<4; i++) insertvertex(g3, i); insertedge(g3, 0, 3); insertedge(g3, 0, 1); insertedge(g3, 1, 3); insertedge(g3, 1, 2); insertedge(g3, 2, 3); printf(" n n G3 의인접리스트 "); print_adjlist(g3); for(i=0; i<3; i++) insertvertex(g4, i); insertedge(g4, 0, 2); insertedge(g4, 0, 1); insertedge(g4, 1, 2); insertedge(g4, 1, 0); printf(" n n G4 의인접리스트 "); print_adjlist(g4); 그래프순회 그래프순회 (graph traversal), 그래프탐색 (graph search) 하나의정점에서시작하여그래프에있는모든정점을한번씩방문하 여처리하는연산 그래프탐색방법 깊이우선탐색 (depth first search : DFS) 너비우선탐색 (breadth first search : BFS) -23- -24-
그래프순회 그래프순회의예 ) 우물파기 한지점을골라서팔수있을때까지계속해서깊게파다가아무리땅을파도물이나오지않으면, 밖으로나와다른지점을골라서다시깊게땅을파는방법 ( 깊이우선탐색 ) 여러지점을고르게파보고물이나오지않으면, 파놓은구덩이들을다시좀더깊게파는방법 ( 너비우선탐색 ) 그래프순회 깊이우선탐색 깊이우선탐색 (depth first search : DFS) 순회방법 시작정점의한방향으로갈수있는경로가있는곳까지깊이탐색해가다가더이상갈곳이없게되면, 가장마지막에만났던갈림길간선이있는정점으로되돌아와서다른방향의간선으로탐색을계속반복하여결국모든정점을방문하는순회방법 가장마지막에만났던갈림길간선의정점으로가장먼저되돌아가서다시깊이우선탐색을반복해야하므로후입선출구조의스택사용 -25- -26-
그래프순회 깊이우선탐색 깊이우선탐색의수행순서 ⑴ 시작정점 v를결정하여방문한다. ⑵ 정점 v에인접한정점중에서 1 방문하지않은정점 w가있으면, 정점 v를스택에 push하고 w를방문한다. 그리고 w를 v로하여다시 ⑵를반복한다. 2 방문하지않은정점이없으면, 탐색의방향을바꾸기위해서스택을 pop하여받은가장마지막방문정점을 v로하여다시 ⑵를수행한다. ⑶ 스택이공백이될때까지 ⑵를반복한다. 그래프순회 깊이우선탐색 깊이우선탐색알고리즘 DFS(v) for (i 0; i<n; i i+1) do { visited[i] false; stack createstack(); visited[v] true; v 방문 ; while (not isempty(stack)) do { if (visited[v 의인접정점 w]=false) then { push(stack, v); visited[w] true; w 방문 ; v w; end DFS() else v pop(stack); -27- -28-
그래프순회 깊이우선탐색 깊이우선탐색예 ) 그래프G9에대한깊이우선탐색 초기상태 : 배열 visited를 False로초기화하고, 공백스택을생성 그래프순회 깊이우선탐색 1 정점 A를시작으로깊이우선탐색을시작 visited[a] true; A 방문 ; -29- -30-
그래프순회 깊이우선탐색 2 정점 A에방문하지않은정점 B, C가있으므로 A를스택에 push 하고, 인접정점 B와 C 중에서오름차순에따라 B를선택하여탐색을계속한다. push(stack, A); visited[b] true; B 방문 ; 그래프순회 깊이우선탐색 3 정점 B에방문하지않은정점 D, E가있으므로 B를스택에 push 하고, 인접정점 D와 E 중에서오름차순에따라 D를선택하여탐색을계속한다. push(stack, B); visited[d] true; D 방문 ; -31- -32-
그래프순회 깊이우선탐색 4 정점 D에방문하지않은정점 G가있으므로 D를스택에 push 하고, 인접정점 G를선택하여탐색을계속한다. push(stack, D); visited[g] true; G 방문 ; A B C D E F G D B A stack 정점 A B C D E F G [0] [1] [2] [3] [4] [5] [6] T T visited F T F F T 그래프순회 깊이우선탐색 5 정점 G에방문하지않은정점 E, F가있으므로 G를스택에 push 하고, 인접정점 E와 F 중에서오름차순에따라 E를선택하여탐색을계속한다. push(stack, G); visited[e] true; E 방문 ; -33- -34-
그래프순회 깊이우선탐색 6 정점 E에방문하지않은정점 C가있으므로 E를스택에 push 하고, 인접정점 C를선택하여탐색을계속한다. push(stack, E); visited[c] true; C 방문 ; 그래프순회 깊이우선탐색 7 정점 C에서방문하지않은인접정점이없으므로, 마지막정점으로돌아가기위해스택을 pop 하여받은정점 E에대해서방문하지않은인접정점이있는지확인한다. pop(stack); -35- -36-
그래프순회 깊이우선탐색 8 정점 E는방문하지않은인접정점이없으므로, 다시스택을 pop 하여받은정점 G에대해서방문하지않은인접정점이있는지확인한다. pop(stack); 그래프순회 깊이우선탐색 9 정점 G에방문하지않은정점 F가있으므로 G를스택에 push 하고, 인접정점 F를선택하여탐색을계속한다. push(stack, G); visited[f] true; F 방문 ; -37- -38-
그래프순회 깊이우선탐색 10 정점 F에서방문하지않은인접정점이없으므로, 마지막정점으로돌아가기위해스택을 pop 하여받은정점 G에대해서방문하지않은인접정점이있는지확인한다. pop(stack); 그래프순회 깊이우선탐색 11 정점 G에서방문하지않은인접정점이없으므로, 다시마지막정점으로돌아가기위해스택을 pop 하여받은정점 D에대해서방문하지않은인접정점이있는지확인한다. pop(stack); -39- -40-
그래프순회 깊이우선탐색 12 정점 D에서방문하지않은인접정점이없으므로, 다시마지막정점으로돌아가기위해스택을 pop 하여받은정점 B에대해서방문하지않은인접정점이있는지확인한다. pop(stack); 그래프순회 깊이우선탐색 13 정점 B에서방문하지않은인접정점이없으므로, 다시마지막정점으로돌아가기위해스택을 pop 하여받은정점 A에대해서방문하지않은인접정점이있는지확인한다. pop(stack); -41- -42-
그래프순회 깊이우선탐색 14 정점 A에서방문하지않은인접정점이없으므로, 마지막정점으로돌아가기위해스택을 pop 하는데스택이공백이므로깊이우선탐색을종료한다. 그래프 G9 의깊이우선탐색경로 : A-B-D-G-E-C-F 그래프순회 깊이우선탐색프로그램 그래프 G9를깊이우선탐색하는 C 프로그램 그래프 G9를인접리스트로표현한다. 정점 A~G 대신에 0~6의번호를사용하여연산하고, 출력할때에는 A~G 문자로바꾸어표시한다. 깊이우선탐색을위해서 6장에서구현한스택프로그램을사용한다. 실행결과 > -43- -44-
그래프순회 너비우선탐색 너비우선탐색 (breadth first search : BFS) 순회방법 시작정점으로부터인접한정점들을모두차례로방문하고나서, 방문했던정점을시작으로하여다시인접한정점들을차례로방문하는방식 가까운정점들을먼저방문하고멀리있는정점들은나중에방문하는순회방법 인접한정점들에대해서차례로다시너비우선탐색을반복해야하므로선입선출의구조를갖는큐를사용 그래프순회 너비우선탐색 너비우선탐색의수행순서 ⑴ 시작정점 v를결정하여방문한다. ⑵ 정점 v에인접한정점들중에서방문하지않은정점을차례로방문하면서큐에 enqueue한다. ⑶ 방문하지않은인접한정점이없으면, 방문했던정점에서인접한정점들을다시차례로방문하기위해서큐에서 dequeue하여구한정점에서 ⑵를반복한다. ⑷ 큐가공백이될때까지 ⑵~⑶을반복한다. -45- -46-
그래프순회 너비우선탐색 너비우선탐색알고리즘 BFS(v) for (i 0; i<n; i i+1) do { visited[i] false; Q createqueue(); visited[v] true; v 방문 ; while (not isempty(q)) do { while (visited[v 의인접정점 w]=false) do { visited[w] true; w 방문 ; enqueue(q, w); v dequeue(q); end BFS() 그래프순회 너비우선탐색 너비우선탐색예 ) 그래프G9에대한너비우선탐색 초기상태 : 배열 visited를 False로초기화하고, 공백큐를생성 -47- -48-
그래프순회 너비우선탐색 1 정점 A 를시작으로너비우선탐색을시작한다. visited[a] true; A 방문 ; 그래프순회 너비우선탐색 2정점A의방문안한모든인접정점B, C를방문하고, 큐에 enqueue 한다. visited[(a의방문안한인접정점 B와 C)] true; (A의방문안한인접정점 B와 C) 방문 ; enqueue(q, (A 의방문안한인접정점 B 와 C)); -49- -50-
그래프순회 너비우선탐색 3 정점 A에대한인접정점들을처리했으므로, 너비우선탐색을계속할다음정점을찾기위해큐를 dequeue 하여정점 B를구한다. v dequeue(q); 그래프순회 너비우선탐색 4 정점 B의방문안한모든인접정점 D, E를방문하고큐에 enqueue 한다. visited[(b 의방문안한인접정점 D 와 E)] true; (B의방문안한인접정점 D와 E) 방문 ; enqueue(q, (B의방문안한인접정점 D와 E)); -51- -52-
그래프순회 너비우선탐색 5 정점 B에대한인접정점들을처리했으므로, 너비우선탐색을계속할다음정점을찾기위해큐를 dequeue 하여정점 C를구한다. v dequeue(q); 그래프순회 너비우선탐색 6 정점 C에는방문안한인접정점이없으므로, 너비우선탐색을계속할다음정점을찾기위해큐를 dequeue 하여정점 D를구한다. v dequeue(q); -53- -54-
그래프순회 너비우선탐색 7 정점 D의방문안한인접정점 G를방문하고큐에 enqueue 한다. visited[(d의방문안한인접정점 G)] true; (D의방문안한인접정점 G) 방문 ; enqueue(q, (D의방문안한인접정점 G)); 그래프순회 너비우선탐색 8 정점 D에대한인접정점들을처리했으므로, 너비우선탐색을계속할다음정점을찾기위해큐를 dequeue 하여정점 E를구한다. v dequeue(q); -55- -56-
그래프순회 너비우선탐색 9 정점 E에는방문안한인접정점이없으므로, 너비우선탐색을계속할다음정점을찾기위해큐를 dequeue 하여정점 G를구한다. v dequeue(q); 그래프순회 너비우선탐색 10 정점 G의방문안한인접정점 F를방문하고큐에 enqueue 한다. visited[(g의방문안한인접정점 F)] true; (G의방문안한인접정점 F) 방문 ; enqueue(q, (G의방문안한인접정점 F)); -57- -58-
그래프순회 너비우선탐색 11 정점 G에대한인접정점들을처리했으므로, 너비우선탐색을계속할다음정점을찾기위해큐를 dequeue 하여정점 F를구한다. v dequeue(q); 그래프순회 너비우선탐색 12 정점 F에는방문안한인접정점이없으므로, 너비우선탐색을계속할다음정점을찾기위해큐를 dequeue 하는데큐가공백이므로너비우선탐색을종료한다. 그래프 G9 의너비우선탐색경로 : A-B-C-D-E-G-F -59- -60-
그래프순회 너비우선탐색프로그램 그래프 G9를너비우선탐색하는 C 프로그램 그래프 G9를인접리스트로표현한다. 정점 A~G 대신에 0~6의번호를사용하여연산하고, 출력할때에는 A~G 문자로바꾸어표시한다. 너비우선탐색을위해서 7장에서구현한큐프로그램을사용한다. 실행결과 > 신장트리와최소비용신장트리 신장트리 (spanning tree) n개의정점으로이루어진무방향그래프 G에서 n개의모든정점과 n-1개의간선으로만들어진트리 그래프 G1과신장트리의예 -61- -62-
신장트리와최소비용신장트리 깊이우선신장트리 (depth first spanning tree) 깊이우선탐색을이용하여생성된신장트리 너비우선신장트리 (breadth first spanning tree) 너비우선탐색을이용하여생성된신장트리 그래프 G1의깊이우선신장트리와너비우선신장트리 신장트리와최소비용신장트리 최소비용신장트리 (minimum cost spanning tree) 무방향가중치그래프에서신장트리를구성하는간선들의가중치합이 최소인신장트리 가중치그래프의간선에주어진가중치 비용이나거리, 시간을의미하는값 최소비용신장트리를만드는알고리즘 Kruskal 알고리즘 Prime 알고리즘 -63- -64-
신장트리와최소비용신장트리 Kruskal 알고리즘Ⅰ 가중치가높은간선을제거하면서최소비용신장트리를만드는방법 Kruskal 알고리즘Ⅰ ⑴ 그래프 G의모든간선을가중치에따라내림차순으로정리한다. ⑵ 그래프 G에서가중치가가장높은간선을제거한다. 이때정점을그래프에서분리시키는간선은제거할수없으므로이런경우에는그다음으로가중치가높은간선을제거한다. ⑶ 그래프 G에 n-1개의간선만남을때까지 ⑵를반복한다. ⑷ 그래프에 n-1개의간선이남게되면최소비용신장트리가완성된다. 신장트리와최소비용신장트리 Kruskal 알고리즘 Ⅰ 을이용하여 G10 의최소비용신장트리만들기 초기상태 : 그래프 G10 의간선을가중치에따라서내림차순정렬 -65- -66-
신장트리와최소비용신장트리 1 가중치가가장큰간선 (A,C) 제거. ( 현재남은간선의수 : 10 개 ) 신장트리와최소비용신장트리 2 남은간선중에서가중치가가장큰간선 (F,G) 제거. ( 현재남은간선의수 : 9개 ) -67- -68-
신장트리와최소비용신장트리 3 남은간선중에서가중치가가장큰간선 (B,G) 제거. ( 현재남은간선의수 : 8개 ) 신장트리와최소비용신장트리 4 남은간선중에서가중치가가장큰간선 (C,E) 제거. ( 현재남은간선의수 : 7개 ) -69- -70-
신장트리와최소비용신장트리 5 남은간선중에서가중치가가장큰간선 (D,E) 를제거하면, 그래프가분리되어단절그래프가되므로, 그다음으로가중치가큰간선 (C,F) 를제거해야한다. 그런데간선 (C,F) 를제거하면정점 C가분리되므로제거할수없으므로, 다시그다음으로가중치가큰간선 (A,D) 를제거한다. ( 현재남은간선의수 : 6개 ) 신장트리와최소비용신장트리 현재남은간선의수가 6개이므로알고리즘수행을종료하고신장트리완성. G10의최소비용신장트리 -71- -72-
신장트리와최소비용신장트리 Kruskal 알고리즘Ⅱ 가중치가낮은간선을삽입하면서최소비용신장트리를만드는방법 Kruskal 알고리즘Ⅱ ⑴ 그래프 G의모든간선을가중치에따라오름차순으로정리한다. ⑵ 그래프 G에가중치가가장작은간선을삽입한다. 이때사이클을형성하는간선은삽입할수없으므로이런경우에는그다음으로가중치가작은간선을삽입한다. ⑶ 그래프 G에 n-1개의간선을삽입할때까지 ⑵를반복한다. ⑷ 그래프 G의간선이 n-1개가되면최소비용신장트리가완성된다. 신장트리와최소비용신장트리 Kruskal 알고리즘 Ⅱ 를이용하여 G10 의최소비용신장트리만들기 초기상태 : 그래프 G10 의간선을가중치에따라서오름차순정렬 -73- -74-
신장트리와최소비용신장트리 1 가중치가가장작은간선 (E,G) 삽입. ( 현재삽입한간선의수 : 1 개 ) 신장트리와최소비용신장트리 2 나머지간선중에서가중치가가장작은간선 (A,B) 삽입. ( 현재삽입한간선의수 : 2개 ) -75- -76-
신장트리와최소비용신장트리 3 나머지간선중에서가중치가가장작은간선 (E,F) 삽입. ( 현재삽입한간선의수 : 3개 ) 신장트리와최소비용신장트리 4 나머지간선중에서가중치가가장작은간선 (B,D) 삽입. ( 현재삽입한간선의수 : 4개 ) -77- -78-
신장트리와최소비용신장트리 5 나머지간선중에서가중치가가장작은간선 (A,D) 를삽입하면 A- B-D의사이클이생성되므로삽입할수없다. 그다음으로가중치가가장작은간선 (C,F) 삽입. ( 현재삽입한간선의수 : 5개 ) 신장트리와최소비용신장트리 6 나머지간선중에서가중치가가장작은간선 (D,E) 삽입. ( 현재삽입한간선의수 : 6개 ) 현재삽입한간선의수가 6개이므로알고리즘수행을종료하고신장트리완성. -79- -80-
신장트리와최소비용신장트리 G10 의최소비용신장트리 -81-