Loading page…
Master the fundamental concepts of cache optimization through this focused micro-challenge.
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.
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.
cLoading…
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.
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.
Implement cache-friendly BFS using level-by-level traversal.
Requirements:
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it works