DFS Pseudocode

  • Implement the Depth-First Search algorithm.

Exercise Based on your understanding of the DFS process, complete the pseudocode of DFS!

mark s as explored;all other vertices as unexplored ______________ data structure, initialized with s while____is not empty do remove the vertex from ____________, call it v for edge (v, w) in v's neighborhood do if ____________ then _________________________ _________________________
Solution
mark s as explored, all other vertices as unexplored S := a stack data structure, initialized with s while S is not empty do pop the vertex from the top of S, call it v for each edge (v, w) in v's neighborhood do if w is unexplored then mark w as explored push w to the top of S