题目

从第v个顶点出发递归的深度优先遍历图G。void DFS(graoh G.int v) Visited[v]=true: Visitfunc(v); for(w=firstAdjVew(G,v):w>=0;w=NestAdj-Vex(G,v,w)) ( if() DFS(G,w); )A.!visited[w]B.visited[w]C.visited[v]D.!Visited[v]

从第v个顶点出发递归的深度优先遍历图G。

void DFS(graoh G.int v)

   Visited[v]=true:

   Visitfunc(v);

   for(w=firstAdjVew(G,v):w>=0;w=NestAdj-Vex(G,v,w))

  {

     if()

    DFS(G,w);

  }

A.!visited[w]

B.visited[w]

C.visited[v]

D.!Visited[v]

题目解答

答案

在给定的代码中，Visited 是一个布尔类型的数组，用于记录每个顶点的访问状态。递归的深度优先遍历从第 v 个顶点出发，需要选择正确的条件来确定是否对顶点 w 进行深度优先遍历。

根据代码片段，正确的选项是：

A. !Visited[w]

在代码的 for 循环中，通过检查 !Visited[w] 来判断顶点 w 是否已经被访问过。只有当顶点 w 还未被访问时，才会进行递归的深度优先遍历 DFS(w)。

因此，答案是 A. !Visited[w]。

解析

考查要点：本题主要考查对深度优先遍历（DFS）算法的理解，特别是如何通过已访问标记数组控制遍历过程，避免重复访问。

解题核心思路：
在DFS中，已访问标记数组visited的作用是记录顶点是否被访问过。遍历过程中，只有未被访问的邻接顶点才会被继续递归处理。因此，if条件需判断当前邻接顶点w是否未被访问（即!visited[w]）。

破题关键点：

  • visited数组的作用：通过visited[w]判断顶点w是否被访问过。
  • DFS逻辑：每次递归时，必须确保邻接顶点w未被访问，否则会导致重复遍历或错误路径。

在代码中，DFS函数从顶点v出发，通过邻接顶点遍历图G。关键步骤如下：

  1. 标记当前顶点为已访问：visited[v] = true;
    这一步确保顶点v不会被重复处理。

  2. 处理当前顶点：Visitfunc(v);
    执行具体的顶点操作（如输出顶点编号）。

  3. 遍历邻接顶点： 

    for (w = firstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
    if (/* 条件 */) {
        DFS(G, w);
    }
}
    • firstAdjVex和NextAdjVex用于获取顶点v的邻接顶点w。
    • if条件的作用：仅当邻接顶点w未被访问时，递归调用DFS(G, w)，继续遍历。

  4. 条件判断：

    • 若选择!visited[w]（选项A），则只有未被访问的顶点w会被递归处理，符合DFS逻辑。
    • 其他选项（B、C、D）均无法正确判断邻接顶点w的访问状态，会导致错误。