Chapter 10 그래프 (graph) SANGJI University Kwangman KO (kkman@sangji.ac.kr)
그래프 (graph) 그래프 연결되어있는객체간의관계를표현하는자료구조 예 : 전기회로, 프로젝트관리, 지도에서도시들의연결 다양한모델에적용할수있는유연성있는자료구조 연결되어있는객체간의관계를표현하는자료구조 꼭지점 (vertex) 와변 (edge) 으로구성 물리적인모델링이나추상적인모델모두에쉽게적용. kkman@sangji.ac.kr -2-
그래프역사 오일러문제 1800 년대오일러에의하여창안 모든다리를한번만건너서처음출발했던장소로돌아오는문제 문제의핵심만을표현 위치 : 정점 (node) 다리 : 간선 (edge) 오일러경로 정점에연결된간선의개수가짝수이면존재 kkman@sangji.ac.kr -3-
그래프용어 그래프는 (V, E) 로표시 V 는정점 (vertices) 들의집합 E 는간선 (edge) 들의집합 정점과간선은모두관련되는데이터를저장 ( 예 ) 예제그래프 정점은각도시를의미 간선은도시를연결하는도로를의미 간선에는도로의길이등의데이터가저장될수있음 kkman@sangji.ac.kr -5-
인접 (adjacency) 두꼭지점이하나의변으로연결되어있는경우 A 와 B, B 와 C, B 와 E, D 와 E 는인접. 경로 (path) 두꼭지점을연결하는변들의연결 경로에서는꼭지점과변이교대로나타나지만연결된꼭지점의나열로표기. A 와 D 사이의경로는 ABED kkman@sangji.ac.kr -6-
그래프의종류 무방향그래프 (undirected graph) 연결된그래프 (connected graph) 무방향간선 간선을통해서양방향으로갈수있음을표현 (A, B) 와같이정점의쌍으로표현 (A, B) = (B, A) A B kkman@sangji.ac.kr -7-
그래프 (directed graph) 로구분 방향간선 방향성이존재하는간선으로도로의일방통행길과마찬가지로한쪽방향으로만갈수있음을표시 A, B> 로표시, <A, B> <B, A> A B kkman@sangji.ac.kr -8-
가중치그래프 (weighted graph) 간선에비용이나가중치가할당된그래프 A 1200 B kkman@sangji.ac.kr -9-
그래프표현의예 V(G1)= {0, 1, 2, 3}, E(G1)= {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)} V(G2)= {0, 1, 2, 3}, E(G3)= {(0, 1), (0, 2))} V(G2)= {0, 1, 2}, E(G2)= {<0, 1>, <1, 0>, <1, 2>} kkman@sangji.ac.kr -10-
그래프용어 인접정점 (adjacent vertex) 간선에의해연결된정점 정점 0 와정점 1 차수 (degree) 정점에연결된다른정점의개수 정점 0 의차수는 3 경로 (path) 정점의나열로표현 단순경로 : 0, 1, 2, 3 사이클 (cycle): 0, 1, 2, 0 kkman@sangji.ac.kr -11-
경로의길이 경로를구성하는데사용된간선의수 완전그래프 모든정점이연결되어있는그래프 kkman@sangji.ac.kr -12-
그래프 ADT 객체 : 정점의집합과간선의집합 연산 : create_graph() ::= 그래프생성 init(g) ::= 그래프 g 를초기화 insert_vertex(g,v) ::= 그래프 g 에정점 v 를삽입 insert_edge(g,u,v) ::= 그래프 g 에간선 (u,v) 를삽입 delete_vertex(g,v) ::= 그래프 g 의정점 v 를삭제 delete_edge(g,u,v) ::= 그래프 g 의간선 (u,v) 를삭제 is_empty(g) ::= 그래프 g 가공백상태인지확인 adjacent(v) ::= 정점 v 에인접한정점들의리스트를반환 destroy_graph(g) ::= 그래프 g 를제거 kkman@sangji.ac.kr -13-
그래프표현방법 그래프표현방법 인접행렬 (adjacent matrix) 2 차원배열사용표현 인접리스트 (adjacency list) 연결리스트를사용표현 kkman@sangji.ac.kr -14-
인접행렬 간선 (i, j) 가그래프에존재, M[i][j] = 1 간선 (i, j) 가그래프에존재하지않음, M[i][j] = 0. kkman@sangji.ac.kr -15-
인접리스트 각정점에인접한정점들을연결리스트로표현 각꼭지점은자신의연결리스트를하나씩유지 자신의연결리스트에자신이연결된꼭지점을항목으로추가 kkman@sangji.ac.kr -16-
kkman@sangji.ac.kr -17-
그래프탐색 탐색 전체그래프를검색하기위하여한꼭지점에서시작하여주변꼭지점들을순서에맞추어방문하는과정 하나의정점으로부터시작하여차례대로모든정점들을한번씩방문 종류 깊이우선탐색 (Depth First Search; DFS) 너비우선탐색 (Breadth First Search; BFS) kkman@sangji.ac.kr -18-
깊이우선탐색 (DFS) 특징 미로를탐색할때한방향으로갈수있을때까지계속가다가더이상갈수없게되면다시가장가까운갈림길로돌아와서이곳으로부터다른방향으로다시탐색을진행하는방법과유사 시작꼭지점에서멀어지는방향으로탐색. 스택을이용하여구현 kkman@sangji.ac.kr -19-
단계 1 스택에서꼭지점 pop. 스택에아무것도없으면탐색을종료 단계 2 꺼내온꼭지점으로이동하고방문표시 단계 3 현재꼭지점에연결된다른꼭지점들을찾아서해당꼭지점에방문한적이없으면스택에 push 단계 4 현재의꼭지점에연결되어있고방문하지않은꼭지점들을모두스택에넣고나면단계 1로돌아간다. kkman@sangji.ac.kr -20-
스텝 스택 탐색한꼭지점 1 A 2 B, F, G A 3 B, F, H A, G 4 B, F A, G, H 5 B A, G, H, F 6 C, D A, G, H, F, B 7 C, E A, G, H, F, B, D 8 C A, G, H, F, B, D, E 9 A, G, H, F, B, D, E, C kkman@sangji.ac.kr -21-
kkman@sangji.ac.kr -22-
DFS 프로그램 // 인접행렬로표현된그래프에대한깊이우선탐색 void dfs_mat(graphtype *g, int v) { int w; visited[v] = TRUE; // 정점 v의방문표시 printf("%d ", v); // 방문한정점출력 for(w=0; w<g->n; w++) // 인접정점탐색 if( g->adj_mat[v][w] &&!visited[w] ) dfs_mat(g, w); // 정점 w에서 DFS 새로시작 } // 인접리스트로표현된그래프에대한깊이우선탐색 void dfs_list(graphtype *g, int v) { GraphNode *w; visited[v] = TRUE; // 정점 v 의방문표시 printf("%d ", v); // 방문한정점출력 for(w=g->adj_list[v]; w; w=w->link)// 인접정점탐색 if(!visited[w->vertex]) dfs_list(g, w->vertex); // 정점 w 에서 DFS 새로시작 } kkman@sangji.ac.kr -23-
너비우선탐색 (BFS) 특징 시작꼭지점에서먼순서대로탐색진행 시작정점으로부터가까운정점을먼저방문하고멀리떨어져있는정점을나중에방문하는순회방법 시작꼭지점에서같은거리에있는꼭지점들부터선택 큐를이용하여구현 kkman@sangji.ac.kr -24-
단계 1 큐에서꼭지점을하나꺼내온다. 큐에아무것도없으면탐색을종료 단계 2 꺼내온꼭지점으로이동하고방문표시 단계 3 현재꼭지점에연결된다른꼭지점들을찾아서해당꼭지점에방문한적이없으면 ( 방문표시가없으면 ) 큐에집어넣는다. 단계 4 현재의꼭지점에연결되어있고방문하지않은꼭지점들을모두스택에넣고나면단계 1 로돌아간다. kkman@sangji.ac.kr -25-
1 A 스텝큐탐색한꼭지점 1 A 5 2 C B D 3 6 F G 4 7 H 2 B, F, G A 3 F, G, C, D A, B 4 G, C, D A, B, F 5 C, D, H A, B, F, G 6 D, H A, B, F, G, C 7 H, E A, B, F, G, C, D 8 E 8 E A, B, F, G, C, D,H 9 A, B, F, G, C, D,H, E kkman@sangji.ac.kr -26-
kkman@sangji.ac.kr -27-
BFS 알고리즘 void bfs_mat(graphtype *g, int v) { int w; QueueType q; init(&q); // 큐초기화 visited[v] = TRUE; // 정점 v 방문표시 printf("%d ", v); enqueue(&q, v); // 시작정점을큐에저장 while(!is_empty(&q)){ v = dequeue(&q); // 큐에정점추출 for(w=0; w<g->n; w++) // 인접정점탐색 if(g->adj_mat[v][w] &&!visited[w]){ visited[w] = TRUE; // 방문표시 printf("%d ", w); enqueue(&q, w); // 방문한정점을큐에저장 } } } kkman@sangji.ac.kr -28-
연결성분 연결성분 (connected component) 최대로연결된부분그래프들을찾는것 그래프탐색으로찾을수있다. visited[i]=count; kkman@sangji.ac.kr -29-
위상정렬 위상정렬 (topological sorting) 그래프를이용한정렬방법 방향그래프에서꼭지점을연결하는변들의방향이용 방향그래프 그래프의변이방향을가지고있어서, 방향에따라두꼭지점의연결여부가결정 인접행렬과인접리스트가모두사용 kkman@sangji.ac.kr -30-
kkman@sangji.ac.kr -31- 방향그래프 방향그래프에서의인접행렬과인접리스트 0 0 0 C 1 0 0 B 1 0 0 A C B A 0 0 0 C 1 0 0 B 1 0 0 A C B A A B C A B C E D E D C B A E D C B A C E A E
방향그래프순환과연결 방향그래프의순환 방향그래프에서도연결된꼭지점에따라경로설정 순환 (cycle) 경로의시작과끝이연결된그래프 Directed Acyclic Graph, DAG 순환을가지지않는방향그래프 위상정렬수행 A E B D C kkman@sangji.ac.kr -32-
방향그래프의연결 한꼭지점에서연결될수있는꼭지점의집합 이렇게찾은꼭지점의집합의역은성립되지않음 Warshall 알고리즘이용. kkman@sangji.ac.kr -33-
위상정렬 방향그래프에의해정해진순서를따라정렬하는방법 DAG 를기반 선수과목체계 조건을만족하는여러가지결과가가능 방향그래프에서간선 <u, v> 정점 u 는정점 v 를선행 방향그래프에존재하는각정점들의선행순서를위배하지않으면서모든정점을나열하는것 kkman@sangji.ac.kr -34-
정렬결과 1: 컴퓨터공학기초 -> 프로그래밍기초 -> C 프로그래밍 -> 객체지향기초 -> Java 프로그래밍 -> Python 프로그래밍 -> Perl 프로그래밍 정렬결과 2: 프로그래밍기초 -> 컴퓨터공학기초 -> 객체지향기초 -> C 프로그래밍 -> Java 프로그래밍 -> Perl 프로그래밍 -> Python 프로그래밍
위상정렬수행단계 단계 1. 자신을가리키는변이없는꼭지점을찾는다. 단계 2. 찾은꼭지점을출력하고찾은꼭지점과그꼭지점에서출발하는변들을그래프에서지운다. 단계 3. 아직그래프에꼭지점이남아있으면단계 1 로돌아가고, 남아있지않으면위상정렬을종료. kkman@sangji.ac.kr -36-
과목번호 과목명 선수과목 0 전산학개론 없음 1 이산수학 없음 2 자료구조 1 3 알고리즘분석 0, 1, 2 4 운영체제 1 5 인공지능 2, 3, 4 n 위상정렬 : (0,1,2,3,4,5), (1,0,2,3,4,5) n (2,0,1,3,4,5) 는위상정렬 n 2 번정점이 0 번정점앞에오기때문이다. 간선 <0, 2> 이존재하기때문에 0 번정점이끝나야만이 2 번정점을시작할수있다. kkman@sangji.ac.kr -37-
kkman@sangji.ac.kr -38-
가중치그래프 가중치그래프 (weighted graph) 그래프의변에가중치를부여한그래프 가중치 (weight) ~ 한꼭지점에서다른꼭지점사이를이동하기위해소요되는비용 인접행렬과인접리스트의방법이모두가능 ~ 인접행렬의방법이좀더단순 kkman@sangji.ac.kr -39-
인접행렬을이용한방법 꼭지점간연결이 1 에서설정된가중치로표기 kkman@sangji.ac.kr -40-
인접리스트를이용한구현 연결정보와함께가중치정보저장 kkman@sangji.ac.kr -41-
신장트리 신장트리 (spanning tree) 그래프내의모든정점을포함하는트리 모든정점들이연결 사이클을포함할수없음 그래프내의 n개의정점, n-1개의간선으로연결 신장트리검색 깊이우선탐색, 너비우선탐색에사용된간선의집합 kkman@sangji.ac.kr -42-
신장트리용도 최소의링크를사용하여네트워크를구축하고싶은경우 도로건설 - 도시들을모두연결하면서도로의길이가최소가되도록하는문제 전기회로 - 단자들을모두연결하면서전선의길이가가장최소가되도록하는문제 통신 - 전화선의길이가최소가되도록전화케이블망을구성하는문제 배관 - 파이프를모두연결하면서파이프의총길이가최소가되도록연결하는문제 kkman@sangji.ac.kr -43-
kkman@sangji.ac.kr -44-
최소신장트리 최소신장트리 (minimum spanning tree) 모든꼭지점을연결할수있도록최소한의변만선택한그래프 그래프의부분집합의개념 한그래프에서여러최소신장트리구성가능 E = V -1 ~ E : 최소신장트리에서필요한변의수 ~ V : 그래프에있는모든꼭지점의수 kkman@sangji.ac.kr -45-
최소신장트리의구현, DFS 이용 DFS 는그래프의연결된변을따라탐색을수행하기때문에적용 하나의꼭지점에서연결된다른꼭지점을찾는과정을반복적으로수행하며모든꼭지점을방문. ~ 지나온변들이최소신장트리를구성 kkman@sangji.ac.kr -47-
MST 알고리즘 2 가지의대표적인알고리즘 Kruskal의알고리즘 Prim의알고리즘 kkman@sangji.ac.kr -48-
Kruskal 의알고리즘 탐욕적인방법 (greedy method) 알고리즘설계에서있어서중요한기법중의하나 결정을해야할때마다그순간에가장좋다고생각되는것을해답으로선택함으로써최종적인해답에도달 탐욕적인방법은항상최적의해답을주는지를반드시검증해야한다. Kruskal 의알고리즘은최적의해답을주는것으로증명 kkman@sangji.ac.kr -49-
특징 최소비용신장트리가최소비용의간선으로구성됨과동시에사이클을포함하지않는다는조건 각단계에서사이클을이루지않는최소비용간선을선택 그래프의간선 가중치의오름차순으로정렬 정렬된간선들의리스트중 사이클을형성하지않는간선을찾아서현재의최소비용신장트리의집합에추가 사이클을형성하면그간선은제외 kkman@sangji.ac.kr -50-
kkman@sangji.ac.kr -51-
kkman@sangji.ac.kr -52-
kkman@sangji.ac.kr -53-
Kruskal 의 MST 알고리즘의구현 union-find 알고리즘 집합들의합집합을구하고집합의원소가어떤집합에속하는지를계산하는알고리즘 여러가지방법으로구현이가능 Kruskal 의 MST 알고리즘에서사이클검사에사용 kkman@sangji.ac.kr -54-
a 와 b 가같은집합에속함 a 와 b 가다른집합에속함 kkman@sangji.ac.kr -55-
Prim 의 MST 알고리즘 특징 시작정점에서부터출발하여신장트리집합을단계적으로확장해나가는방법 시작단계에서는시작정점만이신장트리집합에포함 앞단계에서만들어진신장트리집합에, 인접한정점들중에서최저간선으로연결된정점을선택하여트리를확장 트리가 n-1 개의간선을가질때까지계속. kkman@sangji.ac.kr -56-
간선 (a, b) 와간선 (f, e) 의가중치를비교해보면 (f, e) 가 27 로서 (a, b) 의 29 보다높다. 따라서 (f, e) 간선이선택되고정점 e 가신장트리집합에포함된다. kkman@sangji.ac.kr -57-
Prim 의 MST 알고리즘 kkman@sangji.ac.kr -58-
Prim 의 MST 알고리즘 kkman@sangji.ac.kr -59-
Prim 의 MST 알고리즘 kkman@sangji.ac.kr -60-
최단경로알고리즘 최단경로 (shortest path) 문제 네트워크에서정점 i 와정점 j 를연결하는경로중에서간선들의가중치합이최소가되는경로를찾는문제 간선의가중치는비용, 거리, 시간등 그래프를적용하는가장보편적인경우 가중치와방향을모두가지는그래프를기준으로하여최단경로탐색과정수행 kkman@sangji.ac.kr -61-
kkman@sangji.ac.kr -62-
Dijkstra 의최단경로알고리즘 Dijkstra 알고리즘 꼭지점에서시작해서주변꼭지점으로퍼져가며최단경로탐색 단계 단계 1: 현재선택된꼭지점을 고정 으로표시 단계 2: 선택된꼭지점에연결된변들을통하여다른꼭지점들까지연결되는더짧은경로가있는지를확인, 더짧은경로가있다면꼭지점의 거리정보 를갱신 단계 3: 각꼭지점까지의거리를확인하여 고정 으로표시되지않은꼭지점중거리가가장짧은꼭지점을선택 kkman@sangji.ac.kr -63-
~ 단계 4: 모든꼭지점이 고정 으로표시되었으면최단경로탐색을중지하고아니면단계 1 로돌아간다. ~ ( 고정 : 해당꼭지점에대한최단경로탐색이완료되었기때문에이를확정하고더이상고려하지않음을의미 ) 집합 S: 시작정점 v 로부터의최단경로가이미발견된정점들의집합 distance 배열 최단경로를알려진정점만을통하여각정점까지가는최단경로의길이 매단계에서가장 distance 값이적은정점을 S 에추가. kkman@sangji.ac.kr -64-
kkman@sangji.ac.kr -65-
매단계에서새로운정점이 S 에추가되면 distance 값을갱신 kkman@sangji.ac.kr -66-
kkman@sangji.ac.kr -67-
kkman@sangji.ac.kr -69-
kkman@sangji.ac.kr -70-
kkman@sangji.ac.kr -71-
kkman@sangji.ac.kr -72-
kkman@sangji.ac.kr -73-
kkman@sangji.ac.kr -74-
kkman@sangji.ac.kr -75-
최단경로탐색결과 각꼭지점이자기의전꼭지점으로가리키고있는꼭지점을거꾸로올라가면최단경로 도시대전강릉대구광주부산 경로서울-대전서울-강릉서울-강릉-대구서울-대전-광주서울-강릉-대구-부산 kkman@sangji.ac.kr -76-