4.3 图的遍历

 二、综合应用题

　　1．综合应用题题目部分
　　● 习题1：试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值（设图G已用邻接表存储）。
　　● 习题2：写出连通图的深度优先搜索DFS算法的非递归算法。
　　2．综合应用题答案与分析
　　注意：本节中所涉及的图的数据结构在4.2节中已有描述。
　　习题1分析：
　　从图的遍历算法可知，每进行一次深度优先遍历算法或广度优先遍历算法，就可以得到图的一个连通分量的所有顶点。其算法思想如下：对图中的每一个顶点，若该顶点未被访问过，则从该　　顶点出发进行深度优先遍历，且在遍历过程中输出访问的节点信息，即可得到相应的连通分量。其算法如下所示：

　　void dfs ( int v)
　　{
　　  visited[v]=1; printf ("%3d",v);   //输出连通分量的顶点
 　　 p=g[v].firstarc;
 　　 while （p!=null）
  　　{
   　　 if(visited[p->adjvex]==0)
   　　   dfs(p->adjvex);
   　　 p=p->next;
　　  }
　　}

　　void Count(AdjList g)               //求图中连通分量的个数
　　{
 　　int k=0 ;
 　　for (i=1;i<=n;i++ )
 　　if (visited[i]==0)
 　　 { 
 　　   printf ("\n第%d个连通分量:\n"，++k);
 　　   dfs(i);
 　　 }
　　}
　　习题2分析：
　　深度优先遍历可从图中某个顶点V出发，访问此节点，然后依次访问V的未被访问的邻接点，从该点出发深度优先遍历图，直到图中所有和V有路径相同的顶点都被访问；若此时图中尚有顶点　未被访问，则另选一个未曾被访问的顶点重做起点，重复上述过程。
　　因此，对于深度优先遍历的非递归算法，需要用栈来保存之前已经访问过的节点。若当前节点的所有邻接点都已经访问完，且图中还有节点未被访问，则需要进行出栈操作，再次遍历。其算法如下：

　　void Traver(AdjList g, int v)
　　{
　　  struct arc *stack[];
　　  visited[v]=1;
　　  printf(v); //输出顶点v
　　  top=0;
　　  p=g[v].firstarc;
　　  stack[++top]=p;
 　　 while（top>0 || p!=null）
　　  {
 　　  while (p)
  　　   if (p && visited[p->adjvex])
      　　 p=p->next;
     　　else
     　　{
       　　Printf('%d',p->adjvex); 
       　　visited[p->adjvex]=1;
       　　stack[++top]=p;
       　　p=g[p->adjvex].firstarc;
     　　}
   　　if (top>0)
   　　{ p=stack[top--]; p=p->next; }
  　　}
　　}
　　3．训练自测表（如表4-6所示）

表4-6  应用题练习自测表