슬라이드 1

Size: px

Start display at page:

Download "슬라이드 1"

산 소
4 years ago
Views:

1 CHAP 10 : 그래프 yicho@gachon.ac.kr 1

2 그래프역사 1800 년대오일러에의하여창안 오일러문제 모든다리를한번만건너서처음출발했던장소로돌아오는문제 A,B,C,D 지역의연결관계표현 위치 : 정점 (node) 다리 : 간선 (edge) 오일러정리 모든정점에연결된간선의수가짝수이면오일러경로존재함 따라서그래프 (b) 에는오일러경로가존재하지않음 2

3 그래프정의 그래프 G 는 (V, E) 로표시 정점 (vertices) 여러가지특성을가질수있는객체의미 V(G) : 그래프 G 의정점들의집합 노드 (node) 라고도불림 간선 (edge) 정점들간의관계의미 E(G) : 그래프 G 의간선들의집합 링크 (link) 라고도불림 3

4 그래프의종류 무방향그래프 (undirected graph) 무방향간선 (undirected edge) 만사용 간선을통해서양방향으로갈수있음 도로의왕복통행길 (A, B) 와같이정점의쌍으로표현 (A, B) = (B, A) A B 방향그래프 (directed graph) 방향간선 (undirected edge) 만사용 간선을통해서한쪽방향으로만갈수있음 도로의일방통행길 <A, B> 와같이정점의쌍으로표현 <A, B> <B, A> A B 4

5 가중치그래프 가중치그래프 (weighted graph) 는네트워크 (network) 라고도함 간선에비용 (cost) 이나가중치 (weight) 가할당된그래프 A 1200 B 가중치그래프예 정점 : 각도시를의미 간선 : 도시를연결하는도로의미 가중치 : 도로의길이 5

6 그래프표현의예 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(G3)= {0, 1, 2}, E(G2)= {<0, 1>, <1, 0>, <1, 2>} 6

7 부분그래프 (subgraph) 정점집합 V(G) 와간선집합 E(G) 의부분집합으로이루어진그래프 그래프 G1 의부분그래프들 7

8 인접정점 (adjacent vertex) 그래프 하나의정점에서간선에의해직접연결된정점 G1에서정점 0의인접정점 : 정점 1, 정점 2, 정점 3 무방향그래프의차수 (degree) 하나의정점에연결된다른정점의수 G1에서정점 0의차수 : 3 무방향그래프의모든차수의합은간선수의 2배 G1의차수의합 : 10 G1의간선의합 : 5 8

9 방향그래프의차수 (degree) 그래프 진입차수 (in-degree) : 외부에서오는간선의수 진출차수 (out-degree) : 외부로향하는간선의수 G3에서정점 1의차수 : 내차수 1, 외차수 2 방향그래프의모든진입 ( 진출 ) 차수의합은간선의수 G3의진입차수의합 : 3 G3의진입차수의합 : 3 G3의간선합 : 3 9

10 그래프의경로 (path) 무방향그래프의정점 s 로부터정점 e 까지의경로 정점의나열 s, v1, v2,..., vk, e 나열된정점들간에반드시간선 (s, v1), (v1, v2),..., (vk, e) 존재 방향그래프의정점 s 로부터정점 e 까지의경로 정점의나열 s, v1, v2,..., vk, e 나열된정점들간에반드시간선 <s, v1>, <v1, v2>,...,<vk, e> 존재 경로의길이 (length) 경로를구성하는데사용된간선의수 단순경로 (simple path) 경로중에서반복되는간선이없는경로 사이클 (cycle) 단순경로의시작정점과종료정점이동일한경로 10

11 그래프의경로 (path) G1의 0, 1, 2,3은경로지만 0, 1, 3, 2는경로아님 G1의1, 0, 2, 3은단순경로이지만 1, 0, 2, 0은단순경로아님 G1의 0, 1, 2, 0과 G3의 0, 1, 0은사이클 11

12 그래프의연결정도 연결그래프 (connected graph) 무방향그래프 G에있는모든정점쌍에대하여항상경로존재 G2는비연결그래프임 트리 (tree) 그래프의특수한형태로서사이클을가지지않는연결그래프 트리의예 12

13 그래프의연결정도 완전그래프 (complete graph) 모든정점이연결되어있는그래프 n개의정점을가진무방향완전그래프의간선의수 : n (n-1)/2 n=4, 간선의수 = (4 3)/2 = 6 13

14 그래프 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 를제거한다. 그래프에정점을추가하려면 insert_vertex 연산사용 그래프에간선을추가하려면 insert_edge 연산사용 14

15 그래프표현방법 인접행렬 (adjacent matrix) 방법 if( 간선 (i, j) 가그래프에존재 ) M[i][j] = 1, 그렇지않으면 M[i][j] = 0. 인접행렬의대각선성분은모두 0( 자체간선불허 ) 무방향그래프의인접행렬은대칭 15

16 그래프표현방법 (cont.) 인접리스트 (adjacency list) 방법 각정점에인접한정점들을연결리스트로표현 16

17 그래프탐색 그래프의가장기본적인연산 하나의정점으로부터시작하여차례대로모든정점들을한번씩방문 많은문제들이단순히그래프의노드를탐색하는것으로해결 ( 예 ) 도로망에서특정도시에서다른도시로갈수있는지여부 ( 예 ) 전자회로에서특정단자와다른단자가서로연결되어있는지여부 17

18 깊이우선탐색 (DFS) 깊이우선탐색 (DFS: depth-first search) 한방향으로갈수있을때까지가다가더이상갈수없게되면가장가까운갈림길로돌아와서이곳으로부터다른방향으로다시탐색진행 되돌아가기위해서는스택필요 ( 순환함수호출로묵시적인스택이용가능 ) 18

19 DFS 알고리즘 depth_first_search(v) v 를방문되었다고표시 ; for all u (v 에인접한정점 ) do if (u 가아직방문되지않았으면 )then depth_first_search(u) 19

20 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 새로시작 } 20

21 너비우선탐색 (BFS) 너비우선탐색 (BFS: breadth-first search) 시작정점으로부터가까운정점을먼저방문하고멀리떨어져있는정점을나중에방문하는순회방법 큐를사용하여구현됨 너비우선탐색알고리즘 breadth_first_search(v) v 를방문되었다고표시 ; 큐 Q 에정점 v 를삽입 ; while (not is_empty(q)) do Q 에서정점 w 를삭제 ; for all u (w 에인접한정점 ) do if (u 가아직방문되지않았으면 ) then u 를큐에삽입 ; u 를방문되었다고표시 ; 21

22 22

$find_connected_component(graphtype *g) { int i; count = 0; for(i=0; i<g->n; i++) if(!$

23 연결성분 최대로연결된부분그래프들 DFS 또는 BFS 반복이용 DFS 또는 BFS 탐색프로그램의 visited[v]=true; 를 visited[v]=count; 로교체 void find_connected_component(graphtype *g) { int i; count = 0; for(i=0; i<g->n; i++) if(!visited[i]){ // 방문되지않았으면 count++; dfs_mat(g, i); } } 23

24 신장트리 (spanning tree) 그래프내의모든정점을포함하는트리 모든정점들이연결되어있어야하고사이클을포함해서는안됨 n개의정점을가지는그래프의신장트리는 n-1개의간선을가짐 최소의링크를사용하는네트워크구축시사용 : 통신망, 도로망, 유통망등 신장트리알고리즘 depth_first_search(v) v 를방문되었다고표시 ; for all u (v 에인접한정점 ) do if (u 가아직방문되지않았으면 ) then (v,u) 를신장트리간선이라고표시 ; depth_first_search(u); 24

25 25 신장트리

26 최소비용신장트리 (MST: minimum spanning tree) 네트워크에있는모든정점들을가장적은수의간선과비용으로연결 MST의응용 도로건설 - 도시들을모두연결하면서도로의길이를최소가되도록하는문제 전기회로 - 단자들을모두연결하면서전선의길이를가장최소로하는문제 통신 - 전화선의길이가최소가되도록전화케이블망을구성하는문제 배관 - 파이프를모두연결하면서파이프의총길이를최소로하는문제 26

27 Kruskal 의 MST 알고리즘 탐욕적인방법 (greedy method) 주요알고리즘설계기법 각단계에서최선의답을선택하는과정을반복함으로써최종적인해답에도달 탐욕적인방법은항상최적의해답을주는지검증필요 Kruskal MST 알고리즘은최적의해답임이증명됨 27

28 Kruskal 의 MST 알고리즘 MST 는최소비용의간선으로구성됨과동시에사이클을포함하지않아야함 각단계에서사이클을이루지않는최소비용간선선택 그래프의간선들을가중치의오름차순으로정렬 정렬된간선중에서사이클을형성하지않는간선을현재의 MST 집합에추가 만약사이클을형성하면그간선은제외 28

29 29

30 Kruskal 의 MST 알고리즘 union-find 알고리즘 두집합들의합집합만듬 원소가어떤집합에속하는지알아냄 Kruskal의 MST 알고리즘에서사이클검사에사용 a 와 b 가같은집합에속함 a 와 b 가다른집합에속함 30

31 Kruskal 의 MST 알고리즘복잡도 Kruskal 알고리즘은대부분간선들을정렬하는시간에좌우됨 사이클테스트등의작업은정렬에비해매우신속하게수행됨 네트워크의간선 e 개를퀵정렬과같은효율적인알고리즘으로정렬한다면 Kruskal 알고리즘의시간복잡도는 O(e*log(e)) 가된다 31

32 Prim 의 MST 알고리즘 시작정점에서부터출발하여신장트리집합을단계적으로확장해나감 시작단계에서는시작정점만이신장트리집합에포함됨 신장트리집합에인접한정점중에서최저간선으로연결된정점선택하여신장트리집합에추가함 이과정은신장트리집합이 n-1 개의간선을가질때까지반복 간선 (a, b)=29 간선 (f, e)=27 간선 (f, e) 선택 정점 e 가신장트 리집합에추가됨 32

33 33 Prim 의 MST 알고리즘

34 34

35 Prim 의 MST 알고리즘복잡도 주반복문이정점의수 n 만큼반복하고, 내부반복문이 n 번반복하므로 Prim 의알고리즘은 O(n2) 의복잡도를가진다. 희박한그래프 O(e*log(e)) 인 Kruskal 의알고리즘이유리 밀집한그래프 O(n 2 ) 인 Prim 의알고리즘이유리 35

36 최단경로 (shortest path) 네트워크에서정점 u 와정점 v 를연결하는경로중에서간선들의가중치합이최소가되는경로 간선의가중치는비용, 거리, 시간등 정점 0 에서정점 3 으로가는최단경로문제 인접행렬에서간선이없는노드쌍의가중치는 임 0,4,1,2,3 이최단경로 최단경로길이는 =11 36

37 Dijkstra 의최단경로알고리즘 하나의시작정점으로부터모든다른정점까지의최단경로찾음 집합 S 시작정점 v 로부터의최단경로가이미발견된정점들의집합 distance 배열 최단경로가알려진정점들만을이용한다른정점들까지의최단경로길이 distance 배열의초기값 ( 시작정점 v) distance[v] = 0 다른정점에대한 distance 값은시작정점과해당정점간의가중치값 매단계에서가장 distance 값이작은정점을 S 에추가 37

38 Dijkstra 의최단경로알고리즘 distance 값이가장작은정점을 u 라고하자. 그러면시작정점 v 에서정점 u 까지의최단거리는경로 1 이된다. 정점 w 를거쳐서정점 u 로가는가상적인더짧은경로가있다고가정해보자. 그러면정점 v 에서정점 u 까지의거리는정점 v 에서정점 w 까지의거리 2 와정점 w 에서정점 u 로가는거리 3 을합한값이된다. 그러나경로 2 는경로 1 보다항상길수밖에없다. 왜냐하면현재 distance 값이가장작은정점은 u 이기때문이다. 따라서매단계에서 distance 값이가장작은정점들을추가해나가면시작정점에서모든정점까지의최단거리를구할수있다. 38

39 Dijkstra 의최단경로알고리즘 새로운정점이 S 에추가되면 distance 값갱신 39

40 Dijkstra 의최단경로알고리즘 // 입력 : 가중치그래프 G, 가중치는음수가아님. // 출력 : distance 배열, distance[u] 는 v 에서 u 까지의최단거리이다. shortest_path(g, v) S {v} for 각정점 w G do distance[w] weight[v][w]; while 모든정점이 S에포함되지않으면 do u 집합 S에속하지않는정점중에서최소 distance 정점 ; S S {u} for u에인접하고 S에있는각정점 z do if distance[u]+weight[u][z] < distance[z] then distance[z] distance[u]+weight[u][z]; 40

41 41 Dijkstra 의최단경로알고리즘

42 42 Dijkstra 의최단경로알고리즘

43 Dijkstra 의최단경로프로그램 43 #include <stdio.h> #include <limits.h> #define TRUE 1 #define FALSE 0 #define MAX_VERTICES 7 // 정점의수 #define INF 1000 // 무한대 ( 연결이없는경우 ) int weight[max_vertices][max_vertices]={ // 네트워크의인접행렬 { 0, 7, INF, INF, 3, 10, INF }, { 7, 0, 4, 10, 2, 6, INF }, { INF, 4, 0, 2, INF, INF, INF }, { INF, 10, 2, 0, 11, 9, 4 }, { 3, 2, INF, 11, 0, INF, 5 }, { 10, 6, INF, 9, INF, 0, INF }, { INF, INF, INF, 4, 5, INF, 0 }}; int distance[max_vertices]; // 시작정점으로부터의최단경로거리 int found[max_vertices]; // 방문한정점표시 // int choose(int distance[], int n, int found[]) { int i, min, minpos; min = INT_MAX; minpos = -1; for(i=0;i<n;i++) if( distance[i]< min &&! found[i] ){ min = distance[i]; minpos=i; } return minpos; }

44 44 Dijkstra 의최단경로프로그램 (cont.) void shortest_path(int start, int n) { int i, u, w; for(i=0; i<n; i++) // 초기화 {distance[i] = weight[start][i]; found[i] = FALSE; } found[start] = TRUE; // 시작정점방문표시 distance[start] = 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]+weight[u][w]<distance[w] ) distance[w] = distance[u]+weight[u][w]; } } // void main() { shortest_path(0, MAX_VERTICES); }

45 Dijkstra 의최단경로알고리즘복잡도 네트워크에 n 개의정점이있다면, Dijkstra 의최단경로알고리즘은주반복문을 n 번반복하고내부반복문을 2n 번반복하므로 O(n 2 ) 의복잡도를가진다. 45

46 Floyd 의최단경로알고리즘 모든정점사이의최단경로를찾음 2차원배열 A를이용하여 3중반복을하는루프로구성 인접행렬 weight 구성 i==j이면, weight[i][j]=0 두개의정점 i,j 사이에간선이존재하지않으면, weight[i][j]= 정점 i,j 사이에간선이존재하면, weight[i][j] 는간선 (i, j) 의가중치 배열 A의초기값은인접행렬 weight임 floyd(g) for k 0 to n - 1 for i 0 to n - 1 for j 0 to n - 1 A[i][j] = min(a[i][j], A[i][k] + A[k][j]) 46

47 Floyd 의최단경로알고리즘 A k [i][j] 0 부터 k 까지의정점만을이용한정점 i 에서 j 까지의최단경로길이 A -1 A 0 A 1 A n-1 순으로최단경로구해감 A k-1 까지구해진상태에서 k 번째정점이추가로고려되는상황을생각하자 0 부터 k 까지의정점만을사용하여정점 i 에서정점 j 로가는최단경로는다음의 2 가지의경우로나뉘어진다. 정점 k 를거치지않는경우 : A k [i][j] 는 k 보다큰정점은통과하지않으므로최단거리는여전히 A k-1 [i][j]] 임 정점 k 를거치는경우 : i 에서 k 까지의최단거리 A k-1 [i][k] 에 k 에서 j 까지의최단거리 A k-1 [k][j] 를더한값 47

48 Floyd 의최단경로프로그램 int A[MAX_VERTICES][MAX_VERTICES]; void floyd(int n) { int i, j, k; for(i=0; i<n; i++) for(j=0; j<n; j++) A[i][j]=weight[i][j]; for(k=0; k<n; k++) for(i=0; i<n; i++) for(j=0; j<n; j++) if (A[i][k]+A[k][j] < A[i][j]) A[i][j] = A[i][k]+A[k][j]; } 48

49 Floyd 의최단경로알고리즘복잡도 네트워크에 n 개의정점이있다면, Floyd 의최단경로알고리즘은 3 중반복문을실행되므로시간복잡도는 O(n 3 ) 이된다 모든정점쌍의최단경로를구하려면 Dijkstra 의알고리즘 O(n 2 ) 을 n 번반복해도되며, 이경우전체복잡도는 O(n 3 ) 이된다 모든정점쌍의최단경로를구하는데있어두알고리즘모두동일한 O(n 3 ) 의복잡도를가지지만 Floyd 의알고리즘은매우간결한반복구문을사용하므로 Dijkstra 의알고리즘보다효율적이다 49

50 위상정렬 (topological sort) 방향그래프에서간선 <u, v> 가있다면정점 u 는정점 v 를선행함 방향그래프정점들의선행순서를위배하지않으면서모든정점을나열 선수과목은과목들의선행관계표현함 과목번호 과목명 선수과목 0 전산학개론 없음 1 이산수학 없음 2 자료구조 1 3 알고리즘분석 0, 1, 2 4 운영체제 1 5 인공지능 2, 3, 4 위상순서 (topological order) (0,1,2,3,4,5), (1,0,2,3,4,5) (2,0,1,3,4,5) 는위상순서가아님 왜냐하면 2 번정점이 0 번정점앞에오기때문 50

51 위상정렬알고리즘 Input: 그래프 G=(V,E) Output: 위상정렬순서 topo_sort(g) for i 0 to do if( 모든정점이선행정점을가지면 ) then 사이클이존재하고위상정렬불가 ; 선행정점을가지지않는정점 v 선택 ; v 를출력 ; v 와 v 에서나온모든간선들을그래프에서삭제 ; 51

52 52 위상정렬의예

슬라이드 1

슬라이드 1 CHAP 10: 그래프 C 로쉽게풀어쓴자료구조 생능출판사 2005 그래프 그래프 (graph): 연결되어있는객체간의관계를표현하는자료구조 그래프의예 : 전기회로, 프로젝트관리, 지도에서도시들의연결 그래프 : 아주일반적인자료구조 ( 예 ) 트리도그래프의일종으로볼수있다. 그래프이론 (graph theory): 그래프를문제해결의도구로이용하는연구분야 그래프역사 1800