图中所有顶点均被访问。事实上,深度优先搜索的结果是沿着图的某一分支搜索,直到它的 末端,然后回溯,沿着另一分支进行同样的搜索,依此类推。 (3)广度优先周游 广度优先周游的过程是:从图中的某个顶点ⅴ出发,访问并标记了顶点ⅴ之后,横向搜 索v的所有邻接点u1,u2,…,u。在依次访问v的各个未被访问的邻接点之后,再从这些 邻接点出发,依次访问与它们邻接的所有未曾访问过的顶点。重复上述过程直至图中所有与 源点ⅴ有路径相通的顶点都被访问为止。若G是连通图,则周游完成;否则,在图G中选 一个尚未访问的顶点作为新源点继续广度优先搜索。广度优先搜索是个非递归的过程,而深 度优先搜索是个递归的过程 (4)拓扑排序 有向图拓扑排序的步骤 (1)从有向图中选出一个没有前驱(入度为0)的顶点并输出它。 (2)删除图中该顶点和所有以它为起点的弧 不断重复上述两个步骤,会出现两种情形:要么有向图中顶点全部被输出,要么当前图 中不存在没有前驱的顶点。当图中的顶点全部输出时,就完成了有向无环图的拓扑排序;当 图中还有顶点没有输出时,说明有向图中含有环。可见拓扑排序可以检查有向图是否存在环。 (5)求所有顶点对之间最短路径的 Dijkstra算法 Dijkstra算法的基本思想是:把图的顶点集合化分成两个集合S和VS。第一个集合S 表示最短距离已经确定的顶点集,即一个顶点如果属于集合S当且仅当从源点s到该顶点的 最短路径已知。其余的顶点放在另一个集合VS中。初始时,集合S只包含源点,即S={s} 这时只有源点到自己的最短距离是已知的。设ⅴ是V中的某个顶点,把从源点s到顶点v 且中间只经过集合S中顶点的路径称为从源点到ⅴ的特殊路径,并用数组D来记录当前所 找到的从源点s到每个顶点的最短特殊路径长度。D的初始状态为:如果从源点s到顶点ⅴ 有弧则DⅣv]记为弧的权值;否则将DⅣ置为无穷大。 Dijkstra算法每次从尚未确定最短路径 长度的集合VS中取出一个最短特殊路径长度最小的顶点u,将u加入集合S,同时修改数 组D中由s可达的最短路径长度:若加进u做中间顶点,使得v的最短特殊路径长度变短 则修改v;的距离值(即当Du+W[u,v]<Dv时,令DIv]=Du]+W[uv)。然后重复上 述操作,一旦S包含了所有Ⅴ中的顶点,D中各顶点的距离值就记录了从源点s到该顶点 的最短路径长度。 对于n个顶点e条边的图,图中的任何一条边都可能在最短路径中出现,因此最短路径 算法对每条边至少都要检查一次。 Dijkstra算法采用最小堆来选择权值最小的边,那么每次 改变最短特殊路径长度时需要对堆进行一次重排,此时的时间复杂度为O(n+e)loge),适合3 图中所有顶点均被访问。事实上，深度优先搜索的结果是沿着图的某一分支搜索，直到它的 末端，然后回溯，沿着另一分支进行同样的搜索，依此类推。 （3）广度优先周游 广度优先周游的过程是：从图中的某个顶点 v 出发，访问并标记了顶点 v 之后，横向搜 索 v 的所有邻接点 u1，u2，„，ut。在依次访问 v 的各个未被访问的邻接点之后，再从这些 邻接点出发，依次访问与它们邻接的所有未曾访问过的顶点。重复上述过程直至图中所有与 源点 v 有路径相通的顶点都被访问为止。若 G 是连通图，则周游完成；否则，在图 G 中选 一个尚未访问的顶点作为新源点继续广度优先搜索。广度优先搜索是个非递归的过程，而深 度优先搜索是个递归的过程。 （4）拓扑排序 有向图拓扑排序的步骤： (1) 从有向图中选出一个没有前驱（入度为 0）的顶点并输出它。 (2) 删除图中该顶点和所有以它为起点的弧。 不断重复上述两个步骤，会出现两种情形：要么有向图中顶点全部被输出，要么当前图 中不存在没有前驱的顶点。当图中的顶点全部输出时，就完成了有向无环图的拓扑排序；当 图中还有顶点没有输出时，说明有向图中含有环。可见拓扑排序可以检查有向图是否存在环。 （5）求所有顶点对之间最短路径的 Dijkstra 算法 Dijkstra 算法的基本思想是：把图的顶点集合化分成两个集合 S 和 V-S。第一个集合 S 表示最短距离已经确定的顶点集，即一个顶点如果属于集合 S 当且仅当从源点 s 到该顶点的 最短路径已知。其余的顶点放在另一个集合 V-S 中。初始时，集合 S 只包含源点，即 S = {s}， 这时只有源点到自己的最短距离是已知的。设 v 是 V 中的某个顶点，把从源点 s 到顶点 v 且中间只经过集合 S 中顶点的路径称为从源点到 v 的特殊路径，并用数组 D 来记录当前所 找到的从源点 s 到每个顶点的最短特殊路径长度。D 的初始状态为：如果从源点 s 到顶点 v 有弧则 D[v]记为弧的权值；否则将 D[v]置为无穷大。Dijkstra 算法每次从尚未确定最短路径 长度的集合 V-S 中取出一个最短特殊路径长度最小的顶点 u，将 u 加入集合 S，同时修改数 组 D 中由 s 可达的最短路径长度：若加进 u 做中间顶点，使得 vi的最短特殊路径长度变短， 则修改 vi的距离值（即当 D[u] + W[u, vi] < D[vi]时，令 D[vi] = D[u] + W[u, vi]）。然后重复上 述操作，一旦 S 包含了所有 V 中的顶点，D 中各顶点的距离值就记录了从源点 s 到该顶点 的最短路径长度。 对于 n 个顶点 e 条边的图，图中的任何一条边都可能在最短路径中出现，因此最短路径 算法对每条边至少都要检查一次。Dijkstra 算法采用最小堆来选择权值最小的边，那么每次 改变最短特殊路径长度时需要对堆进行一次重排，此时的时间复杂度为 O((n + e)loge)，适合