[Lecture Summary] 10 Algorithm and Data Structure : BFS & DFS

This contents is based on Lecture of link

Breadth-First Search

Overview

Compute level sets which a set of “iso-distant” vertices from source vertex. For unreachable vertex, distance is infinity. This requires Single Source Shortest Paths! It search for whole verices.

Moreover, we can generalize weight restriction into non-negative weights via expanding graph. We can interprete edge with weight n as a series of vertices with unweighted edge.

Algorithm

• Base case

$L_0$ = {$s$}, $P(s)=None$

• Iteration

$i \gets 1$
while $L_{i-1} \ne $ {},
$\forall u \in L_{i-1}, \forall v\in Adj(u)\backslash \cup_j L_j$
$add $v$ to $L_i$
$ \delta(s,v) = i$
$ P(v)=u$
$ i++$

Time analysis

• Time to access via edges and update parent : $O(\mid E \mid)$
• Time to access unreachable vertices and allocate distance as infinity : $O(\mid V \mid)$

As a result, it takes linear in input size!

Depth-First Search

Overview

Return path should not be the shortest path. But it does not revisit a vertex

Algorithm

$P(s)=None$ and then visit($s$)

def visit(parent $u$):

• for each $v \in Adj(u)$ and $parent(v)$ is None
  • parent(v) $\gets u$
  • visit($v$)

Correctness

DFS visit every vertices which is reachable from source $s$.

Time analysis

It requires only $O(\mid E \mid)$! No need to access every vertices. Only consider reachable verices.

Full search

repeat BFS or DFS util every vertex is visited! For Full-DFS, runing time is $O(\mid E \mid + \mid V \mid)$ because it visits every vertices.