# Depth First Search vs Breadth First Search

### What’s the point? Why inflict this pain upon ourselves?

It turns out that many of the coolest algorithms involve some form of exploring. Now exploring can mean a ton of things but in this case, we are talking about exploring a graph (Basically: A collection of things connected by roads).

### Ok fine, why are there 2 of them?

There are different ways to explore a graph. Do you want to go as far as possible before trying out a different path? or do you want to explore all paths at the same rate?

### (DFS) Depth First Search

Intuition 1.0: Hey this road looks new, let’s go down it, oh I see another road, let’s go down it, oh look! another road let’s go down it!
Intuition 2.0: Depth-first search is a common way that many people naturally approach solving problems like mazes
Steps to DFS:
Visit a Vertex v
Mark v as visited
Recursively visit each unvisited vertex attached to v

#### Pseudocode on graph G which contains Vertices V and edges E

Recursive

` DFS (V,E):    Color all nodes V white     For every vertex in V:         if vertex is white:             DFS_Recursive(vertex,E)DFS_Recursive(v,E):     Color v black     Do something with v     for every neighbor n of v connected by an edge e :         DFS_Recursive (n,E) `

Iterative

`DFS (V,E):     color all nodes in V white     For every vertex v in V:         stack <-- v         while stack:             popped = stack.pop()             popped.color <-- black             Do stuff with popped             for every neighbor n of v:                 if n is white:                     stack <-- n`

#### Complexity Analysis

Time Complexity – O(V+E) if the graph is an adjacency list
Space Complexity – O(V) if it’s a dense graph

Intuition 1.0: Hey there are 10 different roads, let’s take 1 step down each of them, let’s take another 1 step down each of them
Intuition 2.0: Think of zombie infections (or plagues), it wouldn’t spread down one path then go back and spread down another. It would spread equally among every path.
Steps to BFS:
Visit a Vertex v
Add all neighbors to a Queue
Pop from queue and repeat

#### Pseudocode on graph G which contains Vertices V and edges E

`BFS(V,E):       color all nodes in V white         For every vertex v in V:             Queue <-- v             while Queue :             popped = Queue .popleft()             popped.color <-- black             Do stuff with popped             for every neighbor n of v:                 if n is white:                     Queue <-- n`

#### Complexity Analysis

Time Complexity – O(V+E) if the graph is an adjacency list
Space Complexity – O(V) if it’s a dense graph