7.4.1 Breadth First Search

Next: 7. Directed Graphs Up: 7.4 Depth First Search and Breadth First Search Previous: 7.4 Depth First Search and 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
$\begin{figure} \centerline{\psfig{figure=figures/Fdgbfs.ps}} \end{figure}$
The complexity of both DFS and BFS is O(e).

**Figure 7.11:** Breadth-first search of the digraph in Figure 7.11
$\begin{figure} \centerline{\psfig{figure=figures/Fdgbfs.ps}} \end{figure}$

Implementation of Breadth-First Search

eEL,CSA_Dept,IISc,Bangalore