1장. 리스트

Size: px

Start display at page:

Download "1장. 리스트"

다은 주
4 years ago
Views:

1 01. 그래프를소개합니다 02. 그래프를어떻게표현할것인가? 03. 그래프순회 : 그래프를따라산책하기 04. 최소신장트리 05. 최단경로탐색 06. 위상정렬

2 라인하르트오일러가 쾨니히스베르크의 7 개의다리문제 를풀기위해고안해낸수학적도구. 7 개의다리를간선 (Edge) 로, 4 개의육지를정점 (Vertex) 로표현. A A Pregel River B C B C D D

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

4 그래프는 정점의모음 과이정점을잇는 간선의모음 간의결합 정점의집합을 V, 간선의집합을 E, 그리고그래프를 G 라고했을때, G = (V, E) 이다. A B C + = A B C E D E D

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

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

7 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>}

8 인접 (Adjacent) 간선으로연결되어있는두정점을일컫는말 이웃관계 에있다고표현하기도함 정점의차수 (degree) 정점에연결되어있는간선의수 / 인접하는정점의수 A B C (A, B), (A, D), (A, E), (B, C), (B, E), (C, D) 가서로이웃관계 E D 경로 (Path) 위그래프에서정점 A 에서정점 C 까지의경로는 A-B-C 와 A-D- C, A-E-B-C 등이있다. 경로길이 경로를구성하는간선수 A-B-C, A-D-C 경로의길이는 2, A-E-B-C 의길이는 3

9 사이클 (cycle) 두정점간의경로에서동일한정점은두번이상거치는경로 앞의그래프에서 A-B-C-D-A 연결성 (connectivity) 무방향성그래프내에서두정점사이에경로가존재하는경우 두정점은연결되어있다. 완전그래프 그래프내의모든정점이서로연결되어있는그래프

10 객체 : 정점의집합과간선의집합 연산 : 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 연산을사용한다.

11 그래프는정점의집합과간선의집합의결합 그래프를표현하는문제는 정점의집합 과 간선의집합 의표현문제로생각할수있다. 간선은정점과정점이 인접 관계에있음을나타내는존재입니다. 이렇게따지면그래프의표현문제는 간선, 즉정점과정점의인접관계를어떻게나타내는가? 의문제로귀결 인접행렬 (Adjacency Matrix) 2 차원행렬사용 인접리스트 (Adjacency List) 연결리스트사용

12 인접행렬방법 if( 간선 (i, j) 가그래프에존재 ) M[i][j] = 1, 그렇지않으면 M[i][j] = 0.

13 인접행렬 (Adjacent Matrix) 정점끼리의인접관계를나타내는행렬 그래프의정점의수를 N 이라고한다면, 크기 N 의행렬을만들어행렬의각원소를한정점과또다른정점이인접해있는경우 ( 즉, 정점사이에간선이존재하는경우 ) 에는 1 로표시하고, 인접해있 지않은경우에는 0 으로표시

14 인접리스트방법 각정점에인접한정점들을연결리스트로표현

15 인접리스트 (Adjacency List) 그래프내의각정점의인접관계를표현하는리스트 2 3 정점인접정점 1 2, 3, 4, 5 2 1, 3, 5 3 1, 2 4 1, 5 5 1, 2,

16 어떻게하면아래의그래프에서모든정점을방문할수있을까?

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

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

19 깊이우선탐색 (Depth First Search) 더나아갈길이보이지않을때까지깊이들어간다. 1) 시작정점을밟은후이정점을 방문했음 으로표시합니다. 2) 그리고이정점과이웃하고있는정점 ( 즉, 인접정점 ) 중에아직방문하지않은곳을선택하여이를시작정점으로삼아다시깊이우선탐색을시작합니다. 그러니까단계 1) 을다시하는겁니다. 3) 정점에더이상방문하지않은인접정점이없으면이전정점으로돌아가서단계 2) 를수행합니다. 4) 이전정점으로돌아가도더이상방문할이웃이없다면그래프의모든정점을모두방문했다는뜻입니다. 이제탐색을종료합니다.

20 깊이우선탐색의예

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

22 // 인접행렬로표현된그래프에대한깊이우선탐색 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 새로시작

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

24 너비우선탐색 (Breadth First Search) 꼼꼼하게좌우를살피며다니자. 1) 시작정점을 방문했음 으로표시하고큐에삽입 (Enqueue) 합니다. 2) 큐로부터정점을제거 (Dequeue) 합니다. 제거한정점이이웃하고있는인접정점중아직방문하지않은곳들을 방문했음 으로표시하고큐에삽입합니다. 3) 큐가비게되면탐색이끝난것입니다. 따라서큐가빌때까지 2 의과정을반복합니다.

25 너비우선탐색의예 Queue Queue Queue Queue Queue 6 7

26 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); // 방문한정점을큐에저장 } } }

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

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

