Graphs

Breadth-First Search

From a start vertex, explore the graph layer by layer using a queue and a "visited" set. Dequeue a vertex, visit it, enqueue all unvisited neighbours. Visited is checked before enqueue so the queue stays bounded by V.

Algorithm

The canonical input is the 6-vertex undirected graph from graph-adjacency-list (defined inline here). Starting at vertex 1, the deterministic visit order is [1, 2, 3, 4, 5, 6].

Basic Implementation

basic.f90 
program graph_bfs
    implicit none
    integer, parameter :: N = 6
    integer :: adj(N, 3) = 0
    integer :: adj_len(N)
    integer :: visited(N)
    integer :: queue(N)
    integer :: order(N)
    integer :: head, tail, order_count, i, v, nb

    adj_len = [2, 2, 2, 3, 2, 1]
    adj(1, 1:2) = [2, 3]
    adj(2, 1:2) = [1, 4]
    adj(3, 1:2) = [1, 4]
    adj(4, 1:3) = [2, 3, 5]
    adj(5, 1:2) = [4, 6]
    adj(6, 1:1) = [5]

    visited = 0
    visited(1) = 1
    queue(1) = 1
    head = 1
    tail = 1
    order_count = 0

    do while (head <= tail)
        v = queue(head)
        head = head + 1
        order_count = order_count + 1
        order(order_count) = v
        do i = 1, adj_len(v)
            nb = adj(v, i)
            if (visited(nb) == 0) then
                visited(nb) = 1
                tail = tail + 1
                queue(tail) = nb
            end if
        end do
    end do

    print '(*(I0,1X))', (order(i), i = 1, order_count)
end program graph_bfs

Complexity

  • Time: O(V + E)
  • Space: O(V)

Implementation notes

  • Fortran: a small queue(N) array with two indices (head, tail) gives O(1) dequeue/enqueue without ever shifting elements. The visited(N) array indexed by vertex id doubles as the visited set. The adjacency is stored as a fixed adj(N, 3) matrix plus per-vertex adj_len(N) so the inner loop is do i = 1, adj_len(v).
  • The replay shows the dequeued vertex, the queue after, and the visited set after each step, matching the lesson spec.
layered exploration A queue processes the closest vertices first.