Implement Cache-Friendly BFS Using Level-by-Level Traversal

Breadth-First Search and Memory Bandwidth

Standard BFS with a FIFO queue chases pointers through adjacency lists, scattering memory access. Level-synchronous BFS batches all vertices at frontier depth d before moving to d+1, improving locality when you store edges in arrays and visit vertices in sorted order.

Level-by-Level Layout

Keep current_level[] and next_level[] arrays. For each vertex in the current level, scan its edge range [offset[v], offset[v+1]) in one contiguous block.

cCopy
Loading…

• CSR (compressed sparse row) format pairs naturally with level BFS
• Direction-optimizing BFS switches forward/backward search on large graphs
• Bitmap visited arrays reduce pointer chasing versus hash sets
• Graph size must exceed cache for gains to appear in timing

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement level-by-level BFS on a CSR graph and compare against a queue-based version. This exercise asks you to explain which representation reduced cache misses.