Graph Basics: Adjacency Lists, BFS and DFS Traversal

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

In the Bookstore reader community users follow each other. An extreme test for a campaign: 2,000 users who all follow each other. Starting from user 0 we compute how many steps it takes to reach everyone with BFS (Breadth-First Search). There are two implementations; the only difference is when they mark a node as "visited":

long ListBfs(Graph<int> graph, bool markOnEnqueue)
{
    HashSet<int> visited = [];
    Queue<int> queue = new();
    queue.Enqueue(0);
    if (markOnEnqueue) visited.Add(0);
    long enqueues = 1;
    while (queue.Count > 0)
    {
        int v = queue.Dequeue();
        if (!markOnEnqueue && !visited.Add(v)) continue; // mark when dequeuing
        foreach (int next in graph.Neighbors(v))
        {
            if (visited.Contains(next)) continue;
            if (markOnEnqueue) visited.Add(next);            // mark when enqueuing
            queue.Enqueue(next);
            enqueues++;
        }
    }

    return enqueues;
}

Both return the correct result. But how many times in total is something added to the queue? For the first one the answer is obvious: each user once, 2,000. What is your guess for the second? 4,000, 20,000, or much more?

Graph Concepts

A graph consists of vertices (nodes) and the edges connecting them. Unlike a tree, a vertex can have more than one "parent", there can be cycles, and the graph can consist of pieces that are not connected to each other. Three questions determine the kind of graph. Do edges have a direction? Following is directed (Ada may follow Alan without the reverse being true), a road between two cities is undirected. Do edges have a weight? Following does not, a road has a distance or a cost. Are there cycles? In dependency graphs a cycle is an error, in a social graph it is normal.

In this post we work with unweighted graphs: the fewest steps with BFS, deep traversal with DFS (Depth-First Search), and connected components. Weighted shortest paths are the subject of the 17th post of the series, dependency order where cycles are errors that of the 16th.

Adjacency Lists and Adjacency Matrices

There are two classic ways to keep a graph in memory. In an adjacency list every vertex keeps the list of its neighbors:

public sealed class Graph<T> where T : notnull
{
    private readonly Dictionary<T, List<T>> _adjacency = [];

    public Graph(bool directed) => Directed = directed;

    public bool Directed { get; }
    public int VertexCount => _adjacency.Count;
    public int EdgeCount { get; private set; }
    public IEnumerable<T> Vertices => _adjacency.Keys;

    public void AddVertex(T vertex) => _adjacency.TryAdd(vertex, []);

    public void AddEdge(T from, T to)
    {
        AddVertex(from);
        AddVertex(to);
        _adjacency[from].Add(to);
        if (!Directed)
        {
            _adjacency[to].Add(from); // undirected: a neighbor in both directions
        }

        EdgeCount++;
    }

    public IReadOnlyList<T> Neighbors(T vertex) =>
        _adjacency.TryGetValue(vertex, out List<T>? list) ? list : [];
}

An adjacency matrix is a V × V bool[,], and matrix[u, v] answers "is there an edge from u to v" in a single step. The choice depends on how dense the graph is:

Almost all real-world graphs are sparse: a user follows a few hundred out of millions. A 10,000-vertex matrix takes its space whatever the edge count:

adjacency matrix bool[10000,10000]: 95.4 MB regardless of edge count

Using a Dictionary with a generic T lets vertices be string user names or Guids. If performance is critical, mapping vertices to int ids 0..V-1 and using List<int>[] plus a bool[] visited array removes the hashing cost; this "id mapping" is the standard trick of large graph libraries.

BFS: The Fewest Steps

BFS spreads out from the start layer by layer: first everything 1 step away, then everything 2 steps away. A queue provides this; whatever enters the queue first is processed first, so the first time we reach a vertex we have reached it by the shortest path (in an unweighted graph):

public static Dictionary<T, int> Distances<T>(Graph<T> graph, T start) where T : notnull
{
    Dictionary<T, int> distance = new() { [start] = 0 };
    Queue<T> queue = new();
    queue.Enqueue(start);
    while (queue.Count > 0)
    {
        T current = queue.Dequeue();
        foreach (T next in graph.Neighbors(current))
        {
            // Marked when enqueued: no vertex enters the queue twice
            if (distance.TryAdd(next, distance[current] + 1))
            {
                queue.Enqueue(next);
            }
        }
    }

    return distance;
}

