图的遍历的定义以及深度优先搜索和广度优先搜索（二）

接上一篇文章写,大家可以看看前面的文章

接上一篇讲

（这是上图）

由上述遍历（上篇文章算法）可知在遍历过程中有的边发挥了作用、而有的边没发挥作用，如将没发挥作用的边去掉，便得到该图的深度优先生成树:另外，输出的序列方式也不是唯一的，因为出发顶点 V 是从图中任选的。但是，生成树必须与其遍历输出序列完全相对应。上图深度优先生成树如下：(v1,v2,v4,v8,v5,v3,v6,v7)

在实际系统中为保证深度优先遍历正确执行，需设置辅助空间栈，用来保存遍历过程中访问过的顶点。

还有，在遍历过程中，选择出发顶点 v 的次数为该图中连通分量的个数。该算法的时间复杂性为 O(n+e)与下边所要将的广度优先遍历相同。它们的区别是广度优先遍历的过程使用队列与对顶点访问的顺序不同。

深度优先搜索的非递归算法

• 操作步骤

操作步骤如下:

• 1 从任意一个 vi 出发，入栈，然后出栈，并访问 vi,并置位访问标志。

• 2 将 vi 的所有邻接点压入堆栈，然后出栈 vi 的第一个邻接点 vj。若该点没被访问过，则访问，置位访问标恶，重复 2 的过程;若该点已被访问过，则出栈 v 的下一个邻接点，直到遇到未被访问过的邻接点，重复 2 的过程。

• 1.2 的递归过程结束后，若还有未被访问过的邻接点，则重新选取一个新的顶点作为新的 v，重复 1 到 2 的过程。

广度优先搜索

广度优先搜索是类似于树的按层次遍历的过程。假设从图中某个顶点 V0 出发，访问 V0 以后紧接着访问 V0 的所有没被访问过的邻接顶点，然后分别从这些被访问过的邻接顶点出发做广度优先搜索直到图中所有已被访问的顶点的邻接顶点都被访问到。如果，此时图中还有顶点尚未访问，则从剩余的顶点中再任选一个顶点作为 V0，重复上述过程，直到图中全部顶点都被访问为止。上图广度优先搜索的输出序列为下面所示 V1 V2 V3 V4 V5 V6 V7 V8 。其广度优先搜索生成树如下面所示。

• 算法如下：

Void BFSTravrse(Graph GStatus(*Visit) (int v)) {

//按广度优先非递归遍历图 G。使用辅助队列 Q 和访问标志数组 Visited

for(v=0; v<G.vexnum; ++v) visited[v] = FALSE;

InitQueue(Q);(队列置空)

for(v=0; v<G.vexnum; ++v)

if(!visited[v]){ (v 尚未访问)

visited[v] = True;Visit(v);

EnQueue(Q,v);(v 入队列)

while(!QueueEmpty(Q)) {

DeQueue(Q,u);(队头元素出队列并置为 u)

for(w=FirstAdjVex(G,u);w>= 0;w =NextAdjVex(G,u,w))

if (! Visited[w]){w 为 u 的尚未访问的邻接顶点)

Visited[w] = True; Visit(w);

EnQueue(Q,w);

}//if

}//while

}//if

}// BFSTravrse