Also see BFS

Notes

What BFS Gets Us

Breadth-first search is important because it gets us the shortest path (the path with the fewest number of edges) from a vertex u to a vertex v. To state this more rigorously, a path in a breadth-first search tree rooted at vertex u to any other vertex v is guaranteed to be the shortest path from u to v (where shortest path denotes number of edges).

The fact that the BFS tree yields shortest paths is a natural consequence of how the BFS process works.

BFS Tree

Edges discovered during a breadth-first search will form a tree.

BFS tree is notable because the tree consists only of the shortest paths between two nodes.

Edge Classification

For a depth-first search, edges were classified as back edges (connecting vertices to ancestor vertices), forward edges (connecting vertices to descendant vertices), and cross edges (connects vertices to other vertices that are not ancestors or descendants).

For breadth-first search, all BFS tree edges form the shortest path between two vertices. That means that there are NO back edges or forward edges (because if they existed, they would be shorter paths and therefore provide a shorter path).

All edges are classified as:

Cross edge - connects a vertex to a vertex that is not an ancestor or a descendant in the BFS tree

Pseudocode

def bfs(g, s, discovered):
    discovered = empty map
    create new queue
    queue.add(s)
    while queue is not empty:
        u = queue.pop()
        for e in incident_edges(u):
            v = opposite_edge(u, e)
            if v not in discovered:
                // add (v,e) to discovered
                discovered[v] = e 
                queue.add(v)

Properties of BFS

Important properties of BFS:

A BFS traversal that starts at a source vertex will visit all vertices reachable from vertex s.

If a vertex v is at level i, then the path on the BFS tree between the source vertex s and the target vertex v will consist of i edges. (Any other paths will have at least i edges.)

If two vertices (u,v) have an edge connecting them, and the edge is not in the BFS tree, the level number of v can only be maximum 1 level greater than the level of u. (Otherwise, if their level difference were larger, the edge (u,v) would represent a shorter path, and would therefore be part of the BFS tree.)

Big O Cost

Breadth-first search runs in $O(n+m)$ time, similar to DFS.

Flags

Graphs/Breadth First Traversal

From charlesreid1

Contents