GraphsTraversalintro
Breadth-First Search
Explores the graph in expanding rings, visiting all nodes at distance k before any at distance k+1, using a FIFO queue. Finds the shortest path in terms of edge count on unweighted graphs.
- Best
- O(V+E)
- Average
- O(V+E)
- Worst
- O(V+E)
- Space
- O(V)