Graphs

Nievergelt & Hinrichs · Ch. 6 · Algorithms and Data Structures

A graph is vertices and edges. Represent it as an adjacency list (sparse) or adjacency matrix (dense). BFS explores level by level. DFS explores depth-first. Both run in O(V + E).

Adjacency list representation

Scheme

; Graph as adjacency list
; Each vertex maps to its list of neighbors

(define graph
  (list (list "A" "B" "C")
        (list "B" "A" "D" "E")
        (list "C" "A" "F" "G")
        (list "D" "B")
        (list "E" "B" "F")
        (list "F" "C" "E")
        (list "G" "C")))

(define (neighbors g v)
  (let ((entry (assoc v g)))
    (if entry (cdr entry) (list))))

(display "Neighbors of A: ") (display (neighbors graph "A")) (newline)
(display "Neighbors of B: ") (display (neighbors graph "B"))

Breadth-first search

BFS uses a queue. It visits all vertices at distance d before any at distance d+1. This gives shortest paths in unweighted graphs.

Scheme

; BFS: explore level by level using a queue

(define graph
  (list (list "A" "B" "C")
        (list "B" "A" "D" "E")
        (list "C" "A" "F" "G")
        (list "D" "B")
        (list "E" "B" "F")
        (list "F" "C" "E")
        (list "G" "C")))

(define (neighbors g v)
  (let ((entry (assoc v g)))
    (if entry (cdr entry) (list))))

(define (bfs g start)
  (let loop ((queue (list start))
             (visited (list start))
             (order (list)))
    (if (null? queue)
        (reverse order)
        (let* ((v (car queue))
               (rest (cdr queue))
               (nbrs (neighbors g v))
               (new (filter (lambda (n) (not (member n visited))) nbrs)))
          (loop (append rest new)
                (append visited new)
                (cons v order))))))

(display "BFS from A: ")
(display (bfs graph "A"))

Depth-first search

DFS uses a stack (or recursion). It explores as deep as possible before backtracking. Useful for topological sort, cycle detection, and connected components.

Scheme

; DFS: explore depth-first using recursion

(define graph
  (list (list "A" "B" "C")
        (list "B" "A" "D" "E")
        (list "C" "A" "F" "G")
        (list "D" "B")
        (list "E" "B" "F")
        (list "F" "C" "E")
        (list "G" "C")))

(define (neighbors g v)
  (let ((entry (assoc v g)))
    (if entry (cdr entry) (list))))

(define (dfs g start)
  (let loop ((stack (list start))
             (visited (list))
             (order (list)))
    (if (null? stack)
        (reverse order)
        (let ((v (car stack))
              (rest (cdr stack)))
          (if (member v visited)
              (loop rest visited order)
              (let ((nbrs (neighbors g v)))
                (loop (append nbrs rest)
                      (cons v visited)
                      (cons v order))))))))

(display "DFS from A: ")
(display (dfs graph "A"))

Neighbors

Cross-references

🔢 Discrete Math Ch.4 — graph theory: the mathematical foundations

← Trees by june.kim Shortest Paths →