求无向连通图（邻接表表示）的所有深度优先遍历序列

设计算法以实现对无向图G的深度遍历，要求：将每一个连通分量中的顶点以一个表的形，式输出。例如，下图的输出结果为：(1，3)(2，6，7，4，5，8)(9，10)。

注：本算法中可以调用以下几个函数：firstadj(g，1，)——返回图g中顶点v的第一个邻接点的号码，若不存在，则返回0。nextadj(g，v，w)——返回图g中顶点v的邻接点中处于w之后的邻接点的号码，若不存在，则返回0。nodes(g)——返回图g中的顶点数。【合肥工业大学2000五、4(8分)】

对于一个非连通无向图G，采用深度优先遍历访问所有顶点，在DFSTraverse函数(见考点讲解DFS部分)中调用DFS的次数正好等于（ ）。

A．顶点数

B．边数

C．连通分量数

D．不确定

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

此题为判断题(对，错)。

● 对连通图进行遍历前设置所有顶点的访问标志为 false（未被访问） ，遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点 v 出发开始遍历，先访问 v 并设置其访问标志为 true（已访问） ，同时将 v 加入遍历序列，再从 v 的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若 v的所有邻接点都已访问，则回到 v 在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。 （40） 是下图的深度优先遍历序列。

（40）

A. 1 2 3 4 6 5

B. 1 2 6 3 4 5

C. 1 6 2 5 4 3

D. 1 2 3 4 5 6

● 对连通图进行遍历前设置所有顶点的访问标志为 false（未被访问） ，遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点 v 出发开始遍历，先访问 v 并设置其访问标志为 true（已访问） ，同时将 v 加入遍历序列，再从 v 的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若 v的所有邻接点都已访问，则回到 v 在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。 （40） 是下图的深度优先遍历序列。

（40）

A. 1 2 3 4 6 5

B. 1 2 6 3 4 5

C. 1 6 2 5 4 3

D. 1 2 3 4 5 6

对连通图进行遍历前设置所有顶点的访问标志为false(未被访问)，遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点v出发开始遍历，先访问v并设置其访问标志为true(已访问)，同时将v加入遍历序列，再从v的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若v的所有邻接点都已访问，则回到v在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。(40)是下图的深度优先遍历序列。

A．1 2 3 4 6 5

B．1 2 6 3 4 5

C．1 6 2 5 4 3

D．1 2 3 4 5 6

对连通图进行遍历前设置所有顶点的访问标志为false(未被访问)，遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点v出发开始遍历，先访问v并设置其访问标志为true(已访问)，同时将v加入遍历序列，再从v的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若v的所有邻接点都已访问，则回到v在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。(40)是下图的深度优先遍历序列。

A．1 2 3 4 6 5

B．1 2 6 3 4 5

C．1 6 2 5 4 3

D．1 2 3 4 5 6

阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。

1. 【说明】

实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。

【算法】

第一步：首先访问连通图G的指定起始顶点v；

第二步：从V出发，访问一个与v(1)p，再从顶点P出发，访问与p(2)顶点q，然后从q出发，重复上述过程，直到找不到存在(3)的邻接顶点为止。

第三步：回退到尚有(4)顶点，从该顶点出发，重复第二、三步，直到所有被访问过的顶点的邻接点都已被访问为止。

因此，在这个算法中应设一个栈保存被(5)的顶点，以便回溯查找被访问过顶点的未被访问过的邻接点。

此题为判断题(对，错)。