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