Graph Traversal: BFS, DFS, Topological Sort, and the Visited Set

Problem Context

Almost every interesting computational problem is a graph problem in disguise. Pages on the web, friendships in a social network, package dependencies in your build, calls in your call graph, paths through your microservice mesh, states in a workflow — graphs all. BFS and DFS are the two primitives from which most of graph algorithms is built: shortest paths in unweighted graphs, cycle detection, topological sorting, connectivity, bipartite checking, flood-fill, maze solving.

The mistake most people make is "BFS is for shortest path, DFS is for everything else". The honest answer: BFS for shortest-path-by-edge-count and level-order processing; DFS for ordering, cycle detection, and recursion-friendly traversals. This guide is when to reach for which, and the variations that turn them into real algorithms.

Concept Explanation

Both BFS and DFS visit every vertex once and every edge once → O(V + E). The difference is the data structure that holds the frontier:

• BFS uses a Queue (FIFO) → expands the closest unexplored vertices first → finds shortest path by edge count.
• DFS uses a Stack (LIFO, often the call stack) → goes deep before wide → naturally produces discovery/finish times used by topo sort, SCC, and articulation-point algorithms.

flowchart LR
    G["Graph problem"] --> Q1{"Shortest path?"}
    Q1 -->|unweighted| BFS["BFS<br/>Queue, levels"]
    Q1 -->|weighted +| DJK["Dijkstra<br/>(min-heap)"]
    Q1 -->|no| Q2{"Need ordering?"}
    Q2 -->|yes| TOPO["DFS topo sort<br/>or Kahn's BFS"]
    Q2 -->|no| Q3{"Cycle detection?"}
    Q3 -->|yes| DFS3["DFS 3-colour<br/>WHITE/GRAY/BLACK"]
    Q3 -->|no| CC["BFS or DFS<br/>(connected components)"]

    style BFS fill:#0078D4,color:#fff,stroke:#005a9e
    style DFS3 fill:#dc2626,color:#fff,stroke:#b91c1c

Implementation

Step 1: Adjacency list — the only representation you need

// For nearly every real-world graph (sparse, |E| ≪ |V|²): adjacency list
var graph = new Dictionary<int, List<int>>();
void AddEdge(int u, int v)
{
    if (!graph.ContainsKey(u)) graph[u] = new();
    if (!graph.ContainsKey(v)) graph[v] = new();   // include for &quot;directed&quot; too
    graph[u].Add(v);
    // graph[v].Add(u);   ← uncomment for undirected
}

// Adjacency matrix (bool[V,V]): use only when V is small (&lt; 1000)
// and the graph is dense (|E| ~ V²)

Step 2: BFS — shortest path in unweighted graphs

public static int[] BFSDistances(Dictionary<int, List<int>> g, int source)
{
    var dist = new Dictionary<int, int> { [source] = 0 };
    var q = new Queue<int>();
    q.Enqueue(source);
    while (q.Count > 0)
    {
        var u = q.Dequeue();
        foreach (var v in g.GetValueOrDefault(u) ?? new())
        {
            if (dist.ContainsKey(v)) continue;
            dist[v] = dist[u] + 1;
            q.Enqueue(v);
        }
    }
    return dist.Select(kv => kv.Value).ToArray();
}

Step 3: DFS — recursive and iterative

// Recursive — clean, blows the stack on adversarial input
public static void DFS(Dictionary<int, List<int>> g, int u, HashSet<int> seen)
{
    if (!seen.Add(u)) return;
    foreach (var v in g.GetValueOrDefault(u) ?? new()) DFS(g, v, seen);
}

// Iterative — safe for any depth
public static void DFSIter(Dictionary<int, List<int>> g, int start)
{
    var seen = new HashSet<int>();
    var stack = new Stack<int>();
    stack.Push(start);
    while (stack.Count > 0)
    {
        var u = stack.Pop();
        if (!seen.Add(u)) continue;
        foreach (var v in g.GetValueOrDefault(u) ?? new())
            if (!seen.Contains(v)) stack.Push(v);
    }
}

Step 4: Topological sort — Kahn's algorithm (BFS-flavoured)

