Revision as of 11:52, 9 September 2017

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 is notable because the tree that is formed will yield the shortest path between two nodes.

Because of the fact that the depth-first search must proceed in an ordered manner, and cannot re-visit vertices that have already been vertices, we can think of the depth-first search as forming a tree.

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 DFS 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)

Flags

Graphs/Breadth First Traversal: Difference between revisions

From charlesreid1