算法--深度优先和广度优先

BFS广度优先搜索算法

树的广度优先搜索

如上图，对于一颗数，广度优先搜索就是一个节点出队时，它的所有子节点都要入队。相当于数的层序遍历。

第一步：1入队
第二步：1出队 2，3，4入队
第三步：2出队 5，6入队
----------------------------以此类推

图的广度优先搜索

对于一个图，图没有根节点的说法，从任意一个节点开始。如从2节点开始。

构造一个节点是否被访问的数组visited，开始时所有值都为false。为了便于理解，下标和数组id一致，从1开始计。

第一步：2入队，将visited[2]置为true；
第二步：2出队 1，3，5，6入队，visit[1,3,5,6]置为true；
第三步：1出队 2，3，4入队，但2，3都访问过了，所以跳过，只有4入队；
----------------------------以此类推

图通常由邻接表或者邻接矩阵存储，所以当我们要看一个节点的相邻节点时，用邻接矩阵存放的话就可以得到固定的遍历序列；但如果用边链表存储的话，这个边链表可以是随意排序的，所以遍历序列也不固定。

在复杂度上，空间复杂度是O(n)，时间复杂度取决于图的存储方式，用邻接矩阵存储的话是O(n2)，邻接表的存储是O(n+v)。

广度优先生成

按图的邻接矩阵广度优先的方式生成一颗树，那么从A出发，子节点是B,C,D，再看B没有子节点，看C有子节点E，所以生成的树如下图，且是唯一的。

按图的邻接表生成树，由于邻接表的形态不唯一，所以生成的树也不唯一。

DFS深度优先搜索

树的深度优先搜索

树的深度优先搜索和树的中序遍历类似，可以用递归或队列模拟，非常简单，这里略过。

图的深度优先搜索

图的深度优先搜索需要辅助队列，固定的邻接矩阵或者邻接表。如上图，那么它的顺序如下：

第一步：假设从3开始，3入栈，[3];
第二步：3和1，2，4，7，8相邻，1排在最前面，1入栈，[1,3];
第三步：1和2，3，4相邻，2入栈，[2,1,3];
第四步：2和1，3，5，6相邻，1，3 访问过了，5入栈，[5,2,1,3];
第五步：5走到头了，没有未被访问的相邻顶点了，5出栈，[2,1,3]；
接下来回到2，将6入栈，将7入栈，[7,6,2,1,3];
接下来7、6、2相邻的顶点都访问过了，依次出栈；

最后按入栈的顺序：3，1，2，5，6，7，4，8，9
出栈的顺序有：5，7，6，2，8，9，4，1，3