By now, you've probably handled linear data structures, but graphs are a different beast because they don't have a natural "start" or "end." When we talk about traversal, we're really just talking about how we decide which node to visit next. I've found that the best way to wrap your head around this is to stop thinking about "algorithms" and start thinking about "search patterns."

How do I actually choose between BFS and DFS?

It really comes down to what you're looking for. I like to use the "ripple" analogy for Breadth-First Search (BFS). Imagine dropping a stone in a pond; the wave expands outward in concentric circles. BFS visits every neighbor at distance 1, then every neighbor at distance 2, and so on. If you need to find the shortest path in an unweighted graph (like the fewest number of hops between two people on LinkedIn), BFS is your only real choice.

Depth-First Search (DFS), on the other hand, is like exploring a dark cave. You pick a path and follow it as far as it goes until you hit a dead end, then you backtrack to the last fork in the road. DFS is generally more memory-efficient for deep graphs and is the go-to for things like solving a maze or detecting cycles in a dependency graph. If you just need to know "can I get from A to B?" and don't care how long it takes, DFS is often simpler to write.

How do I prevent my code from getting stuck in an infinite loop?

This is the most common mistake I see. Unlike a tree, a graph can have cycles. If Node A points to Node B, and Node B points back to Node A, a naive traversal will bounce between them until your program crashes with a stack overflow.

The solution is a visited tracker. I usually use a std::vector<bool> if the nodes are indexed numerically, or a std::unordered_set if the nodes are strings or non-sequential IDs. You mark a node as visited the moment you encounter it, and you simply ignore any node that's already been flagged. It's a simple check, but if you forget it, your code is a ticking time bomb.

What does a clean implementation look like in C++?

I prefer using an adjacency list (a vector of vectors) because it's far more efficient than a matrix for most real-world graphs. Here is how I would implement both patterns for a simple network of connected computers.

#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

class NetworkGraph {
    int nodes;
    vector<vector<int>> adj;

public:
    NetworkGraph(int n) : nodes(n), adj(n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // Undirected graph
    }

    void bfs(int startNode) {
        vector<bool> visited(nodes, false);
        queue<int> q;

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

        cout << "BFS Order: ";
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            cout << curr << " ";

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

    void dfs(int node, vector<bool>& visited) {
        visited[node] = true;
        cout << node << " ";

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited);
            }
        }
    }

    void startDfs(int startNode) {
        vector<bool> visited(nodes, false);
        cout << "DFS Order: ";
        dfs(startNode, visited);
        cout << endl;
    }
};

int main() {
    NetworkGraph net(6);
    net.addEdge(0, 1);
    net.addEdge(0, 2);
    net.addEdge(1, 3);
    net.addEdge(1, 4);
    net.addEdge(2, 5);

    net.bfs(0); // Expected: 0 1 2 3 4 5
    net.startDfs(0); // Expected: 0 1 3 4 2 5 (or similar)
    return 0;
}

Notice that BFS uses a std::queue to keep track of the "frontier," while DFS uses recursion, which implicitly uses the call stack. If you're dealing with a massive graph where recursion might hit the limit, you can easily rewrite DFS using a std::stack explicitly.

📋 Practical Task

Exercise: Building a Social Circle Distance Tracker

You are tasked with building a simplified "Degrees of Separation" tool. You will be given a graph representing people (nodes) and their friendships (edges). Your goal is to determine the minimum number of hops between two specific people.

Requirements:

• Implement a function int getShortestDistance(int start, int target, const vector<vector<int>>& adj).
• Use a Breadth-First Search (BFS) approach, as DFS will not guarantee the shortest path.
• Instead of just tracking if a node was visited, maintain a distance vector where distance[i] stores the number of hops from the start node to node i.
• If the target is unreachable, return -1.

Test Case:
Graph: 0-1, 0-2, 1-3, 2-3, 3-4.
Start: 0, Target: 4.
Expected Output: 3 (Path: 0 → 1 → 3 → 4 or 0 → 2 → 3 → 4).