Graph Traversal & Shortest Paths lab report

1. Title and aim

Empirical Analysis of Graph Algorithms: Breadth-First Search (BFS), Depth-First Search (DFS), Adjacency Representations, and Dijkstra's Shortest Path Complexity. To investigate fundamental graph representations (Adjacency Matrix vs. Adjacency List), evaluate the asymptotic time and space complexity of Breadth-First Search (BFS) and Depth-First Search (DFS), analyze edge relaxation mechanics in Dijkstra's Single-Source Shortest Path algorithm, and verify the linear scaling law T(|V|) = |V| + |E| = 5.0000·|V| across sparse networks with average degree d = 4.

2. Abstract

Seven benchmark trials were generated across network sizes |V| = 50 to |V| = 1000 vertices in a connected network with average out-degree d = 4 edges/vertex (|E| = 200 to |E| = 4000 edges, traversal operations T from 250 to 5000 operations). An ordinary least-squares regression of traversal operations against vertex count yielded an empirical complexity scaling coefficient of 5.0000 operations/vertex, demonstrating exact agreement with the linear Adjacency List bound (difference = 0.0000%). The empirical telemetry proves that Breadth-First Search (BFS) and Depth-First Search (DFS) achieve optimal linear O(|V| + |E|) complexity on Adjacency Lists, outperforming quadratic Adjacency Matrix representations by over 200× at |V| = 1000 vertices.

3. Apparatus and fixed settings

• Adjacency List Graph Engine: Allocates an array of |V| dynamic neighbor vectors, providing optimal O(1) neighbor iteration per edge with zero unused matrix memory.
• Adjacency Matrix Bitfield Memory Array: Simulates a dense |V| × |V| 2D array to evaluate memory footprint scaling (Θ(V²)) and compare O(1) edge lookup vs. O(V) neighbor scan latency.
• Frontier Queue & Activation Stack Unit: Implements dual-mode FIFO queue (for BFS level-order exploration) and LIFO activation stack (for DFS back-edge discovery) with visited bitfield sets.
• Min-Heap Indexed Priority Queue (Dijkstra): Maintains tentative shortest path distances supporting O(log V) extract_min and O(log V) decrease_key operations via an inverted vertex index map.
• Edge Relaxation & Predecessor Tracker: Evaluates the triangular inequality dist[v] > dist[u] + w(u, v) during Dijkstra execution, updating predecessor pointers to record the Shortest Path Tree.
• Cache Miss & Traversal Performance Telemetry Unit: Monitors discrete vertex discovery steps, edge exploration counts, CPU L1/L2 cache hit ratios, and memory bus transaction cycles during graph walks.
• Connected directed graph G = (V, E) generated with uniform pseudo-random topology and constant average out-degree d = 4 edges/vertex (|E| = 4|V|).
• Adjacency List memory representation utilizing contiguous dynamic vectors to minimize pointer overhead while avoiding quadratic matrix storage.
• Non-negative integer edge weights w(u, v) ∈ [1, 20] assigned uniformly to all directed edges for Dijkstra shortest path validation.
• Deterministic operation counter recording cumulative vertex discovery pushes and edge inspection scans across complete connected traversals.

4. Theory and graph choice

Graph theory forms the core mathematical language of computer science, modeling complex networked systems ranging from internet routing backbones and social networks to compiler dependency graphs and state-space search engines. Formally, a graph G = (V, E) consists of a set of vertices V and a set of edges E representing pairwise relationships. The efficiency of graph algorithms is governed by underlying memory representation: (1) Adjacency Matrices represent graphs as a |V| × |V| 2D array, enabling strict O(1) edge existence queries at the cost of quadratic Θ(|V|²) memory and Θ(|V|²) neighbor scanning overhead—a catastrophic penalty for sparse real-world graphs where |E| << |V|²; and (2) Adjacency Lists store an array of |V| linked neighbor sequences, optimizing memory consumption to optimal Θ(|V| + |E|) and allowing neighbor iterations proportional to vertex degree. The fundamental traversal algorithms—Breadth-First Search (BFS) using a FIFO queue and Depth-First Search (DFS) using a LIFO stack—visit every reachable vertex exactly once and inspect every incident directed edge exactly once, establishing the canonical linear time complexity bound T(V, E) = Θ(|V| + |E|). In a connected sparse network with average out-degree d = 4, edge count scales strictly as |E| = 4|V|, yielding an exact deterministic operation count T(|V|) = |V| + 4|V| = 5.0000·|V| operations. For weighted graphs with non-negative edge costs, Dijkstra's algorithm utilizes a Min-Heap Priority Queue to compute Single-Source Shortest Paths by repeatedly extracting the vertex with minimal tentative distance and greedily relaxing outgoing edges, achieving O((|V| + |E|) log |V|) complexity. Benchmarking graph traversal across varying network scales validates the linear scaling theorem and provides crucial insights into memory hierarchy locality, cache line prefetching, and modern Compressed Sparse Row (CSR) architectures.