The distance dictionary is both the "visited" set and the answer. Our follow graph:

Graph<string> follows = new(directed: true);
follows.AddEdge("ada", "alan");
follows.AddEdge("ada", "grace");
follows.AddEdge("alan", "edsger");
follows.AddEdge("grace", "edsger");
follows.AddEdge("edsger", "barbara");
follows.AddEdge("barbara", "ada");
follows.AddVertex("linus");

foreach ((string user, int hops) in GraphTraversal.Distances(follows, "ada"))
{
    Console.WriteLine($"{user,-8} {hops}");
}

ada      0
alan     1
grace    1
edsger   2
barbara  3

Linus is not in the list because there is no path from Ada to him. The fact that "Edsger is reachable two ways" is lost too; BFS counts every vertex from the first place it reaches it. If we want the path itself, we store where we came from for each vertex (its parent) and walk back from the target:

public static List<T>? ShortestPath<T>(Graph<T> graph, T start, T target) where T : notnull
{
    Dictionary<T, T> parent = [];
    HashSet<T> visited = [start];
    Queue<T> queue = new();
    queue.Enqueue(start);
    while (queue.Count > 0)
    {
        T current = queue.Dequeue();
        if (EqualityComparer<T>.Default.Equals(current, target))
        {
            List<T> path = [current];
            while (parent.TryGetValue(path[^1], out T? p)) path.Add(p);
            path.Reverse();
            return path;
        }

        foreach (T next in graph.Neighbors(current))
        {
            if (visited.Add(next))
            {
                parent[next] = current;
                queue.Enqueue(next);
            }
        }
    }

    return null;
}

grace -> edsger -> barbara -> ada -> alan

Grace does not follow Alan directly, and because the graph is directed she cannot use the edge from Alan backwards; the four-step path is the shortest. The cost is O(V + E): every vertex enters the queue once and every edge is examined once. How that is derived is in the "Deriving Time Complexity from Code" post of the Big-O and Complexity series.

DFS: Recursive and Iterative

DFS follows a path to its end and backtracks when it hits a dead end. The recursive version is very natural:

public static List<T> DepthFirstRecursive<T>(Graph<T> graph, T start) where T : notnull
{
    List<T> order = [];
    HashSet<T> visited = [];
    Visit(start);
    return order;

    void Visit(T vertex)
    {
        if (!visited.Add(vertex))
        {
            return;
        }

        order.Add(vertex);
        foreach (T next in graph.Neighbors(vertex))
        {
            Visit(next);
        }
    }
}

But the recursion depth can be as long as the longest path; on a 100,000-vertex chain a StackOverflowException kills the process (the 5th post of the series). The iterative version uses an explicit Stack<T> instead of the call stack. If we push the neighbors in reverse order we get the same order as the recursive version:

public static List<T> DepthFirstIterative<T>(Graph<T> graph, T start) where T : notnull
{
    List<T> order = [];
    HashSet<T> visited = [];
    Stack<T> stack = new();
    stack.Push(start);
    while (stack.Count > 0)
    {
        T vertex = stack.Pop();
        if (!visited.Add(vertex))
        {
            continue; // the stack may hold more than one copy
        }

        order.Add(vertex);
        IReadOnlyList<T> neighbors = graph.Neighbors(vertex);
        for (int i = neighbors.Count - 1; i >= 0; i--)
        {
            if (!visited.Contains(neighbors[i]))
            {
                stack.Push(neighbors[i]);
            }
        }
    }

    return order;
}

DFS: ada, alan, edsger, barbara, grace

In BFS Grace comes second (1 step), in DFS last: it goes down from Alan to Edsger and on to Barbara before coming back. One subtlety: in DFS we mark a vertex when we pop it from the stack, in BFS when we add it to the queue. In DFS this is needed to keep the order identical to the recursive version; the price is that the stack may hold more than one copy of the same vertex. The test verifies that both versions produce the same order.

