The Ultimate Guide to Breadth-First Search and Depth-First Search 

Introduction

In the dynamic world of computer science, the need to efficiently explore and traverse data structures like graphs is vital. Two of the most fundamental algorithms for this purpose are Breadth-First Search (BFS) and Depth-First Search (DFS). Invented during the early developments of computer science, BFS was first described by Konrad Zuse in the 1940s, while DFS was formally introduced by C.Y. Lee in the 1960s. These algorithms are the building blocks of countless modern technologies — from AI decision trees to GPS navigation systems.

Understanding BFS & DFS

What is BFS?

Breadth-First Search explores a graph level by level. It uses a queue to traverse the nearest nodes first, making it ideal for finding the shortest path in unweighted graphs.

What is DFS?

Depth-First Search dives deep into the graph's branches before backtracking. It typically uses a stack (or recursion), and is preferred in scenarios like puzzle solving or detecting cycles.

Key Characteristics

  • BFS: Layered exploration, uses queue, shortest path in unweighted graphs.
  • DFS: Deep exploration, uses stack/recursion, better for exhaustive searches.

How Are They Different?

  • Memory Usage: BFS uses more memory due to queue size; DFS is often more space efficient.
  • Path Finding: BFS ensures shortest path; DFS may find a longer one.
  • Use-Cases: BFS is ideal for shortest path problems; DFS excels in problems involving full exploration.

Step-by-Step Mathematical Implementation

BFS Steps

  1. Let G = (V, E) be a graph with vertices V and edges E.
  2. Choose a starting vertex s.
  3. Initialize all vertices with distance = ∞ and visited = false.
  4. Set distance[s] = 0, mark s as visited.
  5. While queue is not empty:
    • Dequeue vertex u.
    • For each unvisited neighbor v of u:
      • Set distance[v] = distance[u] + 1
      • Mark v visited, enqueue v.

DFS Steps

  1. Let G = (V, E), and choose a starting vertex s.
  2. Mark s as visited.
  3. For each neighbor v of s:
    • If v is unvisited, recursively call DFS(v).

Solving DFS & BFS

DFS (Depth-First Search)

DFS explores as deep as possible before backtracking. Starting at node 0, the traversal goes deep down a branch before returning and moving to the next.

Traversal Output: 0 → 1 → 4 → 5 → 2 → 6 → 3 → 7

Steps:

  1. Start at node 0
  2. Visit 1, then go to 4
  3. Backtrack to 1 → 5
  4. Backtrack to 0 → 2 → 6
  5. Backtrack to 0 → 3 → 7


BFS (Breadth-First Search)

BFS explores all neighbors level-by-level before moving deeper.

Traversal Output: 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7

Steps:

  1. Start at 0, enqueue its neighbors 1, 2, 3
  2. Visit 1, enqueue 4, 5
  3. Visit 2, enqueue 6
  4. Visit 3, enqueue 7
  5. Then process queue → 4, 5, 6, 7


Code on github: https://github.com/prathmesh192003/dfs_bfs 

DFS Code

#include<bits/stdc++.h>
using namespace std;

void DFS(int node, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;        // Mark node as visited
    cout << node << " ";         // Print the node

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            DFS(neighbor, adj, visited); // Recurse deeper
        }
    }
}

int main() {
    int V = 8;
    vector<vector<int>> adj(V);

    adj[0] = {1, 2, 3};
    adj[1] = {0, 4, 5};
    adj[2] = {0, 6};
    adj[3] = {0, 7};
    adj[4] = {1};
    adj[5] = {1};
    adj[6] = {2};
    adj[7] = {3};

    vector<bool> visited(V, false);
    cout << "DFS Traversal: ";
    DFS(0, adj, visited);
    return 0;
}

BFS Code

#include<bits/stdc++.h>
using namespace std;

void BFS(int start, vector<vector<int>>& adj, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int V = 8;
    vector<vector<int>> adj(V);

    adj[0] = {1, 2, 3};
    adj[1] = {0, 4, 5};
    adj[2] = {0, 6};
    adj[3] = {0, 7};
    adj[4] = {1};
    adj[5] = {1};
    adj[6] = {2};
    adj[7] = {3};

    vector<bool> visited(V, false);
    cout << "BFS Traversal: ";
    BFS(0, adj, visited);
    return 0;
}

Time and Space Complexity

Algorithm Best Case Average Case Worst Case Space Complexity
BFS O(V + E) O(V + E) O(V + E) O(V)
DFS O(V + E) O(V + E) O(V + E) O(V)

Real-World Applications

  • Social Networks (BFS): Finding friends of friends (friend suggestion algorithms).
  • Web Crawling (DFS): Deep exploration of websites for indexing pages.
  • Pathfinding in Games (BFS): AI characters finding shortest route in real-time maps.
  • Solving Mazes (DFS): Searching all possible paths until a solution is found.

Conclusion

BFS and DFS are timeless algorithms in computer science that continue to empower real-world solutions. Whether it's suggesting friends on social media or enabling AI in games to move intelligently, their applications are vast. Mastering these foundational tools allows developers and researchers to build robust systems and tackle complex problems efficiently.

Comments

Post a Comment