Algorithm Visualization
Speed:
Click "Reset" to initialize the algorithm, then "Step Forward" to see each step.
Distance 0
Distance 1
Distance 2
Distance 3
Current Node
Distance Array
Queue Array
■ Read Pointer
■ Write Pointer
Algorithm Theory
BFS Algorithm Steps (Newman Section 8.5.3)
1. Place starting node s in queue[0], set read pointer = 0, write pointer = 1. Set distance[s] = 0, all others = -1.
2. If read pointer == write pointer, algorithm finished. Otherwise, read node from read pointer position, increment read pointer.
3. Find distance d of current node from distance array.
4. For each neighbor: if distance unknown, set distance = d+1, add to queue at write pointer, increment write pointer.
5. Repeat from step 2.
Time Complexity Analysis
Setup: Initialize arrays - O(n)
Main loop: Each node processed once, examining O(m/n) neighbors on average
Total: O(n) × O(m/n) = O(m)
Overall: O(m + n)
Key insight: Each edge examined at most twice (once from each endpoint), giving optimal O(m + n) performance for unweighted shortest paths.
Queue Implementation Details
• Read pointer tracks next node to process
• Write pointer tracks next empty queue position
• When read == write, queue is empty (algorithm done)
• Nodes with same distance appear contiguously in queue