Graph Foundations, Structural Variants & BFS/DFS Traversals

Unlike linear containers where input size is governed by a single parameter $n$, graph algorithms depend on two independent structural parameters: the vertex count $|V|$ and the edge count $|E|$. Formally, in set-builder notation:

In an undirected graph, the edge relation $E$ is a symmetric binary relation ($(v_i, v_j) \in E \iff (v_j, v_i) \in E$), whereas in a directed graph (digraph), $E$ is non-symmetric and edges are ordered pairs representing one-way arcs.

The structural constraints placed on $E$ determine the maximum possible number of edges, the formal Graph Density ($\text{density}(G) = |E| / \max(|E|)$), and which representation (Adjacency List vs Adjacency Matrix) is asymptotically superior.

VCE Pseudocode Conventions & The 3 Core Control Structures

Before writing graph traversal algorithms, the HESS notes standardise VCE Algorithmics Pseudocode around three fundamental control structures, using <- for variable assignment, Algorithm for the main procedure, Function for helper subroutines, and Display / Return for output:

Algorithm Mean(list):
    sum <- 0
    For each element in list do:
        sum <- sum + element
    End do
    mean <- sum / length(list)
    Return mean
End Algorithm

Breadth-First Search (BFS) traverses a graph layer-by-layer outward from a source vertex $s$ using a FIFO Queue. Because it explores all vertices at distance $k$ before discovering any vertex at distance $k+1$, BFS is guaranteed to find the shortest path in an unweighted graph (minimum number of edges).

• 3 Ways to Implement Node Marking (Visited State): To prevent infinite loops on cycles, visited vertices are marked using (1) a node attribute (e.g., v.visited = True), (2) a Boolean array indexed by vertex ID (visited[v] = True), or (3) a Hash Table / Set ADT (visited.add(v)).
• BFS Distance-Labelling Procedure ($s \to t$ Shortest Unweighted Path): Set level counter $i = 0$ and label source $s$ with $0$. In each pass, find all unlabelled vertices adjacent to any vertex labelled $i$, mark them with $i + 1$, and increment $i$ until target $t$ is marked.
• BFS Tree Edges & Back-Edges Reconstruct $G$: The edges traversed to discover unvisited vertices form a spanning tree (the BFS Tree, or a BFS Forest if repeated across an outer loop For each Node start_node in G on a disconnected graph). Edges leading to already-visited vertices are back-edges (or cross-edges); adding all non-tree back-edges back to the BFS/DFS spanning tree recovers the exact original graph $G$!

Algorithm BFS(G, root):
    let Q be a queue
    let T be a new Graph // BFS Tree
    mark root as visited
    Q.enqueue(root)
    While Q is not empty do:
        v <- Q.dequeue()
        For each w in G.adjacent(v) do:
            If w is not visited then:
                mark w as visited
                add edge (v, w) to T
                Q.enqueue(w)
            End If
        End For
    End While
    Return T
End Algorithm

import networkx as nx
from collections import deque

def bfs_tree(G: nx.Graph, startNode):
    visited = set([startNode])
    queue = deque([startNode])
    T = nx.Graph()
    T.add_node(startNode)

    while queue:
        v = queue.popleft()
        for w in G.neighbors(v):
            if w not in visited:
                visited.add(w)
                T.add_edge(v, w)
                queue.append(w)
    return T

Depth-First Search (DFS) plunges as deep as possible along each branch before backtracking. It can be written iteratively using an explicit LIFO Stack or recursively using the program call stack. In Python iterative DFS, calling neighbours.reverse() before pushing onto the stack ensures neighbours are popped and visited in the exact same natural order as recursive DFS. If the graph is disconnected, wrapping DFS in an outer loop For each Node start_node in G restarts traversal from unvisited vertices to produce a DFS Forest. Beyond basic traversal, DFS powers Topological Sorting (on DAGs), finding Strongly Connected Components, and testing $k$-partiteness (such as 2-colouring bipartite graphs).

Algorithm DFS_Iterative(G, start):
    let S be a stack
    S.push(start)
    While S is not empty do:
        v <- S.pop()
        If v is not visited then:
            mark v as visited
            For each w in G.adjacent(v) do:
                If w is not visited then:
                    S.push(w)
                End If
            End For
        End If
    End While
End Algorithm

Algorithm DFS_Recursive(G, v):
    mark v as visited
    For each u in G.adjacent(v) do:
        If u is not visited then:
            DFS_Recursive(G, u)
        End If
    End For
