[Algorithms] 3.2 Depth-first search in undirected graphs

해당 글은 Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani를 정리한 스터디 노트입니다.해석하면서 정리한 글입니다.

3.2 Depth-first search in undirected graphs

3.2.1 Exploring mazes

DFS(Depth-first-search)는 그래프에 대한 풍부한 정보를 보여주는 다재다능한 linear-time procedure 입니다.

가장 기본적인 문제는 주어진 vertex에서 그래프의 어느 부분에 도달할 수 있는가? 입니다.

Exploring mazes: 실뭉치와 분필
- 이미 방문한 곳을 분필로 표시합니다.(반복하는 것을 방지)
- 실뭉치를 이용해 원래 시작했던 곳으로 돌아오게끔 합니다.
Computer
- 각 vertex 마다 boolean 변수로 표시합니다.
- stack 구조의 2가지 연산을 통해 실뭉치 역할을 합니다.
  - 새로운 장소를 갈 때는 unwind
  - 이전의 장소를 갈 떄는 rewind
- stack 구조를 explicitly 이용하기 보단, recursion을 통해 implictly 알고리즘을 구현하는 것이 좋습니다.

Finding all nodes reachable from a particular node.

procedure explore(G,v)  
Input : G=(V,E) is a graph; v ∈ V  
Output : visited(u) is a set to true for all nodes u reachable from v  

visited(v) = true  
previsit(v)  
for each edge (v,u) ∈ E:  
 if not visited(u):	explore(u)  
postvisit(v)

previsit, postvisit은 선택 사항입니다.

previsit: 처음 발견된 vertex에 대해 연산 수행
postvisit: 마지막으로 떠날 때 해당 vertex에 대한 연산 수행

위에서 정의한 탐색 알고리즘 과정이 제대로 돌아갈까?

(pf.) 연결된 vertex 중에서 찾지 못한 vertex u가 있다고 가정합니다.

v에서 u로 가는 path P를 하나 선택합니다.
탐색 알고리즘에 대해 마지막으로 탐색된 vertex를 z로 생각합니다.
Path P상에서 u로 가는 방향의 z 이웃 노드인 w가 있다고 가정합니다.
즉, z는 탐색했지만, w는 탐색을 하지않습니다.(모순)
z에서 탐색과정을 통해 w로 향했기 때문입니다.

3.2.2 Depth-first search

탐색 절차는 시작점에서 도달할 수 있는 그래프 portion만 방문합니다.
그래프의 나머지 부분을 검토하려면, 아직 방문하지 않은 다른 vertex에서 절차를 다시 시작해야 합니다.

깊이우선검색 알고리즘은 전체 그래프를 통과할 때까지 반복해서 이 작업을 수행합니다.

깊이 우선 탐색(DFS)

procedure dfs(G)

for all v ∈ V:
  visited(v) = false

for all v ∈ V:
  if not visited(v): explore(v)

DFS 알고리즘 실행시간 분석 1) 고정된 양의 작업(visited라고 표시함, 혹은 pre/postvisit)

각 노드마다 마킹작업 수행합니다.
총 연산량 $O(\vert V \vert))$

2) 안가본 곳으로 향하기 위해, 인접 엣지들을 탐색하는 루프(loop)

$e$ = {$x,y$} 이므로 각 노드마다 엣지를 탐색 해줍니다.
엣지마다 2번씩 탐색합니다.
총 연산량 $O(\vert E \vert)$

3) 따라서, DFS는 $O(\vert V \vert+\vert E \vert)$ :

그래프의 input 값인 $V$와 $E$에 대한 linear time이 됩니다.

3.2.3 Connectivity in undirected graphs

connected graph
- 어떤 undirected graph가 연결되었다는 것은 어떤 노드들을 잡아도 path가 존재한다는 뜻입니다.
connected components
- 각각의 component가 subgraph가 됩니다.
- subgraph란, internally connected & no edges to the remaining nodes.
특정 노드에 대한 탐색알고리즘은 그 노드가 포함된 connected component 하나를 알아내는 것입니다.
- DFS를 통해, 그래프가 연결되어 있는지 검토할 수 있습니다.
- 하나의 노드에 숫자를 부여해서 포함된 connected component를 식별할 수 있습니다.

procedure previsit(v)
ccnum[v] = cc

cc를 0으로 초기화 해주며, DFS 과정에서 explore가 호출될 때마다 +1을 증가시켜 줍니다.

3.2.4 Previsit and postvisit orderings

저희는 앞서 깊이 우선 탐색이 undirected graph의 연결 구조를 linear time내에 알아낼 수 있는 방법을 확인했습니다.
다시 말해, DFS는 undirected graph의 연결구조를 linear time 내에 찾는 방법이라 할 수 있습니다.

그리고 이를 더 확장하기 위해, 각 노드마다 두개의 중요한 이벤트 때 시간을 메모하는 등 좀 더 많은 정보를 수집할 것 입니다.

해당 노드를 첫 번째로 발견할 경우 previsit
마지막으로 떠날 경우 postvisit

procedure previsit(v)
pre[v] = clock
clock = clock + 1 

procedrue postvisit(v)
post[v] = clock
clock = clock + 1

Property 어떤 노드 u와 v에 대해, 각각의 구간 [$pre(u), post(u)$]와 [$pre(u), post(u)$]는 서로 dispoint 이거나 포함관계 입니다.

Why? stack 구조는 last-in, first-out(후입선출)으로 동작하므로, 노드 u가 스택에 있는 동안의 시간흐름을 구간으로 생각할 수 있습니다.

Reference

Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani