首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》问题

关灯直达底部

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

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