Chap 6: Graphs

Size: px

Start display at page:

Download "Chap 6: Graphs"

대건 강
4 years ago
Views:

1 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page )

2 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v] = 무방향성그래프 : A[][] 는대칭행렬 방향성그래프 : A[][] 는비대칭행렬 대칭행렬 : A[n(n-)/] 로구현가능 6 장. 그래프 (Page )

3 인접리스트 (Adjacency List) 인접행렬의 n 행들을 n 개의연결리스트로표현 즉, 그래프 G 의각 vertex 에대해한개의연결리스트가존재 headnodes vertex link null null null null null null null 6 장. 그래프 (Page )

4 인접다중리스트 (Adjacency Multilist) Edge 별로하나의노드를할당 각 edge 를검사했다는표시를나타내는데용이 marked vertex vertex path path headnodes N N N4 N N N4 N null N5 edge(, ) edge(, ) edge(, ) N4 N5 N6 edge(, ) The lists are: vertex : N N N vertex : N N4 N5 vertex : N N4 N6 vertex : N N5 N6 N5 null N6 N6 null null edge(, ) edge(, ) 6 장. 그래프 (Page 4)

5 그래프표현방법들의분석 G 에존재하는 edge 수? 혹은 G 가연결되었는지검사. 인접행렬 : n(n )/ 개의항을조사 O(n ) 인접리스트 : O(n+e) Good if e << n / (sparse graphs) Digraph 에서 vertex 의 in-degree 를조사 인접행렬 : O(n) 인접리스트 : O(n+e) 역인접리스트 (inverse adjacency list) 를별도유지 in-degree 와 out-degree 를모두표현할수있는인접리스트구조를구현 ( 그림 6.) tail head column link for head row link for tail null null null 6 장. 그래프 (Page 5)

6 Orthogonal Representation of G Headnodes (shown twice) row column NULL NULL NULL NULL NULL NULL tail head 6 장. 그래프 (Page 6)

7 . 기초적인그래프연산들. 깊이우선탐색 (Depth First Search). 너비우선탐색 (Breadth First Search). 연결요소 (Connected Components) 4. 신장트리 (Spanning Trees) 5. 이중결합요소와단절점 (Biconnected Components and Articulation Points) 6 장. 그래프 (Page 7)

8 . Depth First Search 알고리즘 출발 vertex, v 의인접리스트부터방문 v 에인접하면서아직방문하지않은 vertex, w 를선택 w 를시작점으로하여다시깊이우선탐색시작 recursion 을이용하여구현 #define FALSE #define TRUE short int visited[max_vertices]; void dfs(int v) { struct node *w; visited[v] = TRUE; printf("%5d", v); for (w = graph[v]; w; w = w link) if (!visited[w vertex]) dfs(w vertex); } 6 장. 그래프 (Page 8)

9 Depth First Search 의동작과정 struct node *graph[]; struct node { int vertex; struct node *link}; V null 4 null V V 5 6 null V V 4 V 5 V V null depth first search order : v, v, v, v 7, v 4, v 5, v, v 6 6 장. 그래프 (Page 9)

10 . Breadth First Search 알고리즘 출발 vertex, v 의인접리스트부터방문 v 에인접한모든 vertex 들을먼저방문 그다음, v 에인접한첫번째 vertex 에인접한 vertex 중에서아직방문하지않은 vertex 들을다시차례대로방문 (Queue 를이용 ) struct queue { int vertex; struct queue *link; }; void addq(.); int deleteq(.); 6 장. 그래프 (Page )

11 Program 6.: Breadth First Search void bfs(int v) { // Vertex v부터탐색수행. visited[] 배열은 FALSE로초기화. 큐를사용 node_pointer w; struct queue *front = NULL, *rear = NULL; printf("%5d", v); visited[v] = TRUE; addq(&front, &rear, v); while (front) { v = deleteq(&front); for (w = graph[v]; w; w = w link) if (!visited[w vertex]) { printf("%5d", w vertex); addq(&front, &rear, w vertex); visited[w vertex] = TRUE; } } } 6 장. 그래프 (Page )

12 Breadth First Search 의동작과정 V V V V V 4 V 5 V 6 V null null 6 null 5 6 null breadth first search order : v, v, v, v, v 4, v 5, v 6, v 7 6 장. 그래프 (Page )

13 . Connected Components 무방향성그래프가연결되어있는지검사? dfs() 나 bfs() 를호출한후, 방문되지않은 vertex 가존재하는지를검사 그래프의 connected component 들을출력? void connected (void) { /* determine the connected components of a graph */ int i for (i = ; i < n; i++) if (!visited[i]) { dfs(i); printf("\ n"); } } 6 장. 그래프 (Page )

14 .4 Spanning Trees 정의 그래프 G 에포함된 edge 들로구성되며, G 의모든 vertex 들을포함하는트리 DFS 나 BFS 를이용하여 spanning tree 구성 Depth first spanning tree Breadth first spanning tree V V V V V V V V 4 V 5 V 6 V V 4 V 5 V 6 V 7 depth first spanning tree V 7 breadth first spanning tree 6 장. 그래프 (Page 4)

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

Microsoft PowerPoint - 제10장-그래프.pptx 제 강의. 그래프개념과그래프탐색 학습목차. 그래프의개념. 그래프의표현. 그래프탐색 . 그래프의개념 graph? chart? 오래된그래프문제로다음과 Köenigsberg 다리문제가있다. 이문제는다음과같은지형이있을때임의의한곳 (A,B,C,D) 에서출발하여 a 부터 f 까지 모든다리를한번씩건널수있는가? 하는문제이다. 자료구조의그래프는이러한문제를컴퓨터에표현하고알고리즘을개발하는분야이다.