图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的遍历是图的一种最基本的操作，其他许多操作都建立在图的遍历操作操作基础之上。图的遍历主要有两种算法：广度优先搜索和深度优先搜索。

广度优先搜索BFS

广度优先搜索（Breadth-First-Search,BFS）,也称宽度优先搜索。作为连通图的一种遍历算法，其算法原理类似于二叉树的层序遍历算法，是许多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。广度优先搜索属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

基本思想

首先访问起始顶点V,接着由V出发，依次访问V的各个未访问过的邻接顶点WWW，然后依次访问WWW的所有未访问过的邻接顶点；再以这些访问过的顶点出发，访问他们所有未被访问过的邻接顶点······以此类推，直到图中所有顶点都被访问过为止。
其实就是顾全大局，雨露均沾。

不同于递归

广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批结点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

举个例子

image.png
你可以说它是二叉树，你也可以说是树，但我非说它是图。广度优先搜索遍历输出结果abcdefgh.
image.png
那这次是图了吧，广度优先搜索输出结果：128356947

广度优先生成树

在广度遍历的过程中，可以得到一颗遍历，称为广度优先生成树。
image.png
由上图得到的广度优先生成树如下：
image.png

深度优先搜索DFS

与广度优先搜索不同，深度优先搜索（Depth-First-Search，DFS）类似于树的先序遍历。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用栈/堆数据结构来辅助实现DFS算法，

基本思想

首先访问图中某一起始顶点V，然后由V出发，访问与V邻接且未被访问的任一顶点W，再访问与W邻接且未被访问的任一顶点W······重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直到图中所有顶点均被访问过为止。
其实就是不撞南墙不回头，一条路啥时候走到底了，啥时候再回头找下一条路。

举个例子

image.png
你可以说它是二叉树，你也可以说是树，但我非说它是图。（是不是有点熟悉，没错我就是复制过来的）
深度优先搜索遍历输出结果abdehcfg(假设优先访问左孩子结点).
image.png
那这次是图了吧，深度优先搜索输出结果：123456789(假设优先访问左孩子结点).

深度优先生成树和生成深林

与广度优先搜索一样，深度优先搜索也会产生一棵深度优先生成树或者生成深林，取决于图是否是连通的。
image.png
其对应的生成深林如下：
image.png