Algorithm Breadth First Search Bfs And Depth First Search Dfs Complete Guide

1. Graph Representation

First, let's define how we will represent a graph. We'll use an adjacency list for simplicity. An adjacency list represents each vertex and its adjacent vertices in a collection (like a dictionary or hash map).

Below is a sample graph for our examples:

    A
   / \
  B   C
 / \   \
D   E   F

This graph can be represented as:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}

2. Breadth-First Search (BFS)

BFS starts at the root node (or an arbitrary starting node) and explores all the neighbors at the present depth prior to moving on to nodes at the next depth level.

Step-by-Step Example for Unweighted, Undirected Graph

Let’s perform BFS on the graph starting from node A.

Steps:

1. Initialize: Start with the initial node A, enqueue it, and mark it as visited.
2. Process Queue: While the queue is not empty, dequeue a node v and visit it. For each neighbor of v that has not been visited, enqueue it and mark it as visited.
3. Repeat: Continue this process until all reachable nodes are visited.

Python Code:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        v = queue.popleft()  # get first node from queue
        print(v, end=' ')  # visit it
        
        # visit all nieghbours
        for neighbor in graph[v]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Sample graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}

print("BFS Traversal starting from A:")
bfs(graph, 'A')

Output:

BFS Traversal starting from A:
A B C D E F 

The order in which nodes are visited is A -> B -> C -> D -> E -> F. This is because BFS explores all the nodes at the current depth before moving to the next level.

BFS Explanation

• Start: Node A is enqueued, and marked as visited.
• Dequeue A: Node A is visited, and its neighbors B and C are enqueued.
• Dequeue B: Node B is visited, and its neighbors A, D, and E are considered. Nodes A and B are already visited, so only D and E are added to the queue.
• Dequeue C: Node C is visited, and its neighbor F is added to the queue since A (its other neighbor) is already visited.
• Dequeue D: Node D is visited, and since all its neighbors (B) have already been visited, nothing new is added to the queue.
• Dequeue E & F: Similarly, nodes E and F are visited, and no new neighbors are added to the queue.

3. Depth-First Search (DFS)

DFS starts at the root node (or an arbitrary starting node) and explores as far as possible along each branch before backtracking.

There are two common ways to implement DFS: using a stack data structure or recursively.

Step-by-Step Example Using Stack

Let’s perform DFS on the same graph starting from node A.

Steps:

1. Initialize: Start with the initial node A, push it onto the stack, and mark it as visited.
2. Process Stack: While the stack is not empty, pop a node v from the stack and visit it. For each neighbor of v that has not been visited, push it onto the stack and mark it as visited.
3. Repeat: Continue this process until all reachable nodes are visited.

def dfs_stack(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        v = stack.pop()  # get last node from stack
        if v not in visited:
            visited.add(v)
            print(v, end=' ')
        
        # Add unvisited neighbors to stack
        for neighbor in reversed(graph[v]):
            if neighbor not in visited:
                stack.append(neighbor)

# Sample graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}

print("\nDFS Traversal using Stack starting from A:")
dfs_stack(graph, 'A')

Output:

DFS Traversal using Stack starting from A:
A B D E C F 

The order in which nodes are visited is A -> B -> D -> E -> C -> F. This path demonstrates the deep exploration before backtracking.

Step-by-Step Example Using Recursion

Alternatively, you can perform DFS using recursion.

Steps:

1. Initialize: Start with the initial node A, recursively visit it, and mark it as visited.
2. Recursive Visit Neighbors: For each neighbor of the node that has not been visited, recursively perform DFS.
3. Continue Until Exhausted: Repeat until all reachable nodes are visited.

def dfs_recursive(graph, v, visited):
    if v not in visited:
        visited.add(v)
        print(v, end=' ')
        
        for neighbor in graph[v]:
            dfs_recursive(graph, neighbor, visited)

def dfs(graph, start):
    visited = set()
    dfs_recursive(graph, start, visited)

# Sample graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}

print("\nDFS Traversal using Recursion starting from A:")
dfs(graph, 'A')

Output:

DFS Traversal using Recursion starting from A:
A B D E C F 

The output here is the same as the stack implementation. But keep in mind that recursive DFS might lead to a stack overflow if the graph is very large and deeply nested.

4. Directed Graph Example

Let’s take a directed graph to illustrate how BFS and DFS work in this context. The graph will look like this:

    A
   / \
  v   v
  B   C
 / \   \
v   v   v
D   E   F

Directed Graph Representation:

directed_graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

BFS on Directed Graph

# Using the same bfs function from before

print("\nBFS Traversal starting from A (Directed Graph):")
bfs(directed_graph, 'A')

Output:

BFS Traversal starting from A (Directed Graph):
A B C D E F 

DFS on Directed Graph

Using the same dfs_stack and dfs_recursive functions from before

# Using stack implementation
print("\nDFS Traversal using Stack starting from A (Directed Graph):")
dfs_stack(directed_graph, 'A')

# Using recursive implementation
print("\nDFS Traversal using Recursion starting from A (Directed Graph):")
dfs(directed_graph, 'A')

Output:

DFS Traversal using Stack starting from A (Directed Graph):
A C F B E D 

DFS Traversal using Recursion starting from A (Directed Graph):
A B D E C F 

Notice how the traversal paths change depending on the direction of the edges in the graph.

5. Key Differences

• BFS uses a queue and explores nodes level by level.
• DFS can use either a stack or recursion and explores nodes by going as deep as possible.
• BFS finds the shortest path in an unweighted graph where each edge has the same weight.
• DFS is useful for problems like pathfinding (e.g., cycle detection), where exploring deeply first is beneficial.

Summary

In this tutorial, we learned the fundamental difference between Breadth-First Search (BFS) and Depth-First Search (DFS). We represented a graph in Python and provided step-by-step examples of both BFS and DFS, illustrating the difference in traversal methods on both undirected and directed graphs.