Depth-First Search (Recursive)

Visit a start vertex, then recurse into its first unvisited neighbour all the way down before backtracking. A visited set prevents revisiting, and neighbour insertion order fixes the visit sequence.

Algorithm

Basic Implementation

basic.f90

program graph_dfs
    implicit none
    integer, parameter :: N = 6
    integer :: adj(N, 3) = 0
    integer :: adj_len(N)
    integer :: visited(N)
    integer :: order(N)
    integer :: order_count, i

    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
    order_count = 0

    call dfs(1)

    print '(*(I0,1X))', (order(i), i = 1, order_count)
contains
    recursive subroutine dfs(v)
        integer, intent(in) :: v
        integer :: k, nb
        visited(v) = 1
        order_count = order_count + 1
        order(order_count) = v
        do k = 1, adj_len(v)
            nb = adj(v, k)
            if (visited(nb) == 0) then
                call dfs(nb)
            end if
        end do
    end subroutine dfs
end program graph_dfs

DFS follows the first unvisited neighbour as far as it can, then unwinds and tries the next branch.

Step 1 - First branch

Starting from 1, insertion order sends DFS to 2, then 4, then 3.

Step 2 - Full DFS order

The final order is [1, 2, 4, 3, 5, 6], then calls unwind 6 -> 5 -> 4 -> 3 -> 2 -> 1.

Complexity

Time: O(V + E)
Space: O(V) recursion depth

Implementation notes

Fortran: a recursive subroutine dfs host-associates the adj, visited, and order arrays; the visit order prints space-separated.
The replay shows the current vertex, the visited set, and the running visit order after each entry, matching the lesson spec.

recursive descent Follow one branch to its end, then unwind and try the next neighbour.