Tag
breadth-first-search
- May 8, 2025 Two-Colouring a Graph: Why BFS Decides Bipartiteness and Odd Cycles Do Not The equivalence between bipartite graphs and odd-cycle-free graphs, how a colouring traversal detects the failure in linear time, and what the check does not decide. algorithms
- Apr 9, 2025 Frontier Traversal When the Graph Exceeds Cache: Top-Down Against Bottom-Up Why breadth-first search becomes memory-bound on large graphs, how a bottom-up step inverts the loop over unvisited vertices, and when switching directions pays. algorithms
- Apr 8, 2024 Why Breadth-First Search Cannot Discover Vertices Out of Distance Order The queue invariant behind BFS distances, why vertices must be marked on enqueue rather than on dequeue, and where the layer argument stops holding. algorithms