인접 리스트(Adjacency List)

그래프 표현법

 인접 행렬(Adjacency Matrix)

 인접 리스트(Adjacency List)

 인접 다중 리스트(Adjacency Multilist)

인접 행렬(Adjacency Matrix)

 n개의 vertex를 갖는 그래프 G의 인접 행렬의 구성



A[n][n]

 (u, v) ∈ E(G) 이면, A[u][v] = 1

 Otherwise, A[u][v] = 0

 무방향성 그래프: A[][]는 대칭 행렬

 방향성 그래프: A[][]는 비대칭 행렬

0 1 2 3 0 0 1 1 1 1 1 0 1 1 2 1 1 0 1 3 1 1 1 0

0 1 2 0 0 1 0 1 1 0 1 2 0 0 0 0

1

2 0

3

2 1

대칭 행렬:

A[n(n-1)/2]로 구현 가능

인접 리스트(Adjacency List)

 인접 행렬의 n 행들을 n개의 연결 리스트로 표현

 즉, 그래프 G의 각 vertex에 대해 한 개의 연결 리스트 가 존재

0 1 2 3

1

3 null 0

0 0

2

1 3 null

headnodes vertex link

3 null 2

2 null 1

0 1 2

0 2 null

1 null

null 0

1 0

3

2 1

인접 다중 리스트(Adjacency Multilist)

 Edge별로 하나의 노드를 할당

 각 edge를 검사했다는 표시를 나타내는데 용이

marked vertex1 vertex2 path1 path2

The lists are: vertex 0 : N1  N2  N3 vertex 1 : N1  N4  N5 vertex 2 : N2  N4  N6 vertex 3 : N3  N5  N6

edge(0, 1) N1 0 1 N2 N4

edge(0, 2) N2 0 2 N3 N4

edge(0, 3) N3 0 3 null N5

edge(1, 2) N4 1 2 N5 N6

edge(1, 3) N5 1 3 null N6

edge(2, 3) N6 2 3 null null

headnodes 0

1 2 3 0

3

2 1

그래프 표현 방법들의 분석

 G에 존재하는 edge 수? 혹은 G가 연결되었는지 검사.

 인접 행렬: n(n–1)/2 개의 항을 조사  O(n²

)

 인접 리스트: O(n+e)

 Good if e << n²/2 (sparse graphs)

 Digraph에서 vertex의 in-degree를 조사

 인접 행렬: O(n)

 인접 리스트: O(n+e)

 역인접 리스트(inverse adjacency list)를 별도 유지

 in-degree와 out-degree를 모두 표현할 수 있는 인 접 리스트 구조를 구현(그림 6.11)

0 1 2

0 null 1 null

1 null

tail head column link for head row link for tail

Orthogonal Representation of G ₃

0 1 2

1 0

1 2 2

1 0

0 1

NULL

NULL NULL

NULL NULL NULL

Headnodes (shown twice) row

column

tail head

2. 기초적인 그래프 연산들

1. 깊이 우선 탐색(Depth First Search) 2. 너비 우선 탐색(Breadth First Search) 3. 연결 요소(Connected Components) 4. 신장 트리(Spanning Trees)

5. 이중 결합 요소와 단절점(Biconnected Components and Articulation Points)

2.1 Depth First Search

 알고리즘

 출발 vertex, v의 인접 리스트부터 방문

 v에 인접하면서 아직 방문하지 않은 vertex, w를 선택

 w를 시작점으로 하여 다시 깊이 우선 탐색 시작

 recursion을 이용하여 구현

#define FALSE 0

#define TRUE 1

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);

}

Depth First Search의 동작 과정

V₀

V₁ V₂

V₃ V₄ V₅ V₆ V₇

0 1 2 3 4 5 6 7

1

4 null 0

0 1 1 2 2 3

2 null 3

5

7 null 7 null 7 null 7 null 4

6 null

5 6 null

depth first search order : v₀

, v

, v

, v

, v

, v

, v

, v

struct node *graph[];

struct node

{ int vertex; struct node *link};

2.2 Breadth First Search

 알고리즘

 출발 vertex, v의 인접 리스트부터 방문

 v에 인접한 모든 vertex들을 먼저 방문

 그 다음, v에 인접한 첫번째 vertex에 인접한 vertex중 에서 아직 방문하지 않은 vertex들을 다시 차례대로 방 문 (Queue를 이용)

struct queue {

int vertex;

struct queue *link;

};

void addq(….);

int deleteq(….);

Program 6.2: 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;

Breadth First Search의 동작 과정

V₀

V₁ V₂

V₃ V₄ V₅ V₆ V₇

0 1 2 3 4 5 6 7

1

4 null 0

0 1 1 2 2 3

2 null 3

5

7 null 7 null 7 null 7 null 4

6 null

5 6 null

breadth first search order : v₀

, v

, v

, v

, v

, v

, v

, v

2.3 Connected Components

 무방향성 그래프가 연결되어 있는지 검사?

 dfs(0)나 bfs(0)를 호출한 후, 방문되지 않은 vertex가 존재하는지를 검사

 그래프의 connected component들을 출력?

void connected (void) {

/* determine the connected components of a graph */

int i

for (i = 0; i < n; i++) if (!visited[i]) {

dfs(i); printf("\ n");

}

2.4 Spanning Trees

 정의

 그래프 G에 포함된 edge들로 구성되며, G의 모든 vertex들을 포함하는 트리

 DFS나 BFS를 이용하여 spanning tree 구성



Depth first spanning tree



Breadth first spanning tree

depth first spanning tree breadth first spanning tree

V₀

V₁ V₂ V₃ V₄ V₅ V₆

V₇

V₀

V₁ V₂ V₃ V₄ V₅ V₆

V₇