Skip to main content
Logo image

Problem Solving with Algorithms and Data Structures using Java The Interactive Edition

Section 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.
You have attempted 1 of 1 activities on this page.