BFS Pseudocode

  • Implement the Breadth-First Search algorithm.

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

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 every edge (v, w) in v's neighborhood do
    if ___________________ then
      _________________________
      _________________________
Solution
mark s as explored, all other vertices as unexplored
Q := a queue data structure, initialized with s 
while Q is not empty do
  remove the vertex from the front of Q, call it v 
  for every edge (v, w) in v's neighborhood do
    if w is not explored then
      mark w as explored 
      add w to the end of Q