// For DAGs only. Returns a linear order respecting all edges, or null if a cycle exists.
public static List<int>? TopoSort(Dictionary<int, List<int>> g)
{
    var indeg = g.Keys.ToDictionary(k => k, _ => 0);
    foreach (var (_, vs) in g) foreach (var v in vs) indeg[v] = indeg.GetValueOrDefault(v) + 1;

    var q = new Queue<int>(indeg.Where(kv => kv.Value == 0).Select(kv => kv.Key));
    var order = new List<int>();
    while (q.Count > 0)
    {
        var u = q.Dequeue();
        order.Add(u);
        foreach (var v in g.GetValueOrDefault(u) ?? new())
            if (--indeg[v] == 0) q.Enqueue(v);
    }
    return order.Count == indeg.Count ? order : null;   // null = cycle exists
}

Step 5: Cycle detection in directed graphs — three-colour DFS

// WHITE = unvisited, GRAY = on current DFS path, BLACK = fully processed
// A back-edge to a GRAY vertex == cycle.
enum Color { White, Gray, Black }

public static bool HasCycle(Dictionary<int, List<int>> g)
{
    var color = g.Keys.ToDictionary(k => k, _ => Color.White);
    bool Dfs(int u)
    {
        color[u] = Color.Gray;
        foreach (var v in g.GetValueOrDefault(u) ?? new())
        {
            if (color.GetValueOrDefault(v) == Color.Gray) return true;        // back-edge
            if (color.GetValueOrDefault(v) == Color.White && Dfs(v)) return true;
        }
        color[u] = Color.Black;
        return false;
    }
    return g.Keys.Any(u => color[u] == Color.White && Dfs(u));
}

// For undirected graphs: a back-edge that isn&apos;t to the parent == cycle.
// Track parent and ignore it.

Step 6: Connected components / flood-fill

public static List<List<int>> ConnectedComponents(Dictionary<int, List<int>> g)
{
    var seen = new HashSet<int>();
    var components = new List<List<int>>();
    foreach (var start in g.Keys)
    {
        if (seen.Contains(start)) continue;
        var component = new List<int>();
        var q = new Queue<int>(); q.Enqueue(start); seen.Add(start);
        while (q.Count > 0)
        {
            var u = q.Dequeue();
            component.Add(u);
            foreach (var v in g.GetValueOrDefault(u) ?? new())
                if (seen.Add(v)) q.Enqueue(v);
        }
        components.Add(component);
    }
    return components;
}

Pitfalls

1. DFS for shortest path. DFS finds a path; not necessarily the shortest. Use BFS for unweighted shortest path, Dijkstra for weighted with non-negative edges, Bellman-Ford for negative edges.

2. Forgetting to mark visited at enqueue time. Marking only at dequeue lets the same vertex be enqueued many times via different parents → quadratic blowup. Mark when pushing to the queue/stack.

3. Recursive DFS on a chain of 100k nodes. Stack overflow. Default to iterative DFS unless you can prove the depth is logarithmic.

4. Stack vs Queue confusion. Swapping Stack for Queue turns BFS into DFS silently — the algorithm still terminates, but distances are wrong. Name your collections clearly.

5. Cycle detection in undirected graphs using directed-graph rules.Every undirected edge looks like a back-edge if you don't track the parent. Pass the parent into the recursive call and skip it.

6. Adjacency matrix for sparse graphs. A bool[10000, 10000]is 100 MB; an adjacency list with a few thousand edges is a few KB. Use a matrix only for dense graphs with V < 1000.

Practical Takeaways

• Adjacency list (Dictionary<int, List<int>>) is the right default. Matrices only for dense, small graphs.
• BFS for unweighted shortest path and level-order processing. Queue. Mark visited on enqueue.
• DFS for ordering (topo sort), cycle detection (three-colour), articulation points, SCC. Stack or recursion.
• Recursive DFS only when depth is bounded; iterative DFS otherwise.
• Topological sort: Kahn's (BFS) is easier to reason about; DFS-based is shorter.
• Cycle detection in directed graphs: three-colour DFS. In undirected: BFS/DFS with parent tracking.
• For weighted shortest paths, jump straight to Dijkstra / A* / Bellman-Ford. Don't try to coerce BFS.