ABCLearning遍历
遍历是指从某个节点出发，按照一定的的搜索路线，依次访问对数据结构中的全部节点，且每个节点仅访问一次。
在二叉树基础中，介绍了对于树的遍历。树的遍历是指从根节点出发，按照一定的访问规则，依次访问树的每个节点信息。树的遍历过程，根据访问规则的不同主要分为四种遍历方式：
（1）先序遍历
（2）中序遍历
（3）后序遍历
（4）层次遍历
类似的，图的遍历是指，从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列。
图的遍历过程中，根据搜索方法的不同，又可以划分为两种搜索策略：
（1）深度优先搜索（DFS，Depth First Search）
（2）广度优先搜索（BFS，Breadth First Search）
深度优先搜索
深度优先搜索思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
深度优先搜索是一个递归的过程。首先，选定一个出发点后进行遍历，如果有邻接的未被访问过的节点则继续前进。若不能继续前进，则回退一步再前进，若回退一步仍然不能前进，则连续回退至可以前进的位置为止。重复此过程，直到所有与选定点相通的所有顶点都被遍历。
深度优先搜索是递归过程，带有回退操作，因此需要使用栈存储访问的路径信息。当访问到的当前顶点没有可以前进的邻接顶点时，需要进行出栈操作，将当前位置回退至出栈元素位置。
当图采用邻接矩阵存储时，由于矩阵元素个数为n^2，因此时间复杂度就是O(n^2)。
当图采用邻接表存储时，邻接表中只是存储了边结点(e条边，无向图也只是2e个结点)，加上表头结点为n（也就是顶点个数），因此时间复杂度为O(n+e)。
广度优先搜索
广度优先搜索思想：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
广度优先搜索类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。
假设图有V个顶点，E条边，广度优先搜索算法需要搜索V个节点，时间消耗是O(V)，在搜索过程中，又需要根据边来增加队列的长度，于是这里需要消耗O(E)，总得来说，效率大约是O(V+E)。
总结
图的遍历主要就是这两种遍历思想，深度优先搜索使用递归方式，需要栈结构辅助实现。广度优先搜索需要使用队列结构辅助实现。在遍历过程中可以看出，对于连通图，从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点，但对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。
