[Algorithm Part 2] 1. Undirected Graph

이번 글에서는, 3가지 graph-processing algorithm(search, path, connectivity)에 대해 살펴볼 것이다.

Why learning graph-processsing algorithm(s)?

그래프는 "광범위하게 사용되는 추상화(=abstraction) 모델"이다.

(매우) 복잡한 구조를 가진 수 많은 객체(e.g., Internet, Seoul Metro)를 그래프로 추출(=abstract)할 수 있다.

 

그래프로 추상화되는 객체가 갖고 있는 problem(s)를 graph-processing problem(s)라 하며,

graph-processing problem(s)의 algorithm(s)을 graph-processing algorithm(s)이라고 한다.

 

graph-processing algrithm(s)은 객체의 문제를 품으로써, 객체의 특성을 파악하는데 많은 도움을 준다.

결론, graph-processing algorithm(s)의 공부 이유는 "복잡한 구조를 가진 객체의 특성, 패턴 or 성질을 이해하기 위함"이다.

---

Graph

Definition

Graph is set of vertices connected pairwise by edges. (only connection)

Terminology

Path: sequence of vertices connected by edges

Cycle: path whose first and last vertrices are the same

 

두 vertex사이에 경로가 있으면, 두 vertex는 "연결되어 있음"을 의미한다.

---

Graph representation

1. adjancey-matrix graph: 크기가 $V^2$인 배열에 egde 연결 여부를 표현한다.
   dense graph일 때 유리하다. (e.g., adj[v][w] = adj[w][v] = true, if v-w exists)
2. adjancey-list graph: 각 vertex마다 adjacent vertices(=인접 정점) 리스트를 유지한다.
   sparse graph일 때 유리하다. (e.g., adj[v].append(w), adj[w].append(v), if v-w exists)

대부분의 graph가 sparse하기에, adjancey-list graph 방법을 많이 사용한다.

Performance

representation	space	add edge	search edge v-w	iterate vertices adjacent to v
list of edges	E	1	E	E
adjacency matrix	$V^2$	1	1	V
adjacency lists	E + V	1	degree(v)	degree(v)

---

Design pattern

graph-processing problem의 알고리즘을 구현할 때,

Graph class와 분리된 독립적인 class 또는 function(=module)으로 구현해야 한다.

다시 말해, graph class를 parameter로 받는 class 또는 function 형식으로 만들어야 한다.

수많은 graph-processing algorithm을 graph class에 집어 넣으면,

매우 크고 복잡한 interface 즉, fat interface가 되기 때문이다.

---

1. Graph search 

그래프 탐색은 source vertex(=s)와 연결된 모든 vertices(=v)를 찾는 문제다.

그래프 탐색 알고리즘에는 대표적으로 1). depth-first search 2). breadth-first search가 있다.

1.1. Depth-First Search

깊이 우선 탐색(=depth-first search)은 stack(or 재귀)을 통해 깊이를 우선적으로 탐색하는 알고리즘이다.

(e.g., 미로 경로 찾기)

Algorithm

1. stack에 source vertex(=s)를 push한다.
2. stack이 빌 때까지 다음 과정을 반복한다.
   1. stack에서 v를 pop한 후, 방문한다. (e.g., visited[v] = True)
   2. 방문하지 않은 v의 인접 정점(=w)을 모두 찾아 stack에 push한다.

재귀

1. v를 방문한다. (e.g., marked[v] = True)
2. 방문하지 않은 v의 모든 인접 정점(=w)을 찾은 후, 재귀로 방문한다.

---

1.2. Breadth-First Search

너비 우선 탐색(=breadth-first search)는 queue를 사용해 너비를 우선적으로 탐색하는 알고리즘이다.

(e.g., 최소 경로 찾기)

Algorithm

1. source vertex(=s)를 방문한 후(e.g., visited[s] = True), queue에 push한다.
2. queue가 빌 때까지 다음 과정을 반복한다.
   1. queue에서 v를 pop한 후, 방문하지 않은 v의 인접 정점(=w)를 모두 찾는다.
   2. 모든 w를 방문하고(e.g., visited[w] = True), queue에 w를 push한다.

---

Performance

algorithm	graph search
depth-first search	V + E
breadth-first search	V + E

---

2. Path

경로 탐색은 source vertex(=s)와 연결된 모든 vertices(=v)의 경로를 찾는 문제다.

 

그래프 탐색 알고리즘을 활용하면 문제를 쉽게 풀 수 있다.

s(root)에서 모든 v까지의 경로 정보를 트리(edgeTo[])에 저장해 문제를 푼다.

(edgeTo[v]에 v의 부모 노드를 저장하는 배열로 트리를 표현한다.)

(v에서 s까지의) 경로는 (v에서 s까지의) 트리 경로로 쉽게 알 수 있다.

Algorithm

• 정점 s를 시작으로 그래프 탐색을 한다. (by dfs, bfs)
• 탐색 도중 정점(w=방문하지 않은 v의 인접 정점)을 방문하면,
  정점 w의 부모 노드를 v로 할당한다. (e.g., edgeTo[w] = v)

Property

미로 찾기 문제일 경우 dfs을 사용하고, 최소 경로 문제일 때는 bfs를 사용한다.

Performance

	construct edgeTo	has path	get path
breadth-first search	V + E	1	len(path)

---

3. Connected Components

connectivity query는 서로 다른 vertices의 연결 여부를 물어보는 문제다.

 

union-find로 풀 수 있지만,

그래프 탐색 알고리즘을 사용하면 보다 빠르게(by constant time) 문제를 풀 수 있다.

정점 간의 연결성 정보를 저장한 배열(id[])을 구축해 문제를 푼다.

(id[v] == id[w]인 경우, 두 vertices가 같은 CC(=connected component)에 속함을 의미한다.)

Algorithm

모든 vertex(=v)를 순회하면서, 방문 여부를 확인한다. v를 방문하지 않았으면,

1. 정점 v를 시작으로 그래프 탐색을 한다. (by dfs, bfs)
   탐색 도중 정점(w=방문하지 않은 v의 인접 정점)을 방문하면,
   고유 "CC 식별자"를 할당한다. (e.g., id[w] = count)
2. 다음 CC와 식별하기 위해, 식별자를 변경한다. (e.g., count++)

Performance

	construct id	connectivity query	# of connected vertex	get identifier
CC	V + E	1	1	1