그래프표현법 인접행렬 (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] = 무방향성그래프 : A[][] 는대칭행렬 방향성그래프 : A[][] 는비대칭행렬 대칭행렬 : A[n(n-)/] 로구현가능 6 장. 그래프 (Page )
인접리스트 (Adjacency List) 인접행렬의 n 행들을 n 개의연결리스트로표현 즉, 그래프 G 의각 vertex 에대해한개의연결리스트가존재 headnodes vertex link null null null null null null null 6 장. 그래프 (Page )
인접다중리스트 (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)
그래프표현방법들의분석 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)
Orthogonal Representation of G Headnodes (shown twice) row column NULL NULL NULL NULL NULL NULL tail head 6 장. 그래프 (Page 6)
. 기초적인그래프연산들. 깊이우선탐색 (Depth First Search). 너비우선탐색 (Breadth First Search). 연결요소 (Connected Components) 4. 신장트리 (Spanning Trees) 5. 이중결합요소와단절점 (Biconnected Components and Articulation Points) 6 장. 그래프 (Page 7)
. 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)
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 6 4 5 V 7 6 7 4 5 6 null depth first search order : v, v, v, v 7, v 4, v 5, v, v 6 6 장. 그래프 (Page 9)
. 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 )
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 )
Breadth First Search 의동작과정 V V V V V 4 V 5 V 6 V 7 4 5 6 7 null 5 4 4 null 6 null 5 6 null breadth first search order : v, v, v, v, v 4, v 5, v 6, v 7 6 장. 그래프 (Page )
. 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 )
.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)