Source code online books for professionals by professionals

Breadth-first search (BFS). Traversing a graph (possibly a tree) level by level, thereby also identifying (unweighted) 
shortest path. Implemented by using a FIFO queue to keep track of discovered nodes. Running time Q(n+m).  
(See Listing 5-9.)
Bucket sort. Sort numerical values that are evenly (uniformly) distributed in a given interval by dividing the interval 
into n equal-sized buckets and placing the values in them. Expected bucket size is constant, so they can be sorted with 
(for example) insertion sort. Total running time Q(n). (See Chapter 4.)

---

Appendix B 
■
 List of proBLems And ALgorithms
263
Busacker–Gowen. Finds the cheapest max-flow (or the cheapest flow with a given flow value) in a network by using 
the cheapest augmenting paths in the Ford–Fulkerson approach. These paths are found using Bellman–Ford or (with 
some weight adjustments) Dijkstra’s algorithm. The running time in general depends on the maximum flow value and 
so is pseudopolynomial. For a maximum flow of k, the running time is (assuming Dijkstra’s algorithm is used)  
O(km lg n). (See Listing 10-5.)