Graphs/Breadth First Traversal
From charlesreid1
Also see BFS
Contents
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 time, similar to DFS.
Related
Graphs:
- Graphs#Graph Traversals
- Graphs/Depth First Traversal
- Graphs/Breadth First Traversal
- Graphs/Euler Tour
- Graphs/Euler Circuit
Traversals on trees:
Breadth-first search and traversal on trees:
Depth-first search and traversal on trees:
OOP design patterns:
Flags