슬라이드 1

Size: px

Start display at page:

Download "슬라이드 1"

우성 송
5 years ago
Views:

1 CHAP 10: 그래프 C 로쉽게풀어쓴자료구조 생능출판사 2005

2 그래프 그래프 (graph): 연결되어있는객체간의관계를표현하는자료구조 그래프의예 : 전기회로, 프로젝트관리, 지도에서도시들의연결 그래프 : 아주일반적인자료구조 ( 예 ) 트리도그래프의일종으로볼수있다. 그래프이론 (graph theory): 그래프를문제해결의도구로이용하는연구분야

3 그래프역사 1800 년대오일러에의하여창안 오일러문제 : 모든다리를한번만건너서처음출발했던장소로돌아오는문제 문제의핵심만을표현 위치 : 정점 (node) 다리 : 간선 (edge) 오일러경로 : 정점에연결된간선의개수가짝수이면존재

4 그래프용어 그래프는 (V, E) 로표시된다. V 는정점 (vertices) 들의집합 E 는간선 (edge) 들의집합 정점과간선은모두관련되는데이터를가질수있다. ( 예 ) 예제그래프 정점은각도시를의미한다. 간선은도시를연결하는도로를의미한다. 간선에는도로의길이등의데이터가저장될수있다.

5 그래프의종류 간선의종류에따라그래프는무방향그래프 (undirected graph) 와방향그래프 (directed graph) 로구분 무방향간선 : 간선을통해서양방향으로갈수있음을나타내며 (A, B) 와같이정점의쌍으로표현 (A, B) = (B, A) A 방향간선 : 방향성이존재하는간선으로도로의일방통행길과마찬가지로한쪽방향으로만갈수있음을나타낸다. <A, B> 로표시한다. <A, B> <B, A> B A 가중치그래프 (weighted graph), 네트워크 (network): 간선에비용이나가중치가할당된그래프 B A 1200 B

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(G2)= {0, 1, 2}, E(G2)= {<0, 1>, <1, 0>, <1, 2>}

7 그래프용어 인접정점 (adjacent vertex) 란간선에의해연결된정점 정점 0 와정점 1 차수 (degree) 는그정점에연결된다른정점의개수 정점 0 의차수는 3 경로 (path) 는정점의나열로표현 단순경로 : 0, 1, 2, 3 사이클 (cycle): 0, 1, 2, 0 경로의길이 : 경로를구성하는데사용된간선의수 완전그래프 : 모든정점이연결되어있는그래프

8 그래프 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 연산을사용한다.

9 그래프표현방법 그래프를표현하는 2 가지방법 인접행렬 (adjacent matrix): 2차원배열사용표현 인접리스트 (adjacency list): 연결리스트를사용표현 인접행렬방법 if( 간선 (i, j) 가그래프에존재 ) M[i][j] = 1, 그렇지않으면 M[i][j] = 0.

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

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

12 그래프탐색 (cont.) 그래프탐색의 2 가지방법 깊이우선탐색 (DFS: depth-first search) 너비우선탐색 (BFS: breadth-first search) 깊이우선탐색은미로를탐색할때한방향으로갈수있을때까지계속가다가더이상갈수없게되면다시가장가까운갈림길로돌아와서이곳으로부터다른방향으로다시탐색을진행하는방법과유사하다.

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

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

15 너비우선탐색 (BFS) 너비우선탐색은시작정점으로부터가까운정점을먼저방문하고멀리떨어져있는정점을나중에방문하는순회방법 큐를사용하여구현됨

16 BFS 알고리즘 readth_first_search(v) v 를방문되었다고표시 ; 큐 Q 에정점 v 를삽입 ; while (not is_empty(q)) do Q 에서정점 w 를삭제 ; for all u (w 에인접한정점 ) do if (u 가아직방문되지않았으면 ) then u 를큐에삽입 ; u 를방문되었다고표시 ; 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); // 방문한정점을큐에저장 } } }

$visited[i]=count; void find_connected_component(graphtype *g) { int i; } count = 0; for(i=0;$

17 연결성분찾기 최대로연결된부분그래프들을찾는것 그래프탐색으로찾을수있다. visited[i]=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); }

18 신장트리 신장트리 (spanning tree): 그래프내의모든정점을포함하는트리 신장트리는모든정점들이연결되어있어야하고또한사이클을포함해서는안된다.

19 신장트리알고리즘 depth_first_search(v) v 를방문되었다고표시 ; for all u (v 에인접한정점 ) do if (u 가아직방문되지않았으면 ) then (v,u) 를신장트리간선이라고표시 ; depth_first_search(u) 신장트리의용도 통신네트워크구축 : 최소의링크를사용하여네트워크를구축하고싶은경우

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

21 MST 알고리즘 2 가지의대표적인알고리즘 Kruskal 의알고리즘 Prim 의알고리즘 탐욕적인방법 (greedy method) 알고리즘설계에서있어서중요한기법중의하나 결정을해야할때마다그순간에가장좋다고생각되는것을해답으로선택함으로써최종적인해답에도달 탐욕적인방법은항상최적의해답을주는지를반드시검증해야한다. Kruskal 의알고리즘은최적의해답을주는것으로증명

