Algorithms For Dummies

Applying depth-first search

In addition to BFS, you can use a depth-first search (DFS) to discover the vertexes 

in a graph. When performing a DFS, the algorithm begins at the graph root and 

---

178

 

   

  PART 3 

 Exploring the World of Graphs

then explores every node from that root down a single path to the end. It then 

backtracks and begins exploring the paths not taken in the current search path 

until it reaches the root again. At that point, if other paths to take from the root 

are available, the algorithm chooses one and begins the same search again. The 

idea is to explore each path completely before exploring any other path. To make 

this search technique work, the algorithm must mark each vertex it visits. In this 

way, it knows which vertexes require a visit and can determine which path to take 

next. Using BFS or DFS can make a difference according to the way in which you 

need  to  traverse  a  graph.  From  a  programming  point  of  view,  the  difference 

between the two algorithms is how each one stores the vertexes to explore the 

following: