### 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!

*Depth-first search is a common way that many people naturally approach solving problems like mazes*

**Intuition 2.0:***:*

**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

### (First) Breadth First Search

I**ntuition*** 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

*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.*

**Intuition 2.0:***:*

**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