图的遍历（深度优先）

这是我参与11月更文挑战的第8天，活动详情查看：2021最后一次更文挑战

根据这棵二叉树 我们先手动来模拟一下深度优先遍历算法，先访问a,a访问b 在b访问后 我们接着访问c 在c访问发现c没有孩子我们就回溯到b点再访问e点 ，e访问后再访问h ，发现h没有孩子就回溯到e点，发现e点孩子都访问完了又回溯到b点发现b点的孩子有访问了 则又回溯到a点再访问c点这样访问+回缩最后这棵树的顺序则为：abdehcfg 在这个过程中就会有一个（递归思想在里面）
若我们对树进行先序遍历，遍历的结果是：abdehcfg

因此根据上面模拟的过程再一次来梳理思想：
首先访问某一个起始顶点v，然后接着会访问v的未被访问的任一邻接点w1，再访问w1未被访问的任一邻接点w2..不断往下面访问，当不能再往下访问时，就回溯到最近刚被访问的顶点，若这个顶点还有邻接点未访问就继续上面的过程 最后倒所有结点都访问完就结束这次遍历

结合上面的思想来看一下他的代码实现：

bool visited[MaxNum]; //标记数组 用于标记结点是否被访问过
void DFSTraverse(Graph G){
  for(int i=0;i<G.vexnum;i++){ //初始化数组
    visited[i] = false;
  }
  
  for(int i;i<G.vexnum;i++){
    if(visited[i]){
      DFS(G,i);
    }
  }
}

void DFS(Graph G,int v){
   visit(v);
   visited[v] = true; //修改标记数组
   for(w=FirstNeighbor(G,v); W>=0; w= NextNeighbor(G,v,w)){  //检查顶点的所有邻接点
     if(!visited[w]){  
       DFS(G,w);
     }
   }

}
复制代码

算法性能分析：

时间复杂度：

邻接矩阵： O(|V|2)

邻接表： O(|V|+|E|)

空间复杂度：O(|V|)（需要一个递归工作栈）

• 总结

图的遍历算法，在昨天和今天分享的广度优先遍历算法和深度优先遍历算法，广度优先遍历借助队列的先进先出特点来辅助，深度优先借助的就是一个递归栈来辅助实现的

而这两种遍历算法可以用来测试图的连通性，对于无向图来说，从任一个结点出发，遍历一次就能访问所有结点，所以不能一次访问完所有结点就可知该图为非连通图，对于有向图来说，从初始点到每一个点都有路径，则能够访问完所有结点 反之就不能访问。所以对于无向图，调用BFS(G,i)、DFS(G,i)的次数就是该图的连通分量数，而对于有向图，非强连通图是无法访问所有结点的。