The mathematical regression fits the linear model y = mx + b, where x = |V| represents the graph vertex count in vertices, y = T represents total elementary traversal operations, m represents the complexity scaling factor k_graph, and b represents the baseline operation offset (theoretically b = 0.0000 operations). The gradient has physical units operations/vertex.

5. Method

1. Construct a connected directed graph G = (V, E) with |V| vertices and average out-degree d = 4 edges per vertex (|E| = 4|V|). Verify network connectivity using Tarjan's strongly connected components algorithm to ensure all vertices are reachable from source s = 0.
2. Allocate an array of |V| head pointers. Populate neighbor vectors with directed edge endpoints and positive integer weights w(u, v) ∈ [1, 20] chosen from a uniform pseudo-random distribution.
3. Designate vertex s = 0 as the source. Clear visited bitmask flags. Initialize distance array dist[s] = 0 and dist[v] = ∞ for all v ≠ s. Enqueue the source vertex into the traversal frontier register.
4. Execute the traversal loop: in each step, dequeue the active vertex u from the frontier, mark u as visited, and increment the vertex visit counter. Iterate through all out-edges (u, v) incident to u, incrementing the edge inspection counter and enqueuing unvisited neighbors.
5. Repeat traversal benchmarking across vertex scales |V| ∈ [50, 100, 200, 300, 500, 750, 1000] vertices (corresponding to edge counts |E| ∈ [200, 400, 800, 1200, 2000, 3000, 4000]). Record total elementary operations T(|V|) = |V| + |E|.
6. Regress total operations T(|V|) against vertex count |V|. Calculate regression slope k_graph, intercept b, coefficient of determination R², and standard errors to verify the asymptotic complexity bound Θ(|V| + |E|) = 5.0000·|V|.

6. Observations and calculation table

All benchmark observations use strictly controlled memory buffers. Values are recorded deterministically from the algorithmic comparator register. Residuals are computed relative to the ordinary least-squares regression line.

Download the sample observations (CSV) ↓

7. Worked calculation for one observation

8. Graph, gradient and final calculation

Circular markers represent empirical benchmark observations. The solid line represents the ordinary least-squares asymptotic linear fit.

9. Uncertainty and comparison

Percentage difference = |estimate − theoretical value| / |theoretical value| × 100 = 0.0000%.

For n = 7 benchmark observations, Σresidual² = 5.8484e-25; s² = Σresidual²/(n − 2). Gradient standard error = √[s²/Σ(x − x̄)²] = 3.9398e-16. Intercept standard error = √[s²(1/n + x̄²/Σ(x − x̄)²)] = 2.0821e-13.

Propagating the fit parameters yields a fit standard error of 3.9398e-16 operations/vertex, with an ideal coefficient of determination R² = 1.000000.

In discrete graph algorithm analysis, the elementary operation count T(|V|) = |V| + |E| = 5.0000·|V| for Adjacency List BFS/DFS traversal is an exact combinatorial identity for 4-regular networks. Unlike continuous physical instrumentation, there is no analog sensor noise, thermal drift, or calibration variance in counting discrete vertex queue pushes or edge iterations. However, in physical semiconductor microprocessors, wall-clock graph traversal latency is strongly modulated by memory hierarchy and pipeline dynamics: (1) Pointer chasing cache line misses: in linked adjacency lists, vertex neighbor sequences reside at non-contiguous heap addresses, causing cold CPU L1/L2 data cache stalls (~100–250 CPU cycles) once graph footprint exceeds cache capacity; (2) Hardware spatial prefetcher failure: non-linear graph topologies prevent hardware stream prefetchers from predicting memory accesses, giving contiguous Compressed Sparse Row (CSR) arrays a 3× to 5× throughput advantage over linked lists; (3) Branch predictor mispredictions during neighbor iteration loops and visited bitmask checks (`if (!visited[v])`), which stall superscalar execution pipelines by 15–20 clock cycles; and (4) Priority queue overhead in Dijkstra's algorithm: min-heap extract_min and decrease_key operations introduce an additional log|V| factor, scaling execution time to O((|V| + |E|) log |V|). Ordinary least-squares linear regression of observed traversal operations against vertex count |V| across networks from 50 to 1000 vertices yields an empirical scaling slope k_graph = 5.0000 operations/vertex with zero residual variance (R² = 1.00000), verifying the linear time complexity bound Θ(|V| + |E|) with mathematical certitude.

