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 of activities on this page.