Connected Components

In an undirected graph, groups of vertices connected to each other by paths are connected components. If we start a BFS from every vertex not seen yet, each BFS finds one component:

public static List<List<T>> ConnectedComponents<T>(Graph<T> graph) where T : notnull
{
    List<List<T>> components = [];
    HashSet<T> seen = [];
    foreach (T vertex in graph.Vertices)
    {
        if (seen.Contains(vertex))
        {
            continue;
        }

        List<T> component = [.. Distances(graph, vertex).Keys];
        seen.UnionWith(component);
        components.Add(component);
    }

    return components;
}

The total cost is still O(V + E), because every vertex enters exactly one BFS. In the Bookstore this can find disconnected reader groups in a "books bought together" graph, or separate independent pieces of the table relationship graph before a data migration. In the 18th post of the series we will see Union-Find, which answers the same question while edges arrive one at a time.

Seeing a Grid as an Implicit Graph

Not every graph has to be built explicitly. In a grid like a warehouse floor plan every cell is a vertex and its neighbors are the cells in four directions; we compute adjacency instead of storing it. The classic "count the islands" problem (count the shelf blocks) is a flood fill:

private static readonly (int Dr, int Dc)[] Directions = [(-1, 0), (1, 0), (0, -1), (0, 1)];

public static int CountIslands(string[] map)
{
    int rows = map.Length, cols = map[0].Length, islands = 0;
    bool[,] visited = new bool[rows, cols];
    for (int r = 0; r < rows; r++)
    {
        for (int c = 0; c < cols; c++)
        {
            if (map[r][c] == '#' && !visited[r, c])
            {
                islands++;
                Fill(map, visited, r, c);
            }
        }
    }

    return islands;
}

public static int Fill(string[] map, bool[,] visited, int startRow, int startCol)
{
    char target = map[startRow][startCol];
    Queue<(int R, int C)> queue = new();
    queue.Enqueue((startRow, startCol));
    visited[startRow, startCol] = true;
    int size = 0;
    while (queue.Count > 0)
    {
        (int r, int c) = queue.Dequeue();
        size++;
        foreach ((int dr, int dc) in Directions)
        {
            int nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < map.Length && nc >= 0 && nc < map[0].Length
                && !visited[nr, nc] && map[nr][nc] == target)
            {
                visited[nr, nc] = true;
                queue.Enqueue((nr, nc));
            }
        }
    }

    return size;
}

[Fact]
public void CountIslands_CountsConnectedLandCells()
{
    string[] map =
    [
        "##..#",
        "#...#",
        "..#..",
        ".....",
        "##.##",
    ];
    Assert.Equal(5, GridGraph.CountIslands(map));
}

Test run summary: Passed!
  total: 5
  failed: 0
  succeeded: 5
  skipped: 0
  duration: 430ms

In a grid, a bool[,] visited array instead of a HashSet is both fast and memory friendly. We deliberately wrote the flood fill with BFS: a flood fill written with recursive DFS goes a million frames deep on a single 1000 × 1000 area and crashes the process.

Measurement: BFS with a List and a Matrix

I built a sparse graph with 5,000 vertices (a ring plus two random edges from every vertex, about 15,000 edges) and ran the same BFS on both representations. The matrix version scans the whole row for every vertex:

[Benchmark]
public int AdjacencyMatrix()
{
    bool[] seen = new bool[V];
    Queue<int> queue = new();
    queue.Enqueue(0);
    seen[0] = true;
    int count = 0;
    while (queue.Count > 0)
    {
        int v = queue.Dequeue();
        count++;
        for (int u = 0; u < V; u++) // a matrix has to scan the whole row
        {
            if (_matrix[v, u] && !seen[u])
            {
                seen[u] = true;
                queue.Enqueue(u);
            }
        }
    }

    return count;
}

The measurements were taken on an Apple M5 (10 cores), macOS 27.0.1, .NET 10.0.13 and BenchmarkDotNet 0.15.8. I ran the benchmarks one at a time, but other work was running on the machine; look at the ratios, not the absolute numbers.