29 최소비용신장트리 (MST: minimu spanning tree) 네트워크에있는모든정점들을가장적은수의간선과비용으로연결하는신장트리 간선에 가중치 (Weight) 속성을부여, 각간선이갖고있는가중치의합이최소가되는신장트리 천 35 서울 원주 강릉 서울 천 대전 126 원주 전주 82 대전 전주 광주대구 117 강릉 대구 106 광주 106 부산 부산

30 MST 의응용 도로건설 - 도시들을모두연결하면서도로의길이가최소가되도록하는문제 전기회로 - 단자들을모두연결하면서전선의길이가가장최소가되도록하는문제 통신 - 전화선의길이가최소가되도록전화케이블망을구성하는문제 배관 - 파이프를모두연결하면서파이프의총길이가최소가되도록연결하는문제

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

32 크루스칼알고리즘 1) 그래프내의모든간선을가중치의오름차순으로목록을만듭니다. 2) 1) 에서만든간선의목록을차례대로순회하면서간선을최소신장트리에추가합니다. 단, 이때추가된간선으로인해최소신장트리내에사이클이형성되면안됩니다 예 : 간선의오름차순목록 A 247 E 98 H 35 B 126 C F G 106 I D A - B : 35 E - F : 82 E - H : 98 G - I : 106 C - D : 117 F - H : 120 B - C : 126 B - F : 150 F - G : 154 C - F : 162 C - G : 220 A - E : 247

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

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

36 크루스칼알고리즘의예 (1~4)

37 크루스칼알고리즘의예 (5~8)

38 프림알고리즘 (Prim s Algorithm) 1) 그래프와최소신장트리를준비합니다. 물론이때의최소신장트리는노드가하나도없는상태입니다. 2) 그래프에서임의의정점을시작정점으로선택하여최소신장트리의루트노드로삽입합니다. 3) 최소신장트리에삽입되어있는정점들과이정점들의모든인접정점사이에있는간선의가중치를조사합니다. 간선중에가장가중치가작은것을골라이간선에연결되어있는인접정점을최소신장트리에삽입합니다. 단, 새로삽입되는정점은최소신장트리에삽입되어있는기존의노드들과사이클을형성해서는안됩니다. 4) 3) 의과정을반복하다가최소신장트리가그래프의모든정점을연결하게되면알고리즘을종료합니다.

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

43 프림알고리즘의예 (9)

44 프림알고리즘의예 (1~4)

45 프림알고리즘의예 (5~8)

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

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

48 매단계에서새로운정점이 S 에추가되면 distance 값을갱신한다.

49 다익스트라알고리즘 1) 각정점위에시작점으로부터자신에게이르는경로의길이를저장할곳을준비하고모든정점위에있는경로의길이를 ( 무한대 ) 로초기화합니다. 2) 시작정점의경로길이를 0 으로초기화하고 ( 시작정점에서시작정점까지의거리는 0 이기때문 ) 최단경로에추가합니다. 3) 최단경로에새로추가된정점의인접정점들에대해경로길이를갱신하고이들을최단경로에추가합니다. 만약추가하려는인접정점이이미최단경로안에존재한다면갱신되기이전의경로길이가새로운경로의길이보다더큰경우에한해, 다른선행정점을지나던기존의경로를현재정점을경유하도록수정합니다. 4) 그래프내의모든정점이최단경로에소속될때까지 3) 과정을반복합니다.

50 // 입력 : 가중치그래프 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];

53 다익스트라알고리즘의예 I F B D 98 H 220 G C 247 A E I F B D 98 H 220 G C 247 A E I F B D 98 H 220 G C 247 A E I F B D 98 H 220 G C 247 A E I F B D 98 H 220 G C 247 A E I F B D 98 H 220 G C 247 A E

54 그래프에존재하는모든정점사이의최단경로를한번에모두찾아주는알고리즘알고리즘은 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 순으로최단거리를구한다.

55 먼저 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] 를더한값이될것이다.

56 위상정렬 (topological sort) 방향성그래프에서간선 <u, v> 가있다면정점 u 는정점 v 를선행한다고말한다. 방향성그래프에존재하는각정점들의선행순서를위배하지않으면서모든정점을나열하는것 과목번호과목명선수과목 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 번정점을시작할수있다.

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

59 깊이우선탐색을이용한위상정렬 1) 리스트를하나준비한다. 2) 그래프에서진입간선이없는정점대해깊이우선탐색을시행하고, 탐색중에더이상인접옮겨갈수있는인접정점이없는정점을만나면이정점을리스트의새로운 헤드 로입력한다. 3) 2) 를반복하다가더이상방문할정점이없으면깊이우선탐색을종료한다. 깊이우선탐색이끝난후리스트에는위상정렬된리스트가남는다.

60 깊이우선탐색을이용한위상정렬의예 F E C A B G D H H F E C A B G D H F H F E C A B G D H F H C F E C A B G D H F H C G F E C A B G D H F H C G D F E C A B G D H F H C G D A F E C A B G D H F H C G D A E F E C A B G D H F H C G D A E B

슬라이드 1

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