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

(First) Breadth First Search

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

Leave a Reply

Your email address will not be published. Required fields are marked *