7.4.1 Breadth First Search

• Level by level traversal
• A queue data structure is used

 

 
 


Figure 7.11: Breadth-first search of the digraph in Figure 7.11


• The complexity of both DFS and BFS is O(e).

Implementation of Breadth-First Search

void bfs (v) /* visits all vertices connected to v

in breadth-first fashion */

vertex x, y;

vertexqueue Q;

{

            mark [v] = visited ;

            enqueue (v, Q);

                while (Q not empty)

                    { x = front (Q) ;

                        dequeue (Q) ;

                        for (each vertex y adjacent to x)

                        if (mark[y] = unvisited)

                {

                        mark[y] = visited ;

                        enqueue(y,Q) ;

                        insert ((x,y), T)

            }

    }

}
 

Example: See Figure 7.11.