7.23. 总结

7.23. Summary

中文英文

在本章中，我们探讨了图的抽象数据类型和一些图的实现。图使我们能够解决许多问题——前提是我们能够将原始问题转换为可以用图表示的形式。特别是，我们看到图在以下一般领域中非常有用：

• 广度优先搜索用于查找无权最短路径。
• Dijkstra 算法用于加权最短路径。
• 深度优先搜索用于图的探索。
• 强连通分量用于简化图。
• 拓扑排序用于任务排序。
• 最小权重生成树用于广播消息。

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.

---

最后更新: 2024年9月13日
创建日期: 2024年9月9日