Graphs

Build a Graph as an Adjacency List

Represent an undirected graph as a per-vertex list of neighbours. For every edge (u, v), record v as a neighbour of u and u as a neighbour of v. Neighbour lists keep insertion order so the graph is a stable, deterministic fixture for the search lessons.

Algorithm

The canonical fixture is 6 vertices [1..6] with undirected edges (1,2), (1,3), (2,4), (3,4), (4,5), (5,6) inserted in that order. The final adjacency list is {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3, 5], 5: [4, 6], 6: [5]}. This same graph drives graph-bfs, graph-dfs, and graph-shortest-path-bfs.

adjacency list Each edge adds two directed entries, one in each direction.

Visual walkthrough

The graph fixture is pinned once, then the adjacency list writes each undirected edge in both directions.

Step 1 - Pinned graph fixture

The six vertices and six undirected edges are the shared fixture for BFS and DFS.

Graph with edges (1,2), (1,3), (2,4), (3,4), (4,5), (5,6).123456

Step 2 - Final adjacency list

Each row lists neighbours in the same insertion order used by the lesson.

Adjacency list after all six undirected edges are inserted.vertexneighbours1[2, 3]2[1, 4]3[1, 4]4[2, 3, 5]5[4, 6]6[5]

Basic Implementation

basic.f90 
program graph_adjacency_list
    implicit none
    integer, parameter :: N = 6, M = 6
    integer :: edges(M, 2)
    integer :: adj(N, 3)
    integer :: adj_len(N)
    integer :: e, u, w, v, i, pos
    character(len=256) :: line
    character(len=16) :: piece

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

    adj = 0
    adj_len = 0
    do e = 1, M
        u = edges(e, 1)
        w = edges(e, 2)
        adj_len(u) = adj_len(u) + 1
        adj(u, adj_len(u)) = w
        adj_len(w) = adj_len(w) + 1
        adj(w, adj_len(w)) = u
    end do

    pos = 0
    call append(line, pos, '{')
    do v = 1, N
        if (v > 1) call append(line, pos, ', ')
        write (piece, '(I0)') v
        call append(line, pos, trim(piece))
        call append(line, pos, ': [')
        do i = 1, adj_len(v)
            if (i > 1) call append(line, pos, ', ')
            write (piece, '(I0)') adj(v, i)
            call append(line, pos, trim(piece))
        end do
        call append(line, pos, ']')
    end do
    call append(line, pos, '}')
    print '(A)', line(1:pos)
contains
    subroutine append(str, p, frag)
        character(len=*), intent(inout) :: str
        integer, intent(inout) :: p
        character(len=*), intent(in) :: frag
        str(p + 1:p + len(frag)) = frag
        p = p + len(frag)
    end subroutine append
end program graph_adjacency_list

Complexity

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

Implementation notes

  • Fortran: a fixed adj(N, 3) array with a per-vertex adj_len count stores neighbours in edge order; an internal append subroutine builds the output string.
  • The replay shows the adjacency list as the edges are processed, matching the lesson spec.