Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Support Runestone Academy Today

7.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 the 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.