[Data Structure] Graphs: Breadth-first Search / Depth-first Search

Breadth-First Search

An algorithm commonlyu must visit every vertex in a graph in some order, known as a graph traversal.

A breadth-first search (BFS) is a traversal that visits a starting vertex, then all vertices of distance 1 from that vertex, then of distance 2, and so on, without revisiting a vertex. 

 

Since the visiting order of same-distance vertices doesn't matter, there can be multiple graph traversals if we use BFS method. 

 

Breadth-first search algorithm

BFS(startV) {
   Enqueue startV in frontierQueue
   Add startV to discoveredSet

   while ( frontierQueue is not empty ) {
      currentV = Dequeue from frontierQueue
      "Visit" currentV
      for each vertex adjV adjacent to currentV {
         if ( adjV is not in discoveredSet ) {
            Enqueue adjV in frontierQueue
            Add adjV to discoveredSet
         }
      }
   }
}

When the BFS algorithm first encounters a vertex, that vertex is said to have been discovered.

In the BFS algorithm, the vertices in the queue are called the frontier, being vertices thus far discovered but not yet visited. Because each vertex is visited at most once, an already-discovered vertex is not enqueued again.

A "visit" may mean to print the vertex, append the vertex to a list, compare vertex data to a value and return the vertex if found, etc.

 

---

Depth-First Search

A depth-first search (DFS) is a traversal that visits a starting vertex, then visits every vertex along each path starting from that vertex to the path's end before backtracking. 

 

Same as the BFS, DFS traversal can also have multiple traversal paths.

 

DFS Algorithm

DFS(startVertex) {
   Create new, empty stack named vertexStack
   Create new, empty set named visitedSet

   Push startVertex to vertexStack

   while (vertexStack is not empty) {
      currentV = Pop vertexStack

      if (currentV is not in visitedSet) {
         Visit currentV
         Add currentV to visitedSet
         for each vertex adjV adjacent to currentV {
            Push adjV to vertexStack
         }
      }
   }
}

 

Recursive DFS Algorithm

RecursiveDFS(currentV) {
   if ( currentV is not in visitedSet ) {
      Add currentV to visitedSet
      "Visit" currentV
      for each vertex adjV adjacent to currentV {
         RecursiveDFS(adjV)
      }
   }
}