4.3.1.1 - Breadth-first and depth-first graph traversal (C#)

Breadth-first search and queues

Breadth-first search (BFS) explores the starting vertex, then its immediate neighbours, then vertices two edges away, and so on. A first-in, first-out queue stores discovered vertices waiting to be processed.

Use this undirected graph. The neighbour lists fix the order of choices; there is no universal alphabetical order unless the task specifies it.

[DIAGRAM: asset_slug: graph-traversal; description: Undirected graph with edges A–B, A–C, B–D, B–E, C–E and E–F.]

Start by marking A discovered and enqueueing it. Repeatedly dequeue the front vertex, output it and enqueue each not-yet-discovered neighbour, marking that neighbour immediately. The queue below shows its front on the left.

The output is A, B, C, D, E, F. C does not enqueue E again because B already discovered it. In an unweighted graph, the first discovery of a vertex gives a path using the fewest edges from the start. Store its parent at discovery to reconstruct that path; BFS gives A–B–E–F as a shortest path to F here.

This complete static C# example uses integer labels A=0 through F=5. Queue<int>.Dequeue() removes the oldest item and Count controls termination.

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        int[][] graph = {
            new[] { 1, 2 }, new[] { 0, 3, 4 }, new[] { 0, 4 },
            new[] { 1 }, new[] { 1, 2, 5 }, new[] { 4 }
        };
        bool[] discovered = new bool[graph.Length];
        Queue<int> pending = new Queue<int>();
        discovered[0] = true;
        pending.Enqueue(0);
        while (pending.Count > 0)
        {
            int vertex = pending.Dequeue();
            Console.WriteLine((char)('A' + vertex));
            foreach (int neighbour in graph[vertex])
                if (!discovered[neighbour])
                {
                    discovered[neighbour] = true;
                    pending.Enqueue(neighbour);
                }
        }
    }
}

Depth-first search and stacks

Depth-first search (DFS) follows one branch as far as possible before returning to an earlier choice. A last-in, first-out stack supports this return; recursion uses the call stack for the same purpose.

In recursive DFS, mark and output the current vertex, then recursively visit each undiscovered neighbour in the stated list order. If all neighbours are already discovered, return to the previous call. Using the graph above, visit A, then B, then D; D returns to B, which next visits E, then C, then F. The output is A, B, D, E, C, F.

static void DepthFirst(int[][] graph, int vertex, bool[] discovered)
{
    discovered[vertex] = true;
    Console.WriteLine((char)('A' + vertex));
    foreach (int neighbour in graph[vertex])
        if (!discovered[neighbour])
            DepthFirst(graph, neighbour, discovered);
}