BFS

In Chapter 17.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.

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.

The pseudocode for BFS is as follows:

Initialize the fringe (a queue with the starting vertex) and mark that vertex.
Repeat until fringe is empty:
    Remove vertex v from the fringe.
    For each unmarked neighbor n of v:
        Mark n.
        Add n to fringe.
        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.

Question 18.1: If instead we used a stack as our fringe instead of a queue, what do we get?

Answer 18.1: DFS traversal.

edgeTo[...] is a map that helps us track how we got to node n; we got to it via following the edge from v to get 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 (since 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.)

This slide deck illustrates how this pseudocode can be carried out on an example graph.

results matching ""

    No results matching ""