Whatever-First Search, Depth-first search, Breadth-first search topological sort

May 18, 2023

When studying certain properties of graphs, one general concept is to consider the $\mathbf{\text{reachability}}$ problem. Given a graph $G=(V,E)$ and an additional vertex $s\in V$, we want to know which vertices are reachable from $s$. We want to find the vertices where there is a path from $s$ to $v$ $(s\to v)$. One natural tool in any computer science student’s toolbox is the $\mathbf{\text{depth-first search}}$ algorithm. Two forms of methods can be constructed: recursively or iteratively. Either method works; under the hood, it doesn’t really matter. Just go with whatever you’re more comfortable with.

Depth-first search

Here is the recursive pseudocode for DFS

Algorithm 1 Recursice depth-first search

procedure RecursiveDFS($v$)

if $v\text{is unmarked}$ then

mark $v$

for $\text{each edge}v\to w$ do

RecursiveDFS($w$)

end for

end if

end procedure

Here is the iterative pseudocode for DFS

Algorithm 2 Iterative depth-first search

procedure IterativeDFS($s$)

Push($s$)

while the stack is not empty do

$v\leftarrow$ Pop

if $v$ is unmarked then

mark $v$

for each edge $v\to w$ do

Push($w$)

end for

end if

end while

end procedure

Given the description and algortihm for depth-first search we can turn to what we used through out the class for most graph problems is $\mathbf{\text{whatever-first search}}$. Where instead of stacks and queues it uses a more general data structure called a $\mathbf{\text{bag}}$.

The algorithm provided by Jeff in his algorithm textbook is as follows:

Algorithm 3 Whatever-first search

procedure WhateverFirstSearch($s$)

put $s$ into the bag

while the bag is not empty do

take $v$ from the bag

if $v$ is unmarked then

mark $v$

for each edge $v\to w$ do

put $w$ into the bag

end for

end if

end while

end procedure

Looking back to $\mathbf{\text{depth-first search}}$ on graphs that are directed the implenatation can be done by modifying $\mathbf{\text{whatever-first search}}$ to use a stack

Algorithm 4 Depth-first search

procedure DFS($v$)

if $v$ is unmarked then

mark $v$

for each edge $v\to w$ do

DFS($w$)

end for

end if

end procedure

One natural question is to consider how every vertex is being marked and ask ourselves could we do better and not mark vertices that have been marked already. But we also would like to consider other useful information that we could possibly obtain when traversing the vertices and edges in a black-box subroutine that for now is left without clarificaiton.

Algorithm 5 Depth-first search

procedure DFS($v$)

mark $v$

PreVisit$\left(v\right)$

for each edge $v\to w$ do

if $w$ is unmarked then

$parent\left(w\right)\leftarrow v$

DFS($w$)

end if

end for

PostVisit$\left(v\right)$

end procedure

We know that any node $v$ is able to reach $w$ if and only if there is a path from $v$ to $w$ in a directed graph. We can create a subroutine $\mathbf{\text{reach(v)}}$ that returns a set of all vertices reachable from $v$ and $v$ itself included. Given a graph $G=(V,E)$ with all unmarked vertices and calling DFS$(v)$ then the set of all marked vertices would be exactly the reach$(v)$

We can also extend the reachability algorithm to be able to trevaserse the entire graph even if the entire graph is not fully connected.

Algorithm 6 Depth-first search

procedure DFSAll($G$)

Preprocess$\left(G\right)$

for all vertices $v$ do

unmark $v$

end for

for all vertices $v$ do

if $v$ is unmarked then

DFS($v$)

end if

end for

end procedure

Alternatively we could also define it as follows if we are allowed to modify the graph.

Algorithm 7 Depth-first search

procedure DFSAll($G$)

Preprocess$\left(G\right)$

add vertex $s$

for all vertices $v$ do

add edge $s\to v$

unmark $v$

end for

DFS($s$)

end procedure

When considering the input graph $G$ we should consider wether it is directed or unidrected because in each case the algorithm would give us different results.

DFS (Intro to Algorithms 4th ed.)

Algorithm 8 DFS

procedure DFS($G$)

for each vertex $u\in G.V$ do

$u$.color = white

$u.\pi$ = NIL

end for

time = $0$

for each vertex $u\in G.V$ do

if $u$.color == white then

DFS-Visit($(G,u)$)

end if

end for

end procedure

Algorithm 9 DFS-Visit

procedure DFS-Visit($G,u$)

time = time + 1

$u.d=$ time

$u$.color = gray

for each vertex $v$ in $G.Adj\left[u\right]$ do

if $v$.color == white then

$u.\pi =u$

DFS-Visit($(G,v)$)

end if

end for

time = time + 1

$u.f=$ time

$u.$color = black

end procedure

Preorder and Postorder

Recollecting $\mathbf{\text{Preorder}}$ and $\mathbf{\text{Postorder}}$ of rooted trees. If we have a tree noted as $T$ and subtress as $T_1,...,T_k$ and whose root is label $r$ the two methods are described as follows

$\mathbf{\text{Preorder}}$: We visit the root $r$, and then recursively do a preorder traversal of $T_1,...T_k$
$\mathbf{\text{Postorder}}$ We first recursively perform a postorder traversal of the $T_1,...,T_k$ subtrees and then visit the root $r$.

Algorithm 10 Preorder

procedure PreOrder($v$)

if $v\notin V$ then

return

end if

Visit$\left(v\right)$

PreOder($v.left$)

PreOder($v.right$)

end procedure

Algorithm 11 Postorder

procedure PostOrder($v$)

if $v\notin V$ then

return

end if

Postorder($v.left$)

Postorder($v.right$)

Visit$\left(v\right)$

end procedure

Breadth-first search

The representation of the algorithm is provided by Introduction to Algortihms Fourth Edition textbook.

Algorithm 12 Breadth-first search

procedure BreadthFirstSearch($G,s$)

for each vertex $u\in G.V-\left\{s\right\}$ do

$u$.color = White

$u.d=\infty$

$u.\pi =$ NIL

end for

$s$.color = Gray

$s.d$ = 0

$s.\pi =$ NIL

$Q=\varnothing$

Enqueue$(Q,s)$

while $Q\ne \varnothing$ do

$u=$ Dequeue$\left(Q\right)$

for each vertex $v$ in $G.Adj\left[u\right]$ do

if $v.$color == White then

$v.$color = Gray

$v.d=u.d+1$

$v.\pi =u$

Enqueue$(Q,v)$

end if

end for

$u.$color = Black

end while

end procedure

One thing we might wanna do is view the path created by BFS on a given source vertex $s$. Since the path forms a breadth-first tree and a shortest path for all such paths in $G_{\pi }$ for $\pi$.

Algorithm 13 Print-Path

procedure Print-Path($G,s,v$)

if $v==s$ then

print $s$

else if $v.\pi ==$ NIL then

print no path from $s$ to $v$ exists

else

Print-Path($G,s,v.\pi$)

print $v$

end if

end procedure

Topological sort

Topological sort (Intro to Algorithms 4th ed.)

Algorithm 14 Topological sort

procedure Topological-Sort($G$)

call DFS$\left(G\right)$ to compute finish times $v.f$ for each vertex $v$

as each vertex is finished, insert it onto the front of a linked list

return the linked list of vertices

end procedure