Source code online books for professionals by professionals

Topological sorting. Order the nodes of a DAG so that all the edges point in the same direction. If the edges represent 
dependencies, a topological sorting represents an ordering that respects the dependencies. This problem can be 
solved by a form of reference counting (see Chapter 4) or by using DFS (see Chapter 5).
Traversal. The problem here is to visit all the objects in some connected structure, usually represented as nodes in a 
graph or tree. The idea can be either to visit every node or to visit only those needed to solve some problem. The latter 
strategy of ignoring parts of the graph or tree is called pruning and is used (for example) in search trees and in the 
branch and bound strategy. For a lot on traversal, see Chapter 5.
Algorithms and Data Structures
2-3-trees. Balanced tree structure, allowing insertions, deletions, and search in worst-case Q(lg n) time. Internal 
nodes can have two or three children, and the tree is balanced during insertion by splitting nodes, as needed.  
(See Chapter 6.)
A*. Heuristically guided single source shortest path algorithm. Suitable for large search spaces. Instead of choosing 
the node with the lowest distance estimate (as in Dijkstra’s), the node with the lowest heuristic value (sum of distance 
estimate and guess for remaining distance) is used. Worst-case running time identical to Dijkstra’s algorithm.  
(See Listing 9-10.)
AA-tree. 2-3-trees simulated using node rotations in a binary tree with level-numbered nodes. Worst-case running 
times of Q(lg n) for insertions, deletions, and search. (See Listing 6-6.)
Bellman–Ford. Shortest path from one node to all others in weighted graphs. Looks for a shortcut along every edge 
n times. Without negative cycles, correct answer guaranteed after n–1 iterations. If there’s improvement in the last 
round, a negative cycle is detected, and the algorithm gives up. Running time Q(nm). (See Listing 9-2.)