End Algorithm

DFS Time Complexity: Best, Average & Worst Case (Adjacency List vs Matrix)

In VCE Algorithmics exams, deriving the exact complexity of DFS requires accounting for both how the graph is stored and its edge density:

• Why Adjacency List is $\Theta(|V| + |E|)$: Initialising vertices takes $\Theta(|V|)$. Iterating through G.adjacent(v) across all visited vertices sums to $\sum_{v \in V} \deg(v) = 2|E|$. For a tree ($|E| = |V|-1$), this simplifies to $\Theta(|V|)$; for a complete graph, $\Theta(|V|^2)$.
• Why Adjacency Matrix is Always $\Theta(|V|^2)$: Finding the neighbours of each vertex $v$ requires scanning an entire matrix row of length $|V|$ regardless of how few edges $v$ actually has, costing $|V| \times |V| = \Theta(|V|^2)$ in Best, Average, and Worst cases.

Two essential applications of DFS in the HESS syllabus are testing whether an undirected graph is connected and detecting whether an undirected graph contains a cycle.

1. Graph Connectedness Check (Counting Visited Nodes)

Initialise a counter count <- 0 and run DFS (or BFS) starting from a single arbitrary vertex $v_0 \in V$, incrementing count each time a vertex is marked visited. After that single pass terminates, check whether count == |V| (or equivalently, whether the outer loop For each Node start_node in G executes only once). If count == |V|, $G$ is connected; otherwise, $G$ is disconnected.

2. Undirected Cycle Detection (The ancestor Parameter)

In an undirected graph, every edge $\{u, v\}$ appears in both $u$'s adjacency list and $v$'s adjacency list. When DFS moves from parent $u$ to child $v$, examining $v$'s neighbours will immediately see $u$ as already visited! However, going immediately back to the parent $u$ is not a cycle.

Therefore, undirected DFS cycle detection must pass an ancestor (parent) parameter: a cycle exists if and only if DFS encounters an adjacent vertex $w$ that is already visited AND $w \neq \text{ancestor}$.

Algorithm HasCycle(G):
    mark all vertices in G as unvisited

    Function DFS_Cycle(v, ancestor):
        mark v as visited
        For each u in G.adjacent(v) do:
            If u is not visited then:
                If DFS_Cycle(u, v) == True then:
                    Return True
                End If
            Else If u != ancestor then:
                // Visited neighbour that is NOT our immediate parent -> back-edge cycle!
                Return True
            End If
        End For
        Return False
    End Function

    For each v in G.vertices do:
        If v is not visited then:
            If DFS_Cycle(v, null) == True then:
                Return True
            End If
        End If
    End For
    Return False
End Algorithm

Best-First Search replaces the FIFO Queue of BFS and the LIFO Stack of DFS with a Priority Queue (open list) ordered by a heuristic evaluation function $f(n)$ that estimates the desirability of node $n$, alongside a closed list tracking visited nodes. In the HESS notes, typical heuristic factors combined into $f(n)$ include Proximity (estimated distance to goal), Cost (resource expenditure), and Danger (risk penalty). While fast in practice, pure Greedy Best-First Search is not guaranteed to find the shortest path because it ignores the path cost already incurred to reach $n$ (which is corrected by Dijkstra's and A* Search in Lesson 03).

Algorithm Best_First_Search(G, start, f):
    open <- PQueue(min or max) ADT
    closed <- List
    enqueue(open, start, f(start))
    While open is not empty do:
        current <- peek(open)
        dequeue(open)
        append(closed, current)
        For each neighbour in Adjacent(G, current) do:
            If neighbour not in closed and neighbour not in open then:
                enqueue(open, neighbour, f(neighbour))
            Else if neighbour in open then:
                // Update priority if a better heuristic path is found
                requeue(open, neighbour, f(neighbour))
            End if
        End do
    End do
    Return closed
End Algorithm

• I can state the maximum edge bounds for simple undirected ($|V|(|V|-1)/2$) and simple directed ($|V|(|V|-1)$) graphs, and the exact edge count of a tree ($|E| = |V| - 1$).
• I can write both BFS (Queue) and DFS (Iterative Stack & Recursive) in VCE pseudocode and explain why Adjacency Lists yield $\Theta(|V|+|E|)$ while Adjacency Matrices yield $\Theta(|V|^2)$.
• I can trace DFS undirected cycle detection using the ancestor parameter to distinguish genuine back-edges from parent tree-edges.