深度优先搜索

深度优先搜索DFS：【与树的先序遍历类似】
1）首先访问起始顶点v
2）接着由v出发访问v的任意一个邻接且未被访问的邻接顶点wi
3）然后再访问与wi邻接且未被访问的任意顶点yi
4）若wi没有邻接且未被访问的顶点时，退回到它的上一层顶点v
5）重复上述过程，直到所有顶点被访问为止

借助递归(栈)+辅助标记数组来实现：【邻接矩阵法的DFS(BFS)序列唯一，邻接表法的不唯一】
DFS序列：ACDEB

DFS算法的性能分析：
1）空间复杂度：O(|V|)
2）时间复杂度：邻接矩阵法O(|V|^2)，邻接表法O(|V|+|E|)

深度优先生成树：在深度遍历过程中，我们可以得到一棵遍历树，称为深度优先生成树（生成森林）【邻接矩阵法的深度优先生成树唯一，邻接表法的不唯一】

遍历与连通性问题：
1）在无向图中，在任意结点出发进行一次遍历(调用一次BFS或DFS)，若能访问全部结点，说明该无向图是连通的
2）在无向图中，调用遍历函数(BFS或DFS)的次数为连通分量的个数

有向图中上面两个结论都不成立：