Data Structures and Algorithms in C (DSA)

📘 Chapter: BFS and DFS (Traversal & Search)

Now that we understand how to represent graphs, the next crucial step is learning how to explore or "traverse" them. Graph traversal algorithms allow us to visit every vertex and edge in a systematic manner. The two most fundamental and widely used graph traversal algorithms are Breadth-First Search (BFS) and Depth-First Search (DFS). They are the backbone for solving a vast array of graph problems, from finding the shortest path to detecting cycles.

🌳 Why Traverse Graphs?

• Searching: Finding if a path exists between two nodes.
• Reachability: Determining all nodes reachable from a starting node.
• Shortest Path: Finding the shortest path in unweighted graphs.
• Connectivity: Identifying connected components in a graph.
• Cycle Detection: Discovering if a graph contains cycles.
• Topological Sorting: Ordering tasks with dependencies.

🌊 1. Breadth-First Search (BFS)

BFS explores a graph level by level. It starts at a source node, then visits all its immediate neighbors, then all their unvisited neighbors (nodes at distance 2 from the source), and so on. It's like ripples spreading outwards when you drop a stone in a pond. BFS uses a **Queue** data structure to manage which nodes to visit next.

BFS Algorithm Steps:

1. Choose a starting node (source). Enqueue it and mark it as visited.
2. While the queue is not empty:
   • Dequeue a node `u`.
   • Process node `u` (e.g., print it, check for target).
   • For each unvisited neighbor `v` of `u`:
     • Mark `v` as visited.
     • Enqueue `v`.

// Conceptual C++ for BFS
void BFS(int start_node, int V, const vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    queue<int> q;

    visited[start_node] = true;
    q.push(start_node);

    cout << "BFS Traversal starting from node " << start_node << ": ";

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

        // Visit all unvisited neighbors of u
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    cout << endl;
}
  

BFS Characteristics:

• Guaranteed Shortest Path (Unweighted): Finds the shortest path (in terms of number of edges) from the source to all reachable nodes in an unweighted graph.
• Good for finding connected components.
• Explores systematically, ensuring all nodes at a given "level" are visited before moving deeper.

Time Complexity: $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges. Each vertex and each edge is processed at most once.
Space Complexity: $O(V)$ for the queue and the visited array.

🌲 2. Depth-First Search (DFS)

DFS explores a graph by going as deep as possible along each branch before backtracking. It's like exploring a maze: you pick a path and follow it until you hit a dead end, then you backtrack and try another path. DFS uses a **Stack** data structure (or implicitly, the recursion stack) to keep track of nodes to visit.

DFS Algorithm Steps (Recursive Approach):

1. Start at a source node, mark it as visited, and process it.
2. For each unvisited neighbor `v` of the current node `u`:
   • Recursively call DFS on `v`.

// Conceptual C++ for DFS (Recursive)
vector<bool> visited_dfs; // Global or passed around

void DFS(int u, const vector<vector<int>>& adj) {
    visited_dfs[u] = true;
    cout << u << " "; // Process the node

    // Recursively visit all unvisited neighbors of u
    for (int v : adj[u]) {
        if (!visited_dfs[v]) {
            DFS(v, adj);
        }
    }
}

// Call from main:
// visited_dfs.assign(V, false);
// cout << "DFS Traversal starting from node " << start_node << ": ";
// DFS(start_node, adj);
// cout << endl;
  

DFS Characteristics:

• Useful for finding cycles in a graph.
• Key for topological sorting, finding strongly connected components, and bridges/articulation points.
• The path found by DFS is not necessarily the shortest.

Time Complexity: $O(V + E)$, similar to BFS.
Space Complexity: $O(V)$ for the recursion stack (in the worst case, a skewed graph can lead to stack depth of $V$) and the visited array.

🆚 BFS vs. DFS: Key Differences & When to Use

📌 Real-Life Example (UdaanPath)

BFS and DFS are not just theoretical algorithms; they are the workhorses behind many features you interact with daily, including on platforms like UdaanPath:

• Course Prerequisite Checking (DFS/BFS): If courses are nodes and prerequisites are directed edges, both DFS and BFS can be used. DFS can help detect circular dependencies (e.g., Course A requires B, B requires C, C requires A), which would be an invalid curriculum. BFS can find the shortest sequence of courses to take to unlock a target course.
• Content Discovery/Recommendation (BFS): Imagine a user views Course X. Using BFS, you can find courses "closest" to Course X (e.g., related topics, similar skill levels) by traversing edges in a content graph. This can power "users who liked this also liked..." features.
• User Network Analysis (BFS/DFS): In a social learning feature where users connect, BFS can find users within 'N' degrees of separation from a given user. DFS could explore specific chains of connections for deeper analysis (e.g., how a particular piece of information might spread through a network).
• Website/App Navigation & Sitemap Generation (BFS/DFS): If an application's pages are nodes and links are edges, BFS can map out the entire structure (like a sitemap), finding the shortest click paths to any page. DFS could be used to crawl specific sections deeply.
• Feature Dependency Graph (DFS for Cycle Detection): If developing new features has dependencies (e.g., Feature A must be built before Feature B), DFS can ensure there are no circular dependencies that would halt development.

✅ Summary: Your Graph Exploration Tools

• Graph Traversal is about visiting all nodes and edges in a graph.
• BFS (Breadth-First Search) uses a Queue to explore level by level. Good for shortest paths in unweighted graphs.
• DFS (Depth-First Search) uses a Stack (or recursion) to explore as deeply as possible before backtracking. Good for cycle detection and topological sorting.
• Both typically have $O(V + E)$ time complexity and $O(V)$ space complexity.
• The choice between BFS and DFS depends on the problem's requirements.

📤 Coming Next: Topological Sort (Kahn’s & DFS)

Building upon our understanding of graph traversals, the next chapter will delve into Topological Sort. This is a crucial concept for directed acyclic graphs (DAGs), allowing us to linearly order vertices based on their dependencies. We'll explore two primary algorithms: Kahn's Algorithm (using BFS) and the DFS-based approach.