9.23. Summary¶

In this chapter we have looked at the graph abstract data type, and some implementations of a graph. A graph enables us to solve many problems provided we can transform the original problem into something that can be represented by a graph. In particular, we have seen that graphs are useful to solve problems in the following general areas.

Breadth first search for finding the unweighted shortest path.
Dijkstra’s algorithm for weighted shortest path.
Depth first search for graph exploration.
Strongly connected components for simplifying a graph.
Topological sort for ordering tasks.
Minimum weight spanning trees for broadcasting messages.