Comment on page

# 23.1 BFS & DFS

Professor Hug's Lecture on Graphs

In Chapter 22.4, we developed DFS (Depth First Search) Traversal for graphs. In DFS, we visit down the entire lineage of our first child before we even begin to look at our second child - we literally search

**.***depth first*Here, we will talk about BFS (Breadth First Search) (also known as Level Order Traversal). In BFS, we visit all of our immediate children before continuing on to any of our grandchildren. In other words, we visit all nodes 1 edges from our source. Then, all nodes 2 edges from our source, etc.

The pseudocode for BFS is as follows:

Initialize the fringe, an empty queue

add the starting vertex to the fringe

mark the starting vertex

while fringe is not empty:

remove vertex v from the fringe

for each neighbor n of vertex v:

if n is not marked:

add n to fringe

mark n

set edgeTo[n] = v

set distTo[n] = distTo[v] + 1

A

*fringe*is just a term we use for the data structure we are using to store the nodes on the frontier of our traversal's discovery process (the next nodes it is waiting to look at). For BFS, we use a queue for our fringe.`edgeTo[...]`

is a map that helps us track how we got to node `n`

; we got to it by following the edge from `v`

to to `n`

.`distTo[...]`

is a map that helps us track how far `n`

is from the starting vertex. Assuming that each edge is worth a distance of `1`

, then the distance to `n`

is just one more than the distance to get to `v`

. Why? We can use the way we know how to get to `v`

, then pay one more to arrive at `n`

via the edge that necessarily exists between `v`

and `n`

(it must exist since in the `for`

loop header, `n`

is defined as a neighbor of `v`

).Note however that DFS and BFS differ in more than just their fringe data structure. They differ in the order of marking nodes. For DFS we mark nodes only once we visit a node - aka pop it from the fringe. As a result, it's possible to have multiple instances of the same node on the stack at a time if that node has been queued but not visited yet. With BFS we mark nodes as soon as we add them to the fringe so this is not possible.

Recursive DFS implements this naturally via the recursive stack frames; iterative DFS implements it manually:

Initialize the fringe, an empty stack

push the starting vertex on the fringe

while fringe is not empty:

pop a vertex off the fringe

if vertex is not marked:

mark the vertex

visit vertex

for each neighbor of vertex:

if neighbor not marked:

push neighbor to fringe

Last modified 8mo ago