22 Kruskal 의 MST 알고리즘 최소비용신장트리가최소비용의간선으로구성됨과동시에사이클을포함하지않는다는조건에근거하여, 각단계에서사이클을이루지않는최소비용간선을선택 그래프의간선들을가중치의오름차순으로정렬한다. 정렬된간선들의리스트에서사이클을형성하지않는간선을찾아서현재의최소비용신장트리의집합에추가한다. 만약사이클을형성하면그간선은제외된다.

24 kruskal 의 MST 알고리즘의구현 union-find 알고리즘 집합들의합집합을구하고집합의원소가어떤집합에속하는지를계산하는알고리즘 여러가지방법으로구현이가능하다 Kruskal의 MST 알고리즘에서사이클검사에사용된다. a 와 b 가같은집합에속함 a 와 b 가다른집합에속함

25 Prim 의 MST 알고리즘 Prim 의알고리즘은시작정점에서부터출발하여신장트리집합을단계적으로확장해나가는방법 시작단계에서는시작정점만이신장트리집합에포함 앞단계에서만들어진신장트리집합에, 인접한정점들중에서최저간선으로연결된정점을선택하여트리를확장 이과정은트리가 n-1 개의간선을가질때까지계속된다. 간선 (a, b) 와간선 (f, e) 의가중치를비교해보면 (f, e) 가 27 로서 (a, b) 의 29 보다높다. 따라서 (f, e) 간선이선택되고정점 e 가신장트리집합에포함된다.

26 Prim 의 MST 알고리즘

27 Prim 의 MST 알고리즘

28 Prim 의 MST 알고리즘

29 최단경로알고리즘 최단경로 (shortest path) 문제는네트워크에서정점 i 와정점 j 를연결하는경로중에서간선들의가중치합이최소가되는경로를찾는문제 간선의가중치는비용, 거리, 시간등을나타낸다.

30 Dijkstra 의최단경로알고리즘 Dijkstra 의최단경로알고리즘은네트워크에서하나의시작정점으로부터모든다른정점까지의최단경로를찾는알고리즘 집합 S: 시작정점 v 로부터의최단경로가이미발견된정점들의집합 distance 배열 : 최단경로를알려진정점만을통하여각정점까지가는최단경로의길이 매단계에서가장 distance 값이적은정점을 S 에추가한다.

31 Dijkstra 의최단경로알고리즘 매단계에서새로운정점이 S 에추가되면 distance 값을갱신한다.

32 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];

33 Dijkstra 의최단경로알고리즘

34 Dijkstra 의최단경로알고리즘

35 Floyd 최단경로알고리즘 Floyd 의최단경로알고리즘은그래프에존재하는모든정점사이의최단경로를한번에모두찾아주는알고리즘이다. Floyd 의최단경로알고리즘은 2 차원배열 A 를이용하여 3 중반복을하는루프로구성 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]) 위의알고리즘을설명하기위하여 A k [i][j] 를 0 부터 k 까지의정점만을이용한정점 i 에서 j 까지의최단경로라고하자. 우리가원하는답은 A n-1 [i][j] 가된다. A -1 A 0 A 1 A n-1 순으로최단거리를구한다.

36 Floyd 최단경로알고리즘 먼저 A k-1 까지는완벽한최단거리가구해져서있다고가정하자. 일반적으로 k 번째정점이추가로고려되는상황을생각하여보자. 0 부터 k 까지의정점만을사용하여정점 i 에서정점 j 로가는최단경로는다음의 2 가지의경우로나누어서생각할수있다. (1) 정점 k 를거쳐서가지않는경우 : 는 k 보다큰정점은통과하지않으므로이경우최단거리는 A k-1 [i][j] 가된다. (2) 정점 k 를통과하는경우 : 이경우 i 에서 k 까지의최단거리 A k-1 [i][k] 에다가 k 에서 j 까지의최단거리인 A k-1 [k][j] 를더한값이될것이다.

위상정렬 위상정렬 (topological sort): 방향그래프에서간선 <u, v> 가있다면정점 u 는정점 v 를선행한다고말한다. 방향그래프에존재하는각정점들의선행순서를위배하지않으면서모든정점을나열하는것을방향그래프의위상정렬 (topological sort) 이라고한다.

37 위상정렬 위상정렬 (topological sort): 방향그래프에서간선 <u, v> 가있다면정점 u 는정점 v 를선행한다고말한다. 방향그래프에존재하는각정점들의선행순서를위배하지않으면서모든정점을나열하는것을방향그래프의위상정렬 (topological sort) 이라고한다. 과목번호과목명선수과목 0 전산학개론없음 1 이산수학없음 2 자료구조 1 3 알고리즘분석 0, 1, 2 4 운영체제 1 5 인공지능 2, 3, 4 위상정렬 : (0,1,2,3,4,5), (1,0,2,3,4,5) (2,0,1,3,4,5) 는위상정렬이아니다. 왜냐하면 2 번정점이 0 번정점앞에오기때문이다. 간선 <0, 2> 이존재하기때문에 0 번정점이끝나야만이 2 번정점을시작할수있다.

38 위상정렬

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

1장. 리스트

1장. 리스트 01. 그래프를소개합니다 02. 그래프를어떻게표현할것인가? 03. 그래프순회 : 그래프를따라산책하기 04. 최소신장트리 05. 최단경로탐색 06. 위상정렬 라인하르트오일러가 쾨니히스베르크의 7 개의다리문제 를풀기위해고안해낸수학적도구. 7 개의다리를간선 (Edge) 로, 4 개의육지를정점 (Vertex) 로표현. A A Pregel River B C B C D