Source code online books for professionals by professionals

Kosaraju’s algorithm. Finds strongly connected components, using DFS. First, nodes are ordered by their finish 
times. Then the edges are reversed, and another DFS is run, selecting start nodes using the first ordering. Running 
time Q(n+m). (See Listing 5-11.)
Kruskal’s algorithm. Finds a minimum spanning tree by repeatedly adding the smallest remaining edge that doesn’t 
create a cycle. This cycle checking can (with some cleverness) be performed very efficiently, so the running time is 
dominated by sorting the edges. All in all, the running time is Q(m lg n). (See Listing 7-4.)
Linked lists. An alternative to arrays for representing sequences. Although linked lists are cheap (constant time) to 
modify once you’ve found the right entries, finding those normally takes linear time. Linked lists are implemented 
sort of like a path, with each node pointing to the next. Note that Python’s list type is implemented as an array, not a 
linked list. (See Chapter 2.)

---

Appendix B 
■
 List of proBLems And ALgorithms
265
Merge sort. The archetypal divide-and-conquer algorithm. It divides the sequence to be sorted in the middle, sorts 
the two halves recursively, and then merges the two sorted halves in linear time. The total running time is Q(n lg n). 
(See Listing 6-5.)