10. Result and discussion

The empirical benchmark observations provide rigorous quantitative verification of the fundamental linear scaling theorem governing graph traversals. In an Adjacency List representation, every vertex is discovered and enqueued exactly once (|V| operations), and every incident directed edge is traversed exactly once during neighbor exploration (|E| = 4|V| operations). The total operation count T(|V|) = |V| + 4|V| = 5|V| scales in strict linear proportion to network size. The regression slope m = 5.0000 confirms this invariant with zero residual variance (R² = 1.00000). Comparative analysis across graph representations highlights critical systems trade-offs: an Adjacency Matrix requires Θ(|V|²) memory (1 million entries at |V| = 1000) and forces neighbor iterations to scan all |V| columns (taking 1,000,000 operations), whereas an Adjacency List consumes only Θ(|V| + |E|) memory (5,000 elements) and completes traversal in 5,000 operations—a 200-fold performance advantage. Furthermore, the Dijkstra sandbox demonstrates how greedy edge relaxation computes Single-Source Shortest Paths in O((|V| + |E|) log |V|) time using a Min-Heap, illustrating why non-negative edge weights are mathematically required to preserve the greedy choice property. Finally, the investigation explores modern Compressed Sparse Row (CSR) formats, showing how contiguous array packing eliminates pointer chasing and maximizes CPU L1 cache utilization.

11. Precautions and limitations

• Always maintain an explicit visited bitmask or color array during graph traversal to prevent infinite loops when walking graphs containing directed or undirected cycles.
• Never execute Dijkstra's algorithm on graphs with negative edge weights; verify all edge weights w(u, v) ≥ 0, or use the Bellman-Ford algorithm which detects negative weight cycles in O(V·E) time.
• When implementing Dijkstra with priority queues, maintain an inverted vertex index array to support O(log V) decrease_key operations, or use lazy deletion (ignoring stale entries when popped) to avoid heap corruption.
• For massive sparse graphs where |V| > 100,000, avoid Adjacency Matrix representations as a 100,000 × 100,000 matrix consumes 10 GB of RAM; use Compressed Sparse Row (CSR) or Adjacency Lists.

The simulated execution environment models idealized graph traversal where memory operations execute with deterministic cost T(|V|) = |V| + |E|. In physical microprocessors, traversal latency is modulated by CPU L1/L2 data cache hit ratios during pointer chasing across non-contiguous adjacency nodes, Translation Lookaside Buffer (TLB) virtual memory page walks, branch predictor stalls during neighbor iteration termination, and DRAM memory bus contention. In an Adjacency List representation of a graph G = (V, E), Breadth-First Search (BFS) and Depth-First Search (DFS) guarantee that every vertex is discovered and enqueued/pushed exactly once (|V| operations) and every incident directed edge is traversed exactly once (|E| operations). In a network with average out-degree d = 4, total edges |E| = 4|V|, yielding total elementary operations T(|V|) = |V| + |E| = (1 + 4)|V| = 5.0000·|V| operations with zero intercept T_0 = 0.0000.

12. Conclusion

This laboratory investigation quantitatively verified the memory representations, traversal dynamics, and asymptotic scaling of Graph Algorithms. Through systematic benchmarking across networks from |V| = 50 to 1000 vertices, we verified the empirical traversal scaling factor k_graph = 5.0000 operations/vertex with an ideal R² = 1.00000. The investigation established the microarchitectural superiority of sparse adjacency structures over dense matrices, proving why Adjacency Lists, Compressed Sparse Row (CSR), and Min-Heap priority queues form the core computational engine of network routing protocols, social network graphs, and large-scale distributed analytics.