DFS and BFS
2020-1ํ๊ธฐ, ๋ํ์์ โ์๊ณ ๋ฆฌ์ฆโ ์์ ์ ๋ฃ๊ณ ๊ณต๋ถํ ๋ฐ๋ฅผ ์ ๋ฆฌํ ๊ธ์ ๋๋ค. ์ง์ ์ ์ธ์ ๋ ํ์์ ๋๋ค :)
Definition. connected
An undirected graph is <connected> if for every pair of nodes $u$ and $v$, there is a path between $u$ and $v$.
์ด๋ฒ ํฌ์คํธ๋ฅผ ๊ดํตํ๋ ๊ฐ์ฅ ์ค์ํ ์ฃผ์ ๋ ๋ฐ๋ก ์ด๊ฒ์ด๋ค.
How to determine that a given vertex $s$ is reachable?
DFS
<DFS> ์๊ณ ๋ฆฌ์ฆ์ <๊ทธ๋ํ ํ์>์ ๊ฐ์ฅ ๊ธฐ์ด๊ฐ ๋๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. <DFS>์ ์์ด๋์ด๋ ๋ ธ๋ $s$์์ ์์ํด ์ธ์ ํ ๋ ธ๋๋ค๋ถํฐ ํ์ํ๋๋ฐ, ์ด๋์ ํ์์ <terminal node>๋ฅผ ๋ง๋๊ฑฐ๋ ์ด๋ฏธ ๋ฐฉ๋ฌธํ <explored node>๋ฅผ ๋ง๋๊ธฐ ์ ๊น์ง ํ ๋ฐฉํฅ์ผ๋ก ๊ณ์ ๋๋ค. ๋ง์ฝ <terminal node>๋ <explored node>๋ฅผ ๋ง๋๋ค๋ฉด, ๋ฐ๋ก ์ง์ ์ ๋ฐฉ๋ฌธํ ๋ ธ๋๋ก <ํด๊ฐ Retract>ํ๋ค.
์์ ๊ฐ์ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ๊ธฐ ์ํด์๋ ๋ ๊ฐ์ง ์์๊ฐ ํ์ํ๋ค.
- ๋ฐฉ๋ฌธํ ๋ ธ๋๋ฅผ ๊ธฐ๋กํด๋ ๊ฒ
- <ํด๊ฐ Retract> ํ๊ธฐ ์ํด ๋ฐฉ๋ฌธ ์์๋ฅผ ๊ธฐ์ตํ ๊ฒ
<DFS>๋ <๋ฏธ๋ก ํ์>๋ฅผ ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฝ๋-๋ ๋ฒจ๋ก ๊ทธ๋๋ก ์ฎ๊ธด ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์์ ํ ์ธ์ฐ์ค๊ฐ ์๋ฆฌ์๋๋ค๋ฅผ ๊ตฌํ๊ธฐ ์ํด ๋ฏธ๋ ธํ์ฐ๋ฅด์ค์ ๋ฏธ๋ก์์ ๋ฐ์ผ๋ก ๋น ์ ธ๋์ฌ ๋, ์ค๊ณผ ์กฐ์ฝ๋์ ์ด์ฉํด ๋ฏธ๋ก๋ฅผ ํด๋งค์ง ์์ ์ ์์๋ค!! ๋ถ๊ธฐ์ ์ ๋ง๋ฌ์ ๋ ์กฐ์ฝ๋๋ก ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ํ์ํ๊ณ , ํด๊ฐ ์กฐ๊ฑด์์ ์ค์ ๊ฐ์์ ๋ฐ๋ก ์ง์ ์ ๋ถ๊ธฐ์ ์ผ๋ก ๋์๊ฐ๋ฉด ๋ฏธ๋ก์์ ๊ธธ์ ์์ง ์๊ธฐ ๋๋ฌธ์ด๋ค!! ๐คฉ
<DFS>๋ฅผ ์๋ ์ฝ๋๋ก ํํํ๋ฉด ์๋์ ๊ฐ๋ค.
function: explore($G$, $v$)
Input: $G=(V, E)$ is a graph; $v \in V$
Output: for all nodes $u$ reachable from $v$, visited($u$) is set to $true$.
visited($v$) = $true$
for each edge $(v, u) \in E$ do
โโ if not visited($u$) then
โโ โโ expolore($G$, $u$)
โโ end if
end for
ํ์ง๋ง <DFS> ์๊ณ ๋ฆฌ์ฆ์ด ์ ๋ง๋ก $v$์์ reachableํ ๋ชจ๋ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ค๊ณ ์ด๋ป๊ฒ ๋ณด์ฅํ ์ ์์๊น? โ<DFS> ์๊ณ ๋ฆฌ์ฆ์ ์์ ๋ ธ๋ $v$์์ ๋๋ฌํ ์ ์๋ ๋ชจ๋ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ค.โ๋ ๋ช ์ ๋ฅผ ์ฆ๋ช ํด๋ณด์!
Assume $u$ is reachable from $v$ but explore misses $u$. (๊ท๋ฅ๋ฒ)
Let $\pi$ be any path from $v$ to $u$, and let $z \in \pi$ be the last vertex visited by explore.
Let $w$ be the node immediately after $z$ on path $\pi$.
When $z$ was visited, the procedure would have noticed $w$ and moved on to it.
$z$์ ๋ฐฉ๋ฌธํ์ผ๋ฉด, explore ํจ์์์ ์ธ์ ํ ๋ชจ๋ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๊ธฐ ๋๋ฌธ์ ๋ฐ๋์ $w$๋ ๋ฐฉ๋ฌธํ ์ ๋ฐ์ ์๋ค.
ํ์ง๋ง explore์์ $w$๋ฅผ ๋ฐฉ๋ฌธํ๋ค๋ฉด, ์ด๋ ์ฒ์์ ๊ฐ์ ํ $z$๊ฐ explore์์ ๋ฐฉ๋ฌธํ ๊ฐ์ฅ ๋ง์ง๋ง ๋ ธ๋๋ผ๋ ๊ฒ์ ๋ชจ์์ด๋ค.
๋ฐ๋ผ์ ์ฒ์์ ๊ฐ์ ํ reachableํ $u$๋ฅผ ํ์ํ์ง ๋ชป ํ๋ค๋ ๋ช ์ ๋ ๊ฑฐ์ง์ด๋ค. $\blacksquare$
์ด๋ฒ์๋ <DFS> ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ณ์ฐํด๋ณด์! ๊ทธ๋ํ๋ฅผ <์ธ์ ํ๋ ฌ>๊ณผ <์ธ์ ๋ฆฌ์คํธ>๋ก ํํํ๋๋์ ๋ฐ๋ผ์ ์๊ฐ ๋ณต์ก๋๊ฐ ๋ค๋ฅธ๋ฐ, ๋ณธ์ธ์ด ์ฃผ๋ก <์ธ์ ๋ฆฌ์คํธ> ๋ฐฉ์์ผ๋ก ๊ทธ๋ํ๋ฅผ ์๊ฐํ๊ธฐ ๋๋ฌธ์ ์ฌ๊ธฐ์๋ <์ธ์ ๋ฆฌ์คํธ>์ ๊ฒฝ์ฐ๋ฅผ ์ดํด๋ณด๊ฒ ๋ค.
๊ทธ๋ํ $G=(V, E)$์ ๋ํด ๋ชจ๋ ์ ์ ์ ๋ฐฉ๋ฌธํ๋ค๊ณ ํ๋ฉด, explore๋ ์ด $V$๋ฒ ํธ์ถ๋๋ค. ์ด๋, ๊ฐ explore์์ ๋ ธ๋ $v$์ $\deg$ ๋งํผ for ๋ฌธ์ ๋๋ฆฌ๋ฏ๋ก <DFS> ์๊ณ ๋ฆฌ์ฆ์ด ์ข ๋ฃ๋ ์์ ์์ ๋ณด๋ฉด, $\displaystyle \sum_{v} \deg(v)$ ๋งํผ iteration์ ์ํํ ๊ฒ์ด ๋๋ค. ์ด๋, $\displaystyle \sum_{v} \deg(v) = 2 \times E$์ด๋ค.
๋ฐ๋ผ์ ์ ์ฒด ์๊ฐ๋ณต์ก๋๋
\[O(V + 2E) = O(V + E)\]$\blacksquare$
BFS
<BFS> ์๊ณ ๋ฆฌ์ฆ๋ <DFS> ์๊ณ ๋ฆฌ์ฆ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก ๋ ธ๋ $s$๊ฐ reachable ํ์ง๋ฅผ ํ๋จํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ํ์ง๋ง, <BFS>์ ๊ฒฝ์ฐ reachable ํ๋จ ์์ ๋ณด๋ค๋ ๋ ธ๋ $s$๋ถํฐ์ <๊ฑฐ๋ฆฌ distance>๋ฅผ ์ฌ๋ ๋ฐ์ ํ์ํ ์๊ณ ๋ฆฌ์ฆ์ด๋ค!!
<BFS>์ ์ปจ์ ์ โlayer by layerโ๋ค. ์์ ๋ ธ๋ $s$๋ก๋ถํฐ ์ธ์ ํ ๋ชจ๋ ๋ ธ๋๋ฅผ ์ดํผ๊ณ ; 1st layer, ๊ทธ๋ฆฌ๊ณ ๊ทธ 1st layer์ ๋ ธ๋๋ค๋ก๋ถํฐ ์ธ์ ํ์ง๋ง ๋ฐฉ๋ฌธํ์ง ์์ ๋ค๋ฅธ ๋ชจ๋ ๋ ธ๋๋ฅผ ์ดํผ๊ณ ; 2nd layer, โฆ ๋์ด์ ๋ฐฉ๋ฌธํ ๋ ธ๋๊ฐ ์์ ๋๊น์ง ์ด ๋ฐฉ์์ผ๋ก ๋ชจ๋ ๋ ธ๋๋ฅผ ์ํํ๋ค. ์ด์ ๊ฐ ๋ ธ๋๊ฐ ๋ช๋ฒ์งธ layer์ ์ํด์๋์ง๋ฅผ ํตํด $s$๋ก๋ถํฐ์ <๊ฑฐ๋ฆฌ>๋ฅผ ์ธก์ ํ ์ ์๋ค!! ์ด๋ป๊ฒ ๋ณด๋ฉด, ์ด์ฐ ์์ญ์์ <interest circle>์ ๋ฐ์ง๋ฆ์ 1์ฉ ๋ค๋ฆฌ๋ฉฐ ๊ฑฐ๋ฆฌ๋ฅผ ์ธก์ ํด๊ฐ๋ ๊ณผ์ ์ฒ๋ผ ๋ณด์ด๊ธฐ๋ ํ๋ค.
<BFS>๋ฅผ ์๋ ์ฝ๋๋ก ํํํ๋ฉด ์๋์ ๊ฐ๋ค.
function: bfs($G$, $s$)
Input: $G=(V, E)$ is a graph; $s \in V$
Output: for all nodes $u$ reachable from $s$, $\textsf{dist}(u)$ = distance from $s$ to $u$.
for asll $u \in V$ do
โโ $\textsf{dist}(u) = \infty$
end for
$\textsf{dist}(s) = 0$
$Q = [s]$ (queue containing start node $s$)
while $Q$ is not empty do
โโ $u=Q.\textsf{pop}()$
โโ for all edges $(u, v) \in E$ do
โโ โโ if $\textsf{dist}(v) = \infty$ then
โโ โโ โโ $Q.\textsf{push}(v)$
โโ โโ โโ $\textsf{dist}(v) = \textsf{dist}(u) + 1$
โโ โโ end if
โโ end for
end while
<BFS> ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋๋ $V$๊ฐ ๋งํผ์ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๊ณ , ๊ฐ ๋ ธ๋์ ๋ํด์ ๋ชจ๋ ์ธ์ ํ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๊ธฐ ๋๋ฌธ์, <DFS> ์๊ณ ๋ฆฌ์ฆ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก $O(V + E)$์ด๋ค.
<\DFS>, <BFS> ์๊ณ ๋ฆฌ์ฆ์ ๊ทธ๋ํ ์๋ฃํ์ ๋ค๋ฃจ๋๋ฐ ๊ธฐ์ด๊ฐ ๋๋ค. ์ฌ์ค ์ธ๊ฐ์ด ์๊ฐํ๋ ๋ฐฉ์์ ๊ทธ๋๋ก ์ฎ๊ธด ์๊ณ ๋ฆฌ์ฆ์ด๋ผ ๊ทธ๋ ๊ฒ ์ด๋ ต์ง ์๋ค ใ ใ ๐
๋ณธ ํฌ์คํธ์์ ์ฐ๊ด๋๋ ๋ด์ฉ์ ์๋์ ๊ฐ๋ค.
1. DFS & BFS - code ๐ป
์๊ณ ๋ฆฌ์ฆ์ ์ดํดํ๋ ๊ฒ๋ ์ค์ํ์ง๋ง, ๊ทธ๊ฒ์ ์ฝ๋๋ก ๊ตฌํํ๋ ๊ฒ ์ญ์ ์ค์ํ๋ค! ๋ณธ์ธ์ <DFS>, <BFS> ์ฝ๋ ์คํ์ผ์ ์๋์ ๋งํฌ์์ ๋ณผ ์ ์๋ค.
๐ DFS & BFS - code
2. DFS Tree ๐ฒ
<DFS> ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ๊ทธ๋ํ๋ฅผ ์ํํ๋ฉด ๋ฐฉ๋ฌธ ์์๋ฅผ ๋ฐํ์ผ๋ก <Tree> ๊ตฌ์กฐ๋ฅผ ๋ง๋ค ์ ์๋ค!! ์ด <DFS Tree>๋ ๋์ค์ <DAG; Directed Acyclic Graph>๋ฅผ ํ๋จํ๋ ๋ฌธ์ ์๋ ์ฐ๊ด๋๋ค.
๐ DFS Tree
3. Dijkstra Algorithm ๐
<BFS> ์๊ณ ๋ฆฌ์ฆ์ ํตํด ๋ ธ๋์ ๋ ธ๋ ์ฌ์ด์ ๊ฑฐ๋ฆฌ๋ฅผ ์ธก์ ํ ์ ์๊ฒ ๋์๋ค. ํ์ง๋ง, edge ์ฌ์ด์ weight ๊ฐ์ด ๋ถ์ฌ๋์ด ์๋ค๋ฉด, <BFS>๋ก ๊ตฌํ ๊ฑฐ๋ฆฌ๊ฐ ๋ ธ๋์ ๋ ธ๋ ์ฌ์ด์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ ์๋๋ค. <Dijkstra Algorithm>์ <Weighted Graph>์์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค!