深度优先算法遍历
A. 简述深度优先搜索遍历的方法。
简述深度优先搜索遍历的方法？深度优先搜索算法(Depth-First-Search, DFS)，最初是一种用于遍历或搜索树和图的算法，在LeetCode中很常见，虽然感觉不难，但是理解起来还是有点难度的。
简要概括，深度优先的主要思想就是“不撞南墙不回头”，“一条路走到黑”，如果遇到“墙”或者“无路可走”时再去走下一条路。
思路
假如对树进行遍历，沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当达到边际时回溯上一个节点再进行搜索。如下图的一个二叉树。
首先给出这个二叉树的深度优先遍历的结果(假定先走左子树)：1->2->4->5->3->6->7
那是怎样得到这样的结果呢？
根据深度优先遍历的概念：沿着这树的某一分支向下遍历到不能再深入为止，之后进行回溯再裤罩搭选定新的分支。
定义节点
class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
递归的方式
分别对左右子树进行递归，一直到底才进行回溯。如果不了解递归可以参考我的博客你真胡拿的懂闷裤递归吗？。
class Solution{
public void (TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"->");
(root.left);
(root.right);
}
}
迭代的方式
上面实现了递归方式的深度优先遍历，也可以利用栈把递归转换为迭代的方式。
但是为了保证出栈的顺序，需要先压入右节点，再压左节点。
class Solution{
public void (TreeNode root){
if(root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
System.out.print(node.val + "->");
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
}
}
接着再列举个利用深度优先遍历的方式的题目
扫雷
给定一个表示游戏板的二维字符矩阵，'M'表示一个未挖出的地雷，'E'表示一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。
根据以下规则，返回相应位置被点击后对应的面板：
如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为'X'。
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。
示例
输入:
[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]
Click : [3,0]
输出:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
思路：根据给定的规则，当给定一个Click坐标，当不为雷的时候以此坐标为基点向四周8个方向进行深度遍历，把空格E填充为B，并且把与地雷M相连的空方块标记相邻地雷的数量。
注意 ：
在这个题中可以沿着8个方向递归遍历，所有要注意程序中，采用了两个for循环可以实现向8个方向递归。
B. 用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法
使用栈来实现算法。
用邻接表表示图进行深度优先遍历时，通常采用栈来实现算法，广度遍历使用队列。
扩展材料：
深度优先遍历：类似与树的前序遍历。从图中的某个顶点v出发，访问此顶点，然后从v的未被访问到的邻接点进行遍历，直到图中所有和v有路径相通的顶点都被访问到
注：优先访问外层节点，访问到无新顶点时，会进行回退，访问未被访问过的分支顶点。
广度优先遍历：类似于树的层序遍历。从图中的某个顶点w出发，让顶点w入队，然后顶点w再出队，并让所有和顶点w相连的顶点入队，然后再出队一个顶点t，并让所有和t相连但未被访问过的顶点入队……由此循环，指定图中所有元素都出队。
参考资料来源：
知网论文-数据结构中图的遍历算法研究
C. 深度优先遍历怎么修改为广度优先遍历
假设初始状态是图中所有顶点均未被访问
从某个顶点出发，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。
若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
实现深度优先遍历的关键在于回溯。所谓“回溯”，就是自后往前，追溯曾经走过的路径。
算法特点
深度优先搜索是一个递归的过程。
首先，选定一个出发点后进行遍历，如果有邻接的未被访问过的节点则继续前进。
若不能继续前进，则回退一步再前进
若回退一步仍然不能前进，则连续回退至可以前进的位置为止。
重复此过程，直到所有与选定点相通的所有顶点都被遍历。
深度优先搜索是递归过程，带有回退操作，因此需要使用栈存储访问的路径信息。当访问到的当前顶点没有可以前进的邻接顶点时，需要进行出栈操作，将当前位置回退至出栈元素位置。
图解过程
无向图的深度优先遍历
以下图所示无向图说明深度优先搜索遍历过程。
实例一
在这里插入图片描述
假设我们从顶点A开始，遍历过程中的每一步如下：
首先选取顶点A为起始点，输出A顶点信息，而且将A入栈，并且标记A为已访问顶点
A的邻接顶点有C、D、F，从中任意选取一个顶点前进。这里我们选取C为前进位置顶点。输出C顶点信息，将C入栈，并标记C为已访问顶点。当前位置指向顶点C
顶点C的邻接顶点有A、D、B，此时A已经标记为已访问顶点，因此不能继续访问。从B或者D中选取一个顶点前进，这里我们选取B顶点为前进位置顶点。输出B顶点信息，将B入栈，标记B顶点为已访问顶点。当前位置指向B
顶点B的邻接顶点只有C、E，C已被标记，不能继续访问，因此选取E为前进位置顶点，输出E顶点信息，将E入栈，标记E顶点，当前位置指向E。
顶点E的邻接顶点均已被标记，此时无法继续前进，则需要进行回退。将当前位置回退至顶点B，回退的同时将E出栈。
顶点B的邻接顶点也均被标记，需要继续回退，当前位置回退至C，回退同时将B出栈。
顶点C可以前进的顶点位置为D，则输出D顶点信息，将D入栈，并标记D顶点。当前位置指向顶点D。
顶点D没有前进的顶点位置，因此需要回退操作。将当前位置回退至顶点C，回退同时将D出栈。
顶点C没有前进的顶点位置，继续回退，将当前位置回退至顶点A，回退同时将C出栈。
顶点A前进的顶点位置为F，输出F顶点信息，将F入栈，并标记F。将当前位置指向顶点F。
顶点F的前进顶点位置为G，输出G顶点信息，将G入栈，并标记G。将当前位置指向顶点G。
顶点G没有前进顶点位置，回退至F。当前位置指向F，回退同时将G出栈。
顶点F没有前进顶点位置，回退至A，当前位置指向A，回退同时将F出栈。
顶点A没有前进顶点位置，继续回退，栈为空，则以A为起始的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。
采用深度优先搜索遍历顺序为A->C->B->E->D->F->G。
利用一个临时栈来实现回溯，最终遍历完所有顶点
问题：
（1）必须选取A作为遍历的起点吗？
不是原则我们可以选取任何一个节点作为起点进行开始，进行深度优先遍历
（2）当有多个邻接点未被访问时，可以选取哪个作为下一个起点呢？
随便哪个都行。
当有多个临界点可选时，相当于走迷宫时出现了多个分叉路口，我们只要不走之前走过的路就行了。所以关键在于标记哪个点是否已经走过。不过，一般我们会定义一个原则，必须不碰重复点的情况下，选择走左/右手第一条没有走过的路，这样比较好理解
两个原则：
右手原则： 在没有碰到重复顶点的情况下，分叉路口始终是向右手边走，每路过一个顶点就做一个记号
左手原则： 在没有碰到重复顶点的情况下，分叉路口始终是向左手边走，每路过一个顶点就做一个记号
下面以右手原则进行深度优先遍历再看个例子
实例二
在这里插入图片描述
原则我们可以选取任何一个节点作为起点进行开始，进行深度优先遍历，假设我们从顶点A开始，遍历过程中的每一步如下：
第一步：从顶点A开始，将顶点A标记为已访问节点
第二步：根据右手原则，访问顶点B，并将B标记为已访问节点
第三步：右手原则，访问顶点C
第四步：右手原则，访问顶点D
第五步：右手原则，访问顶点E
第六步：右手原则，访问顶点F
在这里插入图片描述
第七步：右手原则，应该先访问顶点F的邻接顶点A，但发现A已经被访问，则访问A之外的最右侧顶点G
在这里插入图片描述
第八步：右手原则，先访问顶点B，顶点B已经被访问；在访问顶点D，顶点D已经被访问；最后访问顶点H
在这里插入图片描述
第九步：发现顶点H的邻接顶点均已被访问，则退回到顶点G;
第十步：顶点G的邻接顶点均已被访问，则退回到顶点F；
第十一步：顶点F的邻接顶点已被访问，则退回到顶点E；
第十二步：顶点E的邻接顶点均已被访问，则退回到顶点D；
第十三步：顶点D的邻接顶点I尚未被访问，则访问顶点I；
在这里插入图片描述
第十四步：顶点I的邻接顶点均已被访问，则退回到顶点D;
第十五步：顶点D的邻接顶点均已被访问，退回到顶点C；
第十六步：顶点C的邻接顶点均已被访问，则退回到顶点B；
顶点B的邻接顶点均已被访问，则退回到顶点A，顶点A为起始顶点，深度优先搜索结束。
图的深度优先搜索和二叉树的前序遍历、中序遍历、后序遍历本质上均属于一类方法。
上面的过程可以总结为以下3个步骤：
首先选定一个未被访问过的顶点V作为起始顶点（或者访问指定的起始顶点V），并将其标记为已访问
然后搜索与顶点V邻接的所有顶点，判断这些顶点是否被访问过，如果有未被访问过的顶点W；再选取与顶点W邻接的未被访问过的一个顶点并进行访问，依次重复进行。当一个顶点的所有的邻接顶点都被访问过时，则依次回退到最近被访问的顶点。若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取出一个并重复上述过程，直到与起始顶点V相邻接的所有顶点都被访问过为止。
若此时图中依然有顶点未被访问，则再选取其中一个顶点作为起始顶点并进行遍历，转（2）。反之，则遍历结束。
有向图深度优先搜索
在这里插入图片描述
（1）以顶点A为起始点，输出A，将A入栈，并标记A为已经访问。当前位置指向A。
（2）以A为尾的边只有1条，且边的头为顶点B，则前进位置为顶点B，输出B，将B入栈，标记B。当前位置指向B。
（3）顶点B可以前进的位置有C与F，选取F为前进位置，输出F，将F入栈，并标记F。当前位置指向F。
（4）顶点F的前进位置为G，输出G，将G入栈，并标记G。当前位置指向G。
（5）顶点G没有可以前进的位置，则回退至F，将G出栈。当前位置指向F。
（6）顶点F没有可以前进的位置，继续回退至B，将F出栈。当前位置指向B。
（7）顶点B可以前进位置为C和E，选取E，输出E，将E入栈，并标记E。当前位置指向E。
（8）顶点E的前进位置为D，输出D，将D入栈，并标记D。当前位置指向D。
（9）顶点D的前进位置为C，输出C，将C入栈，并标记C。当前位置指向C。
（10）顶点C没有前进位置，进行回退至D，回退同时将C出栈。
（11）继续执行此过程，直至栈为空，以A为起始点的遍历过程结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。
性能分析
当图采用邻接矩阵存储时，由于矩阵元素个数为n 2 n^2n
2
，因此时间复杂度就是O ( n 2 ) O(n^2)O(n
2
)
当图采用邻接表存储时，邻接表中只是存储了边结点(e条边，无向图也只是2e个结点)，加上表头结点为n（也就是顶点个数），因此时间复杂度为O(n+e)。
广度优先搜索
算法思想
思想：
从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点
然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
实现广度优先遍历的关键在于回放。
回溯与重放是完全相反的过程。
仍然以刚才的图为例，按照广度优先遍历的思想
我们先遍历顶点0，然后遍历其邻接点1、3
接下来我们要遍历更外围的顶点，可是如何找到这些更外围的顶点呢？我们需要把刚才遍历过的顶点1,3按照顺序回顾一遍，从顶点1发现了邻接点2，从顶点3发现了邻接点4。于是得到了顺序2,4
再把刚才遍历过的顶点2，4按照顺序回顾一遍，分别得到邻接点5，6
再把刚才遍历过的顶点5，7按照顺序回顾一遍，分别得到邻接点7，7。7只需要打印一次，所以我们需要一个东西来标记当前顶点是否已经访问过
在这里插入图片描述
像这样把遍历过的顶点按照之前的遍历顺序重新回顾，就叫做重放。
同样的，要实现重放也需要额外的存储空间，可以利用队列的先入先出特性来实现。
另外，还需要标记某个点是否已经被访问过，可以用数组、set等来实现
可以看出，广度优先搜索它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。
算法特点
广度优先搜索类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。
图解过程
无向图的广度优先搜索
在这里插入图片描述
（1）选取A为起始点，输出A，A入队列，标记A，当前位置指向A。
在这里插入图片描述
（2）队列头为A，A出队列。A的邻接顶点有B、E，输出B和E，并将B和E入队，以及标记B、E为已访问。当前位置指向B。
在这里插入图片描述
（3）队列头为B，B出队列。B的邻接顶点有C、D，输出C、D，将C、D入队列，并标记C、D。当前位置指向B。
在这里插入图片描述
（4）队列头为E，E出队列。E的邻接顶点有D、F，但是D已经被标记，因此输出F，将F入队列，并标记F。当前位置指向E。
在这里插入图片描述
（5）队列头为C，C出队列。C的邻接顶点有B、D，但B、D均被标记。无元素入队列。当前位置指向C。
在这里插入图片描述
（6）队列头为D，D出队列。D的邻接顶点有B、C、E，但是B、C、E均被标记，无元素入队列。当前位置指向D。
在这里插入图片描述
（7）队列头为F，F出队列。F的邻接顶点有G、H，输出G、H，将G、H入队列，并标记G、H。当前位置指向F。
在这里插入图片描述
（8）队列头为G，G出队列。G的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向G。
在这里插入图片描述
（9）队列头为H，H出队列。H的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向H。
在这里插入图片描述
（10）队列空，则以A为起始点的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。
有向图的广度优先搜索
在这里插入图片描述
（1）选取A为起始点，输出A，将A入队列，标记A。
在这里插入图片描述
（2）队列头为A，A出队列。以A为尾的边有两条，对应的头分别为B、C，则A的邻接顶点有B、C。输出B、C，将B、C入队列，并标记B、C。
在这里插入图片描述
（3）队列头为B，B出队列。B的邻接顶点为C，C已经被标记，因此无新元素入队列。
在这里插入图片描述
（4）队列头为C，C出队列。C的邻接顶点有E、F。输出E、F，将E、F入队列，并标记E、F。
在这里插入图片描述
（5）列头为E，E出队列。E的邻接顶点有G、H。输出G、H，将G、H入队列，并标记G、H。
在这里插入图片描述
（6）队列头为F，F出队列。F无邻接顶点
在这里插入图片描述
（7）队列头为G，G出队列。G无邻接顶点
在这里插入图片描述
（8）队列头为H，H出队列。H邻接顶点为E，但是E已被标记，无新元素入队列
在这里插入图片描述
（9）队列为空，以A为起始点的遍历过程结束，此时图中仍有D未被访问，则以D为起始点继续遍历。选取D为起始点，输出D，将D入队列，标记D
在这里插入图片描述
（10）队列头为D，D出队列，D的邻接顶点为B，B已被标记，无新元素入队列
在这里插入图片描述
（11）队列为空，且所有元素均被访问，广度优先搜索遍历过程结束。广度优先搜索的输出序列为：A->B–>C->E->F->G->H->D。
算法分析
我们来看下，广度优先搜索的时间、空间复杂度是多少呢？假设图有V个顶点，E条边
每个顶点都需要进出一遍队列，每个边都会被访问一次。所以，广度优先搜索的时间复杂度是O(V+E)。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)
广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列上。这两个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。
总结
图的遍历主要就是这两种遍历思想，深度优先搜索使用递归方式，需要栈结构辅助实现。广度优先搜索需要使用队列结构辅助实现。在遍历过程中可以看出，
对于连通图，从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点
对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。
实现
深度优先遍历
当图采用邻接矩阵进行存储，递归的实现操作：
#define MAXVBA 100
#define INFINITY 65536
typedef struct {
char vexs[MAXVBA];
int arc[MAXVBA][MAXVBA];
int numVertexes, numEdges;
} MGraph;
// 邻接矩阵的深度有限递归算法
#define TRUE 1
#define FALSE 0
#define MAX 256
typedef int Boolean; // 这里我们定义Boolean为布尔类型，其值为TRUE或FALSE
Boolean visited[MAX]; // 访问标志的数组
void DFS(MGraph G, int i){
visited[i] = TRUE;
printf("%c", G.vexs[i]);
for (int j = 0; j < G.numVertexes; ++j) {
if (G.arc[i][j] == 1 && !visited[j]){
DFS(G, j); // 对为访问的邻接顶点递归调用
}
}
}
// 邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G){
int i;
// 初始化所有顶点状态都是未访问过状态
for (i = 0; i < G.numVertexes; ++i) {
visited[i] = FALSE;
}
//防止图为非联通的情况，遍历整个图
for (i = 0; i < G.numVertexes; ++i) {
if (!visited[i]){ // 若是连通图，只会执行一次
DFS(G, i);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
当图采用邻接矩阵进行存储，栈的实现操作：
void DFS_Stack(MGraph G, int i)
{
int node;
int count = 1;
printf("%c ", G.vexs[i]); // 打印已访问顶点
visited[i] = TRUE;
node = i;
push(i); //开始的节点入栈
while(count < G.numVertexes) //still has node not visited
{
/* 所有被访问的节点依次入栈，只有node当找不到下一个相连的节点时，才使用出栈节点 */
for(j=0; j < G.numVertexes; j++)
{
if(G.arc[node][j] == 1 && visited[j] == FALSE)
{
visited[j] = TRUE;
printf("%c ", G.vexs[j]);
count++;
push(j); //push node j
break;
}
}
if(j == G.numVertexes) //与node相连的顶点均已被访问过，所以需要从stack里取出node的上一个顶点，再看该顶点的邻接顶点是否未被访问
node = pop();
else //找到与node相连并且未被访问的顶点，
node = j;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
请添加图片描述
邻接表存储下图的深度优先搜索代码实现，与邻接矩阵的思想相同，只是实现略有不同：
// 邻接表的深度有限递归算法
#define TRUE 1
#define FALSE 0
#define MAX 256
typedef int Boolean; // 这里我们定义Boolean为布尔类型，其值为TRUE或FALSE
Boolean visited[MAX]; // 访问标志的数组
void DFS(GraphAdjList GL, int i)
{
EdgeNode *p;
visited[i] = TRUE;
printf("%c " GL->adjList[i].data);
p = GL->adjList[i].firstEdge;
while(p)
{
if( !visited[p->adjvex] )
{
DFS(GL, p->adjvex);
}
p = p->next;
}
}
// 邻接表的深度遍历操作
void DFSTraverse(GraphAdjList GL)
{
int i;
for( i=0; i < GL->numVertexes; i++ )
{
visited[i] = FALSE; // 初始化所有顶点状态都是未访问过状态
}
for( i=0; i < GL->numVertexes; i++ )
{
if( !visited[i] ) // 若是连通图，只会执行一次
{
DFS(GL, i);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
广度优先遍历
请添加图片描述
// 邻接矩阵的广度遍历算法
void BFSTraverse(MGraph G)
{
int i, j;
Queue Q;
for( i=0; i < G.numVertexes; i++ )
{
visited[i] = FALSE;
}
initQueue( &Q );
for( i=0; i < G.numVertexes; i++ )
{
if( !visited[i] )
{
printf("%c ", G.vex[i]);
visited[i] = TRUE;
EnQueue(&Q, i);
while( !QueueEmpty(Q) )
{
DeQueue(&Q, &i);
for( j=0; j < G.numVertexes; j++ )
{
if( G.art[i][j]==1 && !visited[j] )
{
printf("%c ", G.vex[j]);
visited[j] = TRUE;
EnQueue(&Q, j);
}
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
原文链接：https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw%3D%3D&chksm=db828f&idx=1&mid=2653197523&scene=21&sn=#wechat_redirect
D. JS 深度优先遍历(DFS)和广度优先遍历(BFS)
深度优先遍历DFS
自定义：深度单线游走，从根走完最后一个节点，在游走兄弟节点，走完兄弟的所有子节点，循环之。
银高返 递归算法：
function deepFirstSearch(node, nodeList = []) {
if (node) {
nodeList.push(node);
var children = node.children;
for (var i = 0; i < children.length; i++)
//每次递归的时候将 需要遍历的节点 和 节点所存储的数组传下去
deepFirstSearch(children[i], nodeList);
}
return nodeList;
}
非递归算法：
function deepFirstSearch(node) {
var nodes = [];
if (node != null) {
var stack = [];
stack.push(node);
while (stack.length != 0) {
var item = stack.pop();
nodes.push(item);
var children = item.children;
for (var i = children.length - 1; i >= 0; i--)
stack.push(children[i]);
}
}
return nodes;
}
广度优先遍历(BFS)
自定义：从根开始 层层推进 走完一层 走下一层 （犹如爬楼，走完一层的楼梯，继续下一层的楼梯）
递锋饥归算法：（容易念森栈溢出）
function breadthFirstSearch(node) {
var nodes = [];
var i = 0;
if (!(node == null)) {
nodes.push(node);
breadthFirstSearch(node.nextElementSibling);
node = nodes[i++];
breadthFirstSearch(node.firstElementChild);
}
return nodes;
}
非递归算法：（推荐）
function breadthFirstSearch(node) {
var nodes = [];
if (node != null) {
var queue = [];
queue.unshift(node);
while (queue.length != 0) {
var item = queue.shift();
nodes.push(item);
var children = item.children;
for (var i = 0; i < children.length; i++)
queue.push(children[i]);
}
}
return nodes;
}
E. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的先序遍历，为什么是先序呢
这是因为图的深度优先遍历算法先访问所在结点，再访问它的邻接点。与二叉树的先序遍历先访问子树的根结点，再访问它的孩子结点（邻接点）类似。图的广度优先遍历算法类似于二叉树的按层次遍历。
先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。
首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。
例如，下图所示二叉树的遍历结果是：ABDECF。
(5)深度优先算法遍历扩展阅读：
遍历种类：
一、NLR：前序遍历(Preorder
Traversal
亦称（先序遍历）），访问根结点的操作发生在遍历其左右子树之前。
二、LNR：中序遍历(Inorder
Traversal)，访问根结点的操作发生在遍历其左右子树之中（间）。
三、LRN：后序遍历(Postorder
Traversal)，访问根结点的操作发生在遍历其左右子树之后。
注意：
由于被访问的结点必是某子树的根，所以N(Node）、L(Left
subtree）和R(Right
subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为
先根遍历、中根遍历和后根遍历。
参考资料来源：网络-先序遍历