深度优先遍历算法DFSTraverse

深度优先遍历总结
深度优先遍历是一种常见的图遍历算法。

其基本思想是从图的某个顶点出发，沿着一条路径一直走到不能走为止，然后回溯到前一个节点，继续走下一个路径，直到遍历完整个图。

深度优先遍历可以用递归或者栈来实现。

递归实现方法比较简单，栈实现方法需要手动维护一个栈。

深度优先遍历的时间复杂度为O(V+E)，其中V为顶点数，E为边数。

空间复杂度为O(V)，即需要开辟一个visited数组来记录每个
顶点是否被访问过。

深度优先遍历可以用来解决一些图论问题，例如判断图是否连通，找到图中的所有连通分量，求解最短路径等。

需要注意的是，深度优先遍历不一定能够找到最优解，因为它只考虑了当前路径，而没有考虑其他路径的可能性。

因此，在实际应用中，需要根据具体问题来选择合适的算法。

- 1 -。

1图的遍历问题在实践中常常遇到这样的问题：给定n个点，从任一点出发对所有的点访问一次并且只访问一次。

如果用图中的顶点表示这些点，图中的边表示可能的连接，那么这个问题就可以表示成图的遍历问题，即从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。

图的遍历操作和树的遍历操作功能相似，是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础上。

由于图结构本身的复杂性，所以图的遍历操作也比较复杂，主要表现在以下几个方面：(1) 在图结构中，没有一个确定的首结点，图中任意一个顶点都可以作为第一个被访问的结点。

(2) 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需要考虑如何选取下一个出发点以访问图中其余的连通分量。

(3) 在图结构中，如果有回路存在，那么一个顶点被访问后，有可能沿回路又回到该顶点。

⑷在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。

基于以上分析，图的遍历方法目前有深度优先搜索(DFS)和广度优先搜索(BFS)两种算法。

下面将介绍两种算法的实现思路，分析算法效率并编程实现。

1.1深度优先搜索算法深度优先搜索算法是树的先根遍历的推广，它的实现思想是：从图G的某个顶点V o出发，访问V o,然后选择一个与V o相邻且没被访问过的顶点V i访问，再从V i出发选择一个与V i相邻且未被访问的顶点V j进行访问，依次继续。

如果当前被访问过的顶点的所有邻接顶点都已被访问，贝U退回已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样的方法向前遍历，直到图中所有顶点都被访问。

其递归算法如下：Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数void DFSTraverse (Graph G Status(*Visit)(i nt v)){VisitF unc = Visit;for(v=0; vvG.vex num; ++v)visited[v] = FALSE; //访问标志数组初始化for(v=0; v<G .vex num; ++v)if(!visited[v])DFS(G v); //对尚未访问的顶点调用DFS}void DFS(Graph G int v){ //从第v个顶点出发递归地深度优先遍历图Gvisited[v]=TRUE; VisitFunc(v); // 访问第v 个顶点for(w=FirstAdjVex(G ,v); w>=0;w=NextAdjVex(G ,v,w))//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空(0)。

JS树结构数据的遍历树结构是一种常见的数据结构，它由若干节点组成，节点之间存在一对多的关系。

在前端开发中，经常需要遍历树结构的数据来进行处理操作。

本文将介绍几种常用的树结构数据的遍历算法。

一、深度优先遍历（DFS）深度优先遍历是一种递归的遍历算法，其核心思想是先遍历子节点，再遍历父节点。

在JavaScript中，可以使用递归函数来实现深度优先遍历。

以下是一个简单的树结构数据的遍历例子：```javascriptfunction dfs(node)console.log(node.value);if (node.children)for (let child of node.children)dfs(child);}}```在上述例子中，dfs函数用来深度优先遍历树结构数据。

它首先打印当前节点的值，然后递归调用dfs函数遍历子节点。

二、广度优先遍历（BFS）广度优先遍历是一种按层次顺序遍历节点的算法，其核心思想是先遍历同一层的节点，再遍历下一层的节点。

在JavaScript中，可以使用队列来实现广度优先遍历。

以下是一个简单的树结构数据的遍历例子：```javascriptfunction bfs(root)let queue = [root];while (queue.length > 0)let node = queue.shift(;console.log(node.value);if (node.children)for (let child of node.children)queue.push(child);}}}```在上述例子中，bfs函数用来广度优先遍历树结构数据。

它使用一个队列来保存待遍历的节点，初始时将根节点加入队列，然后循环进行以下操作：从队列中取出一个节点，打印该节点的值，将该节点的子节点加入队列。

三、前序遍历、中序遍历和后序遍历（二叉树）在二叉树中，除了深度优先遍历和广度优先遍历外，还常用以下三种特殊的遍历方式：1. 前序遍历（pre-order）：先访问根节点，再依次访问左子树和右子树。

⼆叉树遍历（前序、中序、后序、层次、⼴度优先、深度优先遍历）⽬录转载：⼆叉树概念⼆叉树是⼀种⾮常重要的数据结构，⾮常多其他数据结构都是基于⼆叉树的基础演变⽽来的。

对于⼆叉树，有深度遍历和⼴度遍历，深度遍历有前序、中序以及后序三种遍历⽅法，⼴度遍历即我们寻常所说的层次遍历。

由于树的定义本⾝就是递归定义，因此採⽤递归的⽅法去实现树的三种遍历不仅easy理解并且代码⾮常简洁，⽽对于⼴度遍历来说，须要其他数据结构的⽀撑。

⽐⽅堆了。

所以。

对于⼀段代码来说，可读性有时候要⽐代码本⾝的效率要重要的多。

四种基本的遍历思想前序遍历：根结点 ---> 左⼦树 ---> 右⼦树中序遍历：左⼦树---> 根结点 ---> 右⼦树后序遍历：左⼦树 ---> 右⼦树 ---> 根结点层次遍历：仅仅需按层次遍历就可以⽐如。

求以下⼆叉树的各种遍历前序遍历：1 2 4 5 7 8 3 6中序遍历：4 2 7 5 8 1 3 6后序遍历：4 7 8 5 2 6 3 1层次遍历：1 2 3 4 5 6 7 8⼀、前序遍历1）依据上⽂提到的遍历思路：根结点 ---> 左⼦树 ---> 右⼦树，⾮常easy写出递归版本号：public void preOrderTraverse1(TreeNode root) {if (root != null) {System.out.print(root.val+" ");preOrderTraverse1(root.left);preOrderTraverse1(root.right);}}2）如今讨论⾮递归的版本号：依据前序遍历的顺序，优先訪问根结点。

然后在訪问左⼦树和右⼦树。

所以。

对于随意结点node。

第⼀部分即直接訪问之，之后在推断左⼦树是否为空，不为空时即反复上⾯的步骤，直到其为空。

若为空。

则须要訪问右⼦树。

注意。

在訪问过左孩⼦之后。