7.23. 总结
.. Copyright (C) Brad Miller, David Ranum This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/.
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.
创建日期: 2023年10月10日