问题

使用图结构可以解决很多问题。本章我们只是讨论其中一些，不过你仍然有机会寻找到一些我们没有讨论的问题，然后去研究。给定一个用边来定义的图，很多问题会和图中两顶点之间的最短路径相关，路的长度就是路上边的长度之和。在“单源最短路径”这个问题（例6-6）上，给定一个顶点s，我们需要计算出到图中其他所有顶点的最短路径。在“对顶点间最短路径”问题（例6-7）中，我们需要计算图中所有的顶点对（u,v）之间的最短路径。有些问题则是在更加深入地使用了图的结构。我们可以从一个图中构造出一个最小生成树（MST），最小生成树是一个无向有权图，是原图边的一个子集，但是，原图的顶点仍然是连通的，而边的权值总和最小。在本章稍后部分，“最小生成树算法”一节，我们将会描述如何高效地解决这个问题。

我们首先从如何探索图开始讨论。两个最常使用的搜索方法是深度优先搜索（DFS）和广度优先搜索（BFS）。