精选优质文档-倾情为你奉上5.3 图的遍历 和树的遍历类似，在此，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历(TraversingGraph)。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。然而，图的遍历要比树的遍历复杂得多。因为图的任一顶点都可能和其余的顶点相邻接。所以在访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该顶点上。例如图7.1(b)中的G2，由于图中存在回路，因此在访问了v1,v2,v3,v4之后，沿着边(v4 , v1)又可访问到v1。为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。为此，我们可以设一个辅助数组visited0.n-1，它的初始值置为“假”或者零，一旦访问了顶点vi，便置visitedi为“真”或者为被访问时的次序号。 通常有两条遍历图的路径：深度优先搜索和广度优先搜索。它们对无向图和有向图都适用。5.3.1 深度优先搜索 深度优先搜索(Depth-Fir
