1、
》》图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问
一次且仅访问一次。
注意：树是一种特殊的图，所以树的遍历实际上也可以看作是一种特殊的图的遍历。
》》 图的遍历是图的一种最基本的操作，其他许多操作都是建立在图的遍历操作基础之上。
》》图的遍历主要有两种算法：广度优先搜索、深度优先搜索。
2、广度优先搜索（Breadth-First-Search , BFS）【借助队列实现】
》》广度优先搜索（BFS）类似于二叉树的层序遍历算法，它的基本思想是：首先访问起始顶点 v ,
接着由v出发，依次访问v的各个未访问过的邻接顶点w1 ， w2, w3 , ... , wi ，然后再依次访问
w1 , w2 , w3 , ... , wi的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，再访问它们所有
未被访问过的邻接顶点.....依次类推，直到图中所有顶点都被访问过为止。
类似的思想还将应用于“ Dijkstra单源最短路径算法 ”和“ Prim最小生成树算法 ”。
》》广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样
有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，
以记忆正在访问的顶点的下一层顶点。
》》广度优先搜索的案例：【借助队列实现--》非递归算法】
假设从 a开始访问，a先入队。此时队列非空，取出队头元素 a ，由于 b 、 c和a邻接且未被
访问过，于是依次访问 b 、c ，并将 b 、c依次入队。队列非空，取出队头元素 b ，依次访问与
b邻接且未被访问过的顶点 d和 e ，并将 d 、e入队（注意：a与 b也邻接，但是 a已被设置为
访问标记，故不再重复访问）。此时队列非空，取出队头元素c ，访问与c邻接且未被访问的顶点
f 、 g ，并将 f 、 g入队。此时，取出队头元素 d ，但与 d邻接且未被访问过的顶点为空，故而
不进行任何操作。继续取出队头元素 e ，将 h入队。。。。当最后取出队头元素 h后，队列为空，
从而循环自动跳出。遍历结果为 abcdefgh
》》补充1：“图的广度优先搜索的过程”与 “二叉树的层序遍历”是完全一致的，这也说明了图的
广度优先搜索遍历算法是二叉树的层序遍历算法的扩展。
》》 BFS算法的性能分析
##无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列 Q ，n个顶点均
需要入队一次，在最坏的情况下，空间复杂度为 O( | V | )。
## 当采用邻接表存储方式时，每个顶点均需要搜索一次（或入队一次），故时间复杂度为O( | V | ) 。
在搜索任意顶点的邻接点时，每条边至少访问一次，故时间复杂度为 O(| E | ) ，算法的时间复杂度为
O( | V | + | E | )。
##当采用邻接矩阵存储方式时，查找每个顶点的邻接点所需要的时间为 O(| V |) ,故算法总的时间
复杂度为 O()。
》》BFS 算法求解单源最短路径问题
##如果图 G = （V , E ）为非带权图，定义从顶点u到顶点v的最短路径 d(u,v) 为从 u到 v
的任何路径中最少的边数；如果从 u到 v没有通路，则 d(u,v) =∞。
##使用 BFS ，我们可以求解一个满足上述定义的非带权图的单源最短路径问题，这是由广度优先
搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。
》》广度优先生成树【遍历树】
##在广度优先搜索的遍历过程中，我们可以得到一棵遍历树，称为“广度优先生成树 ”。
注意：一个给定图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的。
一个给定图的邻接表存储表示不唯一，故其广度优先生成树也是不唯一的。
3、深度优先搜索（Depth-First-Search , DFS）【借助递归栈实现】
》》深度优先搜索（DFS）类似于树的先序遍历。这种搜索算法所遵循的搜索策略是尽可能“深”
地搜索一个图。它的基本思想如下：首先访问图中某一起始顶点v ，然后由v出发，访问与
v邻接且未被访问的任一顶点 w1 ,再访问与w1邻接且未被访问的任一顶点w2 ，。。。重复
上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被
访问过，则从该点开始继续上述搜索过程，直到图中所有顶点均被访问过为止。
》》深度优先搜索是借助递归栈实现的。
》》注意：图的邻接矩阵表示是唯一的，但对于邻接表来说，如果边的输入次序不同，生成的邻接
表也不同。
对于同样一个图，基于邻接矩阵的遍历所得到的 DFS序列和 BFS序列是唯一的，基于
邻接表的遍历所得到的 DFS序列和 BFS序列是不唯一的。
》》 DFS算法的性能分析
##DFS算法是一个递归算法，需要借助一个递归工作栈，故它的空间复杂度为 O( |V | )。
##遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的
存储结构。
a.当以邻接矩阵表示时，查找每个顶点的邻接点所需要的时间为 O( | V | ) ，故总的时间
复杂度为 O( )。
b.当以邻接表表示时，查找所有顶点的邻接点所需要的时间为 O( | E | ) ，访问顶点所
需时间为 O(| V | ) ，此时，总的时间复杂度为 O( | V | + | E | )
》》深度优先的生成树和森林
深度优先搜索也会产生一棵深度优先生成树。但是，是有条件的。
条件：对连通图调用 DFS才可以产生深度优先生成树，否则产生的将是深度优先生成森林。
4、图的遍历与图的连通性
》》图的遍历算法可以用来判断图的连通性。
》》对于无向图来说，如果无向图是连通的，则从任一结点出发，仅需一次遍历就能访问图中
所有顶点；如果无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在
连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。
对于有向图来说，若从初始点到图中每个顶点都有路径则能够访问到图中所有顶点，否则
不能访问到所有顶点。