| Method          | V    | Mean        | Ratio | Allocated |
|---------------- |----- |------------:|------:|----------:|
| AdjacencyList   | 5000 |    309.1 us |  1.00 | 542.67 KB |
| AdjacencyMatrix | 5000 | 14,364.1 us | 46.52 |  37.19 KB |

The matrix is 46 times slower: it looks at 5,000 × 5,000 = 25 million cells, while the list looks only at the roughly 30,000 adjacency entries that actually exist (undirected, both directions). The list version allocates more because Distances returns a Dictionary as its result; the matrix itself sits in memory outside the measurement as a 24 MB array.

Production Notes

If the graph lives in a database, think before pulling it into memory. Queries like "all subcategories of this category" run inside the database in a BFS-like way with a recursive CTE (Common Table Expression) in SQL (Structured Query Language); we saw how to write that with EF (Entity Framework) Core in the EF Core series. Loading a follow graph with millions of edges into memory on every request is both slow and expensive.

End-to-end "how many steps away" questions explode quickly in a social graph: with 200 follows on average, a distance of 3 can touch up to 200³ = 8 million vertices. Bidirectional BFS (starting from both ends at once and meeting in the middle) or limiting the depth (say at most 3 steps) is a practical necessity. If the graph itself is huge and queries are always about relationships, a relationship-oriented graph database is worth considering too.

Do not change the graph during a traversal. If another thread adds or removes follows while a BFS is running, the List<T> enumerator throws an exception or gives inconsistent results. Either traverse an immutable snapshot of the graph or synchronize reads and writes.

Recursion and user data. If users determine the shape of the graph (nested categories, comment chains), a recursive DFS lets an attacker crash the process with a single long chain. Write it iteratively or set a depth limit.

Common Pitfalls

Marking visited when dequeuing instead of when enqueuing. The answer to the opening question, together with the grid version of the same comparison:

10x10 grid: mark on enqueue = 100 enqueues, mark on dequeue = 181 enqueues
100x100 grid: mark on enqueue = 10,000 enqueues, mark on dequeue = 19,801 enqueues
300x300 grid: mark on enqueue = 90,000 enqueues, mark on dequeue = 179,401 enqueues
complete graph, 2,000 users: mark on enqueue = 2,000 enqueues, mark on dequeue = 1,999,001 enqueues

When marked on dequeue, a vertex that has not been processed yet gets added to the queue again and again by every vertex adjacent to it. On a grid that is twice the work; in the graph where everyone follows everyone it is about 2 million additions instead of 2,000: O(E) instead of O(V). Since the result is still correct, this bug passes the tests and only shows up as memory and time on large data. The BFS rule: mark when you enqueue.

Adding an undirected edge in one direction only. If you add the road between two cities only with adjacency[a].Add(b), you cannot get from b to a and BFS thinks some vertices are "unreachable". A single method like AddEdge plus a Directed flag centralizes this mistake.

Forgetting unreachable vertices. Distances returns only the reached vertices; distance["linus"] throws a KeyNotFoundException. The calling code should use TryGetValue, or an explicit value should be produced for "infinity".

Using BFS on a weighted graph. BFS finds the fewest edges, not the lowest total cost. If shipping costs differ, you need Dijkstra; the 17th post of the series.

A Small Experiment

★☆☆ Change Distances to take a maxDepth parameter and produce the list of "users at most 2 steps away from Ada". In the follow graph Barbara should not be in the list.

★★☆ Write a bidirectional BFS: start one BFS from the start and one from the target at the same time, expand the smaller frontier at each step, and stop when the two sides meet. On a random 100,000-vertex graph with 50 neighbors on average, compare the number of vertices examined with one-directional BFS.

★★★ Write the grid flood fill with recursive DFS and run it on a single 2000 × 2000 area. Watch how the process ends, then try the same on a thread with a large stack via new Thread(..., maxStackSize), and note why this is a postponement rather than a fix.

We learned to traverse graphs with BFS and DFS. In the next post we look at a problem where a cycle in a directed graph is an error: in what order should the projects in a solution be built, in what order should seed data be inserted according to foreign keys? The answer is topological sort and Kahn's algorithm.