Table of Contents

Vocabulary

Depth First Search (BFS)

What Is Depth First Search?

<aside> 💡 Depth First Search (BFS) is a graph traversal algorithm that traverses a graph. However, unlike BFS, it traverses the graph vertically, going branch by branch

</aside>

DFS Algorithm Explanation

<aside> 💡 DFS works by pushing nodes to in a stack. When a node is visted, it is marked as visited and any edges the node has to other nodes are added to the stack.

DFS Algorithm Steps

  1. Pushing the starting node onto the stack.
  2. Pop the starting node, mark it has visited and push the node’s edges (the other nodes it’s connected to) onto the stack.
  3. Pop the next node off of the stack and repeat step 2 until there there are no edges.

</aside>

Time Complexity

<aside> 💡 The Time Complexity of Breadth First Search is $O(V+E)$. At worst case, we will visit every node and explore every edge.

</aside>