2020-1ํ•™๊ธฐ, ๋Œ€ํ•™์—์„œ โ€˜์•Œ๊ณ ๋ฆฌ์ฆ˜โ€™ ์ˆ˜์—…์„ ๋“ฃ๊ณ  ๊ณต๋ถ€ํ•œ ๋ฐ”๋ฅผ ์ •๋ฆฌํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค. ์ง€์ ์€ ์–ธ์ œ๋‚˜ ํ™˜์˜์ž…๋‹ˆ๋‹ค :)

7 minute read

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>ํ•œ๋‹ค.

์œ„์™€ ๊ฐ™์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋‘ ๊ฐ€์ง€ ์š”์†Œ๊ฐ€ ํ•„์š”ํ•˜๋‹ค.

  1. ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ๋ฅผ ๊ธฐ๋กํ•ด๋‘˜ ๊ฒƒ
  2. <ํ‡ด๊ฐ 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>์—์„œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค!

Categories:

Updated: