Microsoft PowerPoint - 제10장-그래프.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - 제10장-그래프.pptx"

설아 호
5 years ago
Views:

1 제 강의. 그래프개념과그래프탐색 학습목차. 그래프의개념. 그래프의표현. 그래프탐색

2 . 그래프의개념 graph? chart?

3 오래된그래프문제로다음과 Köenigsberg 다리문제가있다. 이문제는다음과같은지형이있을때임의의한곳 (A,B,C,D) 에서출발하여 a 부터 f 까지 모든다리를한번씩건널수있는가? 하는문제이다. 자료구조의그래프는이러한문제를컴퓨터에표현하고알고리즘을개발하는분야이다. c C d g a A Kneiphof B e b f D c A a C B d e g b f D Königsberg 다리문제

4 . 그래프의개념 그래프의수학적정의 그래프 : G = (V,E) 이고, V,E는다음과같다. V(G) : 정점 (set of vertices) E(G) : 간선 (set of edges), 정점을연결하는선, V X V의부분집합 무방향그래프 (undirected graph) 예를들면쌍방통행이가능한도로의지도이다. - 정점을연결하는선에방향이없다 (undirected, unordered). 즉 (v i,v j ) = (v j,v i ) 이다. 방향그래프 (directed graph) 예를들면일방통행만있는도로의지도이다. - 정점을연결하는선에방향이있다 (directed, ordered). 즉 <v i,v j > <v j,v i > 4

5 그래프의예와수학적인표현 : 그래프를표현하는방법은여러가지이다. 아래방법은그림으로그리는그래프의모습과수학적인기호로표현하는방법이다 G G 예) 그래프의수학적인표현 그래프 G V(G) = {,,,} E(G) = {(,),(,),(,),(,),(,),(,)} 그래프 G V(G) = {,,,,4,5,6} E(G) = {(,),(,),(,),(,4),(,5),(,6)} 그래프 G V(G) = {,,} E(G) = {<,>,<,>,<,>} G 5

6 4 H G4 H 예) 두개의연결된부분을가진그래프그래프 G4 V(G4) = {,,,,4,5,6,7} E(G4) = {(,),(,),(,),(,),(,), (,),(4,5),(5,6),(6,7)} 6

7 그래프에서의제한사항 ) 자기자신을향하는간선은없다.(no self loop) no edge from a vertex, i, back to itself, no (vi,vi) or <vj,vi> ) 중복된간선을허용하지않는다.(not multigraph) no multiple occurrences of the same edge (a) (b) 그래프의제한사항의예 a) self loops, b) multigraph 7

8 그래프에관한용어들 () 완전그래프 (complete graph) - 그래프에서간선의수가최대인그래프를말한다. 정점이 개인그래프는간선의최대갯수가 개, 정점이 4개인그래프는간선의최대개수는 6개이다. 정점이 n개면? 계산을해보자. * 무방향그래프경우 n 개의정점이있는경우간선의수가 n(n-)/ * 방향그래프경우 n 개의정점이있는경우간선의수가 n(n-) () 인접 (adjacent) - 무방향그래프에서정점 a, b에대하여간선 (a,b) 가있으면, 정점 a 는정점 b에인접 (adjacent) 하다고한다. () 부속 (incident) - 무방향그래프에서정점 a, b에대하여간선 (a,b) 가있으면, 간선 (a,b) 는정점 a와정점 b에부속 (incident) 한다고한다. 8

9 예 ) 무방향그래프의 (v,v) : 무방향간선 -정점v과 v 은인접 (adjacent) 하다. -간선(v,v) 은정점v와 v 에부속 (incident) 된다. 예 ) 방향그래프 <v,v> : 방향간선 -정점v는정점v 에인접 (adjacent) 하다. -정점v은정점v로부터인접 (adjacent) 하다. -간선 <v,v> 은정점v와 v 에부속 (incident) 된다. 9

10 (4) 부분그래프 (subgraph) G of G : -V(G ) V(G) and -E(G ) E(G) (a) 그래프 G의부분그래프의예 (i) (ii) (iii) (iv) G (b) 그래프 G 의부분그래프들 G (i) (ii) (iii) (iv)

11 그래프에관한용어들 (5) 경로 (path) : 정점 vp 에서정점 vq 으로가는경로 - 정점의연속인 vp, v, v, v,, vn, vq 가다음과같은간선이존재할때정점vp 에서정점 vq으로가는경로가있다고한다. (vp,vi)), (v,v),,(vn,vq) - 무방향그래프에서다음의간선들이존재한다. <vp,v>, <v,v>,,<vn,vq> (6) 경로의길이 : 경로상에있는간선의수 -(vp,vi),(vi,vi),,(vin,vq) 경로의경우 n+ 이된다. (7) 단순경로 (simple path) - 처음과마지막을제외하고정점이모두다른경로, 즉경로상의정점이중복되지않는경로를단순경로라고한다. (8) 사이클 (cycle) - 처음과마지막정점이같은단순경로, 즉단순경로중경로가다시원점에도달하는경우이며사이클을형성한다. - 방향성그래프에서는방향성사이클 (directed cycle) 이라한다. (9) 연결됨 (connected) -정점v와정점v이연결되있다는것은그래프 G에서정점 v에서정점 v 로가는경로가있는경우이다. 지도로말하면통행로가있는경우이다.

12 그래프에관한용어들 () 연결된부분 (connected component) - 부분그래프에서최대로연결된그래프, 즉그래프에서모든정점이연결되지않을수있다. 이경우최대로연결된부분그래프를 connected component 라고한다. (maximal connected subgraph) 4 H G4 두개의연결된부분을가진그래프 () 트리 (tree) - 트리를그래프로정의할수있다. 사이클이없으며연결된그래프로루트노드가 개존재하는그래프를트리라고한다. 트리는그래프의일종이다. H

13 그래프에관한용어들 () 강연결과강연결요소 ( strongly connected, strongly connected component in a directed graph) - 강연결 : 정점의쌍 vi, vj in V(G) 에대하여 vi to vj 그리고 vj to vi 경로가존재할때즉정점의상대방으로가는경로가모두존재할때강연결되있다고한다. - 강연결요소 (strongly connected component in a directed graph) 강연결된최대부분그래프, 정점의모든쌍 vi, vj in V(G) 에대하여 vi to vj 그리고 vj to vi 경로가존재하는연결된부분요소이다.(maximal subgraph that is strongly connected) 4 강연결된그래프 G 의강연결요소 (strongly connected components) () 차수 (degree of vertex) - 정점에부속된 (incident) 간선의수 - in-degree (of vertex v) : 정점에들어오는간선의수 - out-degree (of vertex v) : 정점으로부터나가는간선의수

14 Q/A 그래프에대하여답하여라 () Vertex와 edge의수는몇개인가? () 그래프를수학적인표기법으로적어라. () 5번노드에인접한노드는? (4) 6번에서 번으로가는최단경로의길이는? 4

15 . 그래프의표현 () 인접행렬 (adjacency matrix) - 그래프 G = (V,E), V = n( ) 일때그래프를이차원행렬에다음과같이저장하는방법이다. adj_mat[i][j] = : if (vi, vj) 가인접할때 (adjacent) : 인접하지않을경우 - 필요한기억장소의크기 = 공간복잡도 (space complexity) : S(n) = n - 무방향그래프에서는행렬이대각선을중심으로대칭 (symmetric) 이다. G G 인접행렬로표현된그래프 G, G, and G4 G4 4 H H

16 () 인접리스트 (adjacency lists) n 개의연결리스트로그래프를표현한다. 그래프의각정점에대하여정점과연결된간선을한개의연결리스트에저장한다. 전체연결리스트는 n 개가되며이연결리스트를배열로표현한다. #define MAX_VERTICES 5 struct list_node { int vertex; struct list_node * link; }; typedef struct list_node node; typedef node * node_ptr; node_ptr graph[max_vertex]; vertex link 노드의자료구조 6

17 graph vertex link G 인접리스트로표현된 G G 인접리스트로표현된 G H H 인접리스트로표현된 G4 7

18 () 인접리스트 (adjacency lists) 참고 : 역 (inverse) 인접리스트 G G의역인접리스트 참고 : 차원직교표현 연결리스트를이차원으로표현한다. tail head column link for head row link for tail 헤드노드 (headnodes) 그래프 G 의직교표현 8

19 참고 : 가중치간선 (weighted edges) - 그래프의간선에가중치 (weights) 를부여할수있다. 가중치의의미는다음이다. ) 정점에서정점으로가는거리혹은 ) 정점에서정점까지의도달하는비용 - 인접행렬이나인접리스트에가중치를부여하여표현한다. 9

20 Q/A 그래프에대하여답하여라 () 그래프를인접행렬로나타내어라 () 그래프를인접리스트로나타내어라

21 . 그래프탐색 그래프자료구조와연산모델 : 그래프를표현하고그래프에관한연산을구현한다. 그래프자료구조연산 읽기 검사 삽입삭제 traversal ( ) insert ( ) delete ( ) isempty ( ) isfull( ) 그래프자료구조 = 그래프자료선언 + 그래프연산그래프자료구조는자료의선언과자료에대한연산으로구성된다. 그래프자료의선언과저장은인접행렬이나인접리스트로표현한다. 그래프연산은자료의탐색 (traversal) 과갱신에관한연산으로이루어진다. 탐색은원하는노드를 개혹은일부를찾는작업이다. 갱신은정점과간선의삽입 (insert), 삭제 (delete), 수정을말한다.

22 그래프탐색 (graph traversals) - 그래프의각정점을방문하는것을탐색 (traversal) 이라고한다. - 그래프에관한연산중가장중요한것이다. - 탐색에서노드의방문순서에따라다음과같은방법이있다. 깊이우선탐색 DFS (Depth First Search) 갈수있는데까지가보는방문방법 -트리의전위탐색방법을그래프에적용한것이다. (preorder tree traversal) 너비우선탐색 BFS (Breath First Search) 거리가가까운곳부터가보는방문방법 - 트리의레벨우선탐색을그래프에적용한것이다. (level order tree traversal)

23 . 그래프탐색 V (a) 그래프 G V V V V 4 V 5 V V (b) 그래프 G와인접리스트 (adjacency lists)

24 () 그래프탐색 - 깊이우선탐색 (depth first search) 방법 : 자동차로여행할경우방문지가있으면무조건방문하는방법이다. 즉후진하지않고가는방법이며후진하는경우는길이막히거나, 이미방문했던곳일경우이다. 후진하여방문할곳은마지막에갈수있었던곳중가지않았던길이다. 이방법을깊이우선탐색이라고하며탐색중방문가능한곳은스택자료를이용하여저장해둔다. 단계 : 하나의노드를택한다. 단계 : 노드를방문하여필요한작업을한다음연결된다음노드를찾는다. 현재방문노드는스택에저장한다. 단계를반복하면서방문을계속한다. 막히면 단계로간다. 단계 : 더이상방문할노드가없으면스택에서노드를빼내다음방문노드를찾아 ) 번과정을다시반복한다. 특징 : - 스택을이용한다. - visited[max_vertices] 배열을사용하여방문했던것을표시한다. 초기값은 FALSE 이고방문하면 TRUE #define FALSE #define TRUE short int visited[max_vertices]; 4

25 () 그래프탐색 - 깊이우선탐색 (depth first search) 깊이우선탐색의예 V V V 8 V V 4 7 V 5 5 V V 7 배열 visited : 방문 5: 되돌아옴 방문할곳이여러곳일때노드번호가작은쪽방문 V V 7 V 7 V 7 V 4 V V V V V V V V V V V V V V 스택의변화 5

26 깊이우선탐색알고리즘 (depth first search) /* 깊이우선탐색알고리즘 (depth first search) */ /* 정점 v에서시작하여그래프의깊이우선방문 */ void dfs(int v) { node_ptr w; visited[v] = TRUE; /* 방문지표시 */ printf( %5d, v); for(w = graph[v]; w; w = w->link) /* 연결리스트탐색 */ if(!visited[w->vertex]) dfs(w->vertex); } * 깊이우선탐색알고리즘 (depth first search) 의시간복잡도 -> 시간복잡도 (time complexity) : O(e), e 는간선의수 6

27 () 그래프탐색 - 너비우선탐색 (breadth first search) 방법 : 자동차로여행할경우가까운곳부터방문하는방법이다. 즉어느지점에서가까운곳을방문하고다음방문가능지점은모두저장해둔다. 다음방문지는항상저장해둔곳에서순서대로꺼낸다. 예를들어종로 가에서시작하여종로의버스정류장을모두방문해야한다고하면종로 가의한정류장거리를다방문하고끝나면두정류장거리에있는정류장을모두방문하고이러한순서로진행한다. 두정류장거리에있는정류장들은첫번째정류장을방문할경우기억을해둔다. 먼저기억된정류장이다음번에먼저방문을하게된다. 즉큐자료구조를이용하여다음방문지를선택한다. 단계 : 하나의노드를택한다. 단계 : 노드를방문하여필요한작업을한다음연결된다음노드를찾는다. 노드들을큐에저장한다. 더이상방문할곳이없으면 단계로간다. 단계 : 큐의맨앞의노드를빼내 단계를반복한다. 특징 : - 큐를이용한다. - visited[max_vertices] 배열을사용하여방문했던것을표시한다. 초기값은 FALSE 이고방문하면 TRUE #define FALSE #define TRUE short int visited[max_vertices]; 7

28 너비우선탐색 (breadth first search) 예제 너비우선탐색의예 V 배열 visited V V V V 4 V 5 V V : 방문 방문할곳이여러곳일때노드번호가작은쪽방문 8

29 너비우선탐색의예 큐의모양 V V V V V V V V 4 V V 4 V 5 V 6 V V 4 V 5 V 4 V 5 V 6 V 7 V 5 V 6 V 7 V 6 V 7 V 6 V 7 V 7 9

30 /* 너비우선탐색알고리즘 (breadth first search) */ /* 정점 v에서시작하여그래프의너비우선방문 */ void bfs(int v) { node_ptr w; queue_ptr front, rear; front = rear = NULL;/* initialize queue */ 너비우선탐색알고리즘 (breadth first search) */ } printf( %5d, v); visited[v] = TRUE; /* 방문지기록 */ insert(&front, &rear, v); while(front) /* 방문지있는동안반복 */ { v = delete(&front); for(w = graph[v]; w; w = w->link; if(!visited[w->vertex]) { printf( %5d, w->vertex); insert(&front, &rear, w->vertex); visited[w->vertex] = TRUE; } }

31 () 연결요소의계산 - bfs(), dfs() 를이용하여그래프의어느한노드에서연결되는모든노드를구하는연결요소 (connected components) 을구한다. - 알고리즘 dfs() or bfs() 를호출하여구한다. - dfs() 나 bfs() 는경로가있는노드들만을탐색한다. void connected(void) { 연결요소의계산 /* 그래프의연결요소를출력한다 */ int i; for(i = ; i < n; i++) { if(!visited[i]) { dfs(i); printf( n );} } } 그래프 G4 에알고리즘을적용하면결과는 줄이된다. 즉 개의연결요소를찾는다. ( 결과 )

32 학습내용정리 그래프는지도상의최단경로찾기등의문제를해결하는데사용이된다. 그래프자료구조는그래프를컴퓨터에표현하고그래프에관한알고리즘을개발하는기초이다. 그래프는정점 (node) 과간선 (edge) 의집합으로구성이된다. 간선이방향을갖는지여부에따라무방향그래프와방향그래프로구분한다. 그래프에관한용어로는경로, 사이클, 연결요소등이있다. 그래프를컴퓨터에저장하는방법은인접행렬과인접리스트가있다. 인접행렬은행렬로표현하는방법이며인접리스트는연결리스트를이용한방법이다. 인접행렬은표현하기쉽지만기억장소의낭비가많기때문에잘사용되지않는다. 연결리스트는복잡하기는하지만큰그래프를표현할수있는방법이다. 그래프에관한연산은트리와마찬가지로탐색이가장중요하며탐색방법은깊이우선탐색과너비우선탐색의두가지방법이있다. 두방법모두순환알고리즘을이용하여작성하며이미배운스택과큐자료구조를이용하게된다.

Chap 6: Graphs

Chap 6: Graphs 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page ) 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v]