4.3.1.1 - Breadth-first and depth-first graph traversal (VB.NET)

Breadth-first search with a queue

Breadth-first search explores all vertices one edge from its start before vertices two edges away, then three edges away, and so on.

Use a queue, which removes the earliest inserted vertex first. Mark a vertex as discovered when it is put in the queue, so two neighbours cannot schedule it twice. Removing it means processing it: record its visit and inspect its neighbours. A discovered vertex may still be waiting to be processed.

This undirected graph has vertices numbered A=0, B=1, C=2, D=3 and E=4. The adjacency lists are in alphabetical order. The order matters when several neighbours are eligible.

[DIAGRAM: asset_slug: traversal_graph; description: Exact five-vertex graph used to trace breadth-first and depth-first visits]

Starting at A, put A in the queue and discover it. Then:

The processing order is A, B, C, D, E. D was already discovered by B when C's list reached it. The edge C–D therefore does not insert another D.

Imports System.Collections.Generic

Module Program
    Function BreadthFirst(graph As Integer()(), start As Integer) As List(Of Integer)
        Dim seen(graph.Length - 1) As Boolean
        Dim work As New Queue(Of Integer)()
        Dim order As New List(Of Integer)()
        seen(start) = True
        work.Enqueue(start)
        While work.Count > 0
            Dim node As Integer = work.Dequeue()
            order.Add(node)
            For Each neighbour As Integer In graph(node)
                If Not seen(neighbour) Then
                    seen(neighbour) = True
                    work.Enqueue(neighbour)
                End If
            Next
        End While
        Return order
    End Function
End Module

The input is a nonempty adjacency-list array with valid vertex indices and a valid start. The function returns only the reachable component. To visit a disconnected graph completely, start another traversal at each vertex still undiscovered.

Depth-first search and backtracking

Depth-first search follows one branch as far as possible before returning to a vertex that has an unexplored neighbour.

A stack removes the most recently inserted item first. Recursion uses the call stack to remember unfinished visits. In the following procedure, the current call resumes its neighbour loop when a recursive call returns. Mark before exploring neighbours; otherwise a cycle such as A–B–D–C–A could recurse indefinitely.

Sub DepthFirst(graph As Integer()(), node As Integer,
               seen As Boolean(), order As List(Of Integer))
    seen(node) = True
    order.Add(node)
    For Each neighbour As Integer In graph(node)
        If Not seen(neighbour) Then
            DepthFirst(graph, neighbour, seen, order)
        End If
    Next
End Sub

Place this procedure in a module with Imports System.Collections.Generic. The caller creates a false-filled seen array and an empty List(Of Integer), then calls DepthFirst(graph, 0, seen, order) with the graph above. The visit order is A, B, D, C, E. A pauses while B is explored; B pauses at D; D reaches C; C reaches E. After E returns, C has no new neighbour, so the calls return in turn.