深度优先遍历顾名思义就是一条路走到黑，再寻其他未走过的路。其类似于树的先序遍历。

思想： 假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。显然，深度优先搜索是一个递归的过程。

方法：

例子： 深度优先遍历上图为：

1.初始状态，从顶点1开始 2.依次访问过顶点2,3后，终止于顶点3 3.从顶点3回溯到顶点2，继续访问顶点5，并且终止于顶点5 4.从顶点5回溯到顶点2，并且终止于顶点2 5.从顶点2回溯到顶点1，并终止于顶点1 6.从顶点4开始访问，并终止于顶点4

像这样先深入探索，走到头再回退寻找其他出路的遍历方式，就叫做深度优先遍历（DFS）。

其实，二叉树的前序、中序、后序遍历，本质上也可以认为是深度优先遍历

时间复杂度：

BFS类似于树的层次遍历。

方法： 从图的某一顶点出发，首先依次访问该顶点的所有邻接顶点，再按照这些顶点被访问的先后顺序依次访问与它们相邻接的所有未被访问的顶点；重复此过程，直至所有顶点均被访问为止。 时间复杂度： 1.如果使用邻接矩阵存储，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），故时间复杂度为O( n 2 n^2 n2) 2.如果使用邻接表存储，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)