1介绍遍历是指从某个节点开始，按照一定的搜索路径依次访问数据结构中的所有节点，每个节点只访问一次。在二叉树基础中，介绍了树的遍历。树的遍历是指从根节点开始，按照一定的访问规则依次访问树的各个节点的信息。树的遍历过程根据不同的访问规则主要分为四种遍历方式：(1)前序遍历(2)中序遍历(3)后序遍历(4)层次遍历类似的，图遍历是指，从给定图中的任意指定顶点（称为初始点）开始，按照一定的搜索方式沿图的边访问图中的所有顶点，使得每个顶点只被访问一次，这个过程称为图遍历.遍历时得到的顶点序列称为图遍历序列。在图遍历过程中，根据搜索方式的不同，可以分为两种搜索策略：(1)深度优先搜索(DFS，DepthFirstSearch)(2)广度优先搜索(BFS，BreadthFirstSearch)2深度优先搜索2.1算法思想深度优先搜索思想：假设初始状态为图中所有顶点都未被访问过，从某个顶点v开始，先访问该顶点，然后依次从其未访问过的相邻点开始。深度优先搜索遍历图，直到图中所有具有路径为v的顶点都被访问过。如果此时还有其他顶点没有被访问过，则选择另一个没有被访问过的顶点作为起点，重复上述过程，直到图中所有顶点都被访问过。2.2算法特点深度优先搜索是一个递归过程。首先选择一个起点进行遍历，如果有相邻的未访问节点，则继续前进。进不了就退一步进，退一步还是进不了，再继续退到可以进的位置。重复此过程，直到遍历了所有连接到所选点的顶点。深度优先搜索是一个带有回滚操作的递归过程，因此需要使用栈来存储访问路径信息。当当前访问的顶点没有相邻顶点可以前进时，需要进行一次入栈操作，将当前位置返回到出栈元素的位置。2.3图解过程2.3.1无向图深度优先搜索用图2.3.1.1所示的无向图来说明深度优先搜索的遍历过程。图2.3.1.1(1)首先选择顶点A作为起点，输出顶点A的信息，并将A压入栈中，标记A为访问过的顶点。(2)A的相邻顶点为C、D、F，任意选择一个顶点向前移动。这里我们选择C顶点作为前向位置顶点。输出C顶点信息，将C入栈，标记C为已访问顶点。当前位置指向顶点C。(3)顶点C的相邻顶点为A、D、B，此时A已经被标记为已访问顶点，不能继续访问。从B或D中选择一个顶点前进，这里我们选择B顶点作为前进位置顶点。输出B顶点信息，将B压入栈中，将B顶点标记为已访问顶点。当前位置指向顶点B。(4)顶点B的相邻顶点只有C和E，C已经被标记，不能继续访问。因此，选择E作为前向位置顶点，输出E顶点的信息，将E压入栈中，标记E顶点，当前位置指向E。(5)顶点E的相邻顶点已经标记完毕，它这个时候是不可能再往前走了，所以需要回滚。将当前位置返回到顶点B，同时将E出栈。(6)顶点B的相邻顶点也被标记，需要继续回滚。当前位置回退到C，同时B出栈。(7)顶点C可以前进的顶点位置为D，然后输出D顶点信息，将D入栈，标记D顶点。当前位置指向顶点D。(8)顶点D没有前向顶点位置，因此需要回滚操作。将当前位置返回到顶点C，同时将D出栈。(9)顶点C没有顶点位置向前移动，继续回滚，将当前位置回滚到顶点A，回滚同时将C出栈。(10)顶点A前进的顶点位置为F，输出F的顶点信息，将F压入栈中，标记F。将当前位置指向顶点F。(11)顶点F前进的顶点位置为G，输出G顶点信息，将G压入栈中，标记G。将当前位置指向顶点G。(12)顶点G不前进到顶点位置，返回F。当前位置指向F，回溯并将G从堆栈中弹出。(13)顶点F不前进到顶点位置，返回A，当前位置指向A，同时将F出栈。(14)顶点A没有前进到顶点位置，继续后退，栈为空，则从A开始的遍历结束。如果图中还有未访问的顶点，则选择未访问的顶点作为起点并继续该过程。直到访问完所有的顶点。(15)深度优先搜索的遍历顺序是A->C->B->E->D->F->G。2.3.2有向图深度优先搜索用图2.3.2.1所示的有向图来说明深度优先搜索的遍历过程。图2.3.2.1有向图(1)以顶点A为起点，输出A，将A入栈，标记A，当前位置指向A。(2)只有一条边以A为尾，边的头为顶点B，则前向位置为顶点B，输出B，将B入栈，标记B，当前位置指向B.(3)顶点B可以向前移动的位置是C和F，选择F作为前进位置，输出F，将F压入栈中，标记F。当前位置指向F。(4)前进顶点F的位置为G，输出G，将G入栈，标记G。当前位置指向G。(5)如果顶点G没有地方可以向前移动，则返回F，将F弹出堆栈。当前位置指向F。(6)顶点F无处可进，继续回退到B，将F出栈。当前位置指向B。(7)顶点B可以前进到C和E，选择E，输出E，将E压入栈，标记E。当前位置指向E。(8)顶点前进位置E为D，输出D，将D入栈，标记D。当前位置指向D。(9)顶点D的前进位置为C，输出C，将C压入栈，标记C。当前位置指向C。(10)顶点C没有前向位置，回滚到D，同时将C出栈。(11)继续执行这个过程，直到栈为空，结束以A为起点的遍历过程。如果图中还有未访问的顶点，则选择未访问的顶点作为起点并继续该过程。直到访问完所有的顶点。2.4算法分析当图存储在邻接矩阵中时，由于矩阵元素个数为n^2，时间复杂度为O(n^2)。当图存入邻接表时，邻接表只存边节点（e条边，而无向图只有2e个节点），加上头节点为n（即顶点个数），所以时间复杂度是O(n+e)。3广度优先搜索3.1算法思想广度优先搜索思想：从图中的某个顶点v开始，在访问完v之后，依次访问v的每个没有被访问过的相邻点，然后依次访问它们的相邻点开始从这些邻接点出发，使得“最先访问的顶点的邻接点先于后访问的顶点的邻接点被访问，直到图中所有被访问的顶点的邻接点都被访问。如果图中还有顶点3.2算法特点广度优先搜索类似于树级遍历，就是按照从近到远的方式访问图的顶点。在进行广度优先搜索时，需要使用队列来存储顶点信息。3.3图过程3.3.1无向图的广度优先搜索例如：图3.3.1.1所示的无向图有向图，采用广度优先搜索过程。图3.3.1.1（1）选择A作为起点，输出A，将A放入队列，标记A，指向当前位置的A。(2)队头是A，A出队。A的相邻顶点为B和E，输出B和E，将B和E入队，标记B和E。当前位置指向A。(3)队头为B，B出队队列。B的相邻顶点为C和D，输出C和D，将C和D放入队列，并标记C和D。当前位置指向B。(4)队头为E，E去不在队列中。E的相邻顶点是D和F，但是D已经被标记了，所以输出F，将F放入队列，并标记F。当前位置指向E。(5)队列的头部是C，C离开队列。C的相邻顶点是B和D，但是B和D都被标记了。没有元素排队。当前位置指向C。(6)队头为D，D出队。D的相邻顶点是B、C、E，但是B、C、E都被标记了，没有元素排队。当前位置指向D。(7)队头为F，F出队。F的相邻顶点为G和H，输出G和H，将G和H放入队列，标记G和H。当前位置指向F。(8)队列的头部为G，G去不在队列中。G的相邻顶点有F，但是F已经被标记，没有元素入队。当前位置指向G。(9)队头为H，H出队。H的相邻顶点有F，但是F已经被标记，没有元素入队。当前位置指向H。(10)如果队列为空，则结束以A为起点的遍历。如果图中还有未访问的顶点，则选择未访问的顶点作为起点并继续该过程。直到访问完所有的顶点。3.3.2有向图的广度优先搜索以图3.3.2.1所示的有向图为例，进行广度优先搜索。.3.2.1（1）选择A为起点，输出A，将A放入队列，标记A。（2）队头为A，A出队。有两条以A为尾的边，对应的头分别为B、C，则A的相邻顶点为B、C。输出B、C，将B、C放入队列，标记B、C。(3)队头是B，B出队。B的相邻顶点是C，C已经被标记，所以没有新的元素入队。(4)队头为C，C出队。C的相邻顶点为E、F。输出E、F，将E、F入队，标记E、F。(5)队头为E，E出队。E的相邻顶点为G、H。输出G、H，将G、H入队，标记G、H。(6)队头为F，F出队。F没有相邻的顶点。(7)队头为G，G出队。G没有相邻的顶点。(8)队头为H，H出队。H的相邻顶点是E，但是E已经被标记，没有新的元素入队。(9)队列为空，以A为起点的遍历过程结束。此时图中还有D没有被访问，以D为起点继续遍历。选择D作为起点，输出D，将D放入队列，标记D。(10)队头为D，D出队，与D相邻的顶点为B，B已被标记，没有新元素入队。(11)队列为空，访问所有元素，广度优先搜索遍历过程结束。广度优先搜索的输出顺序是：A->B->E->C->D->F->G->H。3.4算法分析假设图有V个顶点和E条边，广度优先搜索算法需要搜索V个节点，耗时为O(V)。在查找的过程中，需要根据边增加队列的长度，所以这里需要消耗O(E)，一般来说效率在O(V+E)左右。4总结图的遍历主要基于这两种遍历思想。深度优先搜索采用递归的方法，需要栈结构的辅助。广度优先搜索需要使用队列结构来实现。在遍历过程中可以看出，对于连通图，从图的任意一个顶点开始，深度优先或者广度优先遍历必须能够访问到图中的所有顶点，但是对于不连通图，从任意一个顶点开始遍历该图，深度或广度优先遍历不会访问图中的所有顶点。
