遍历是指从某个节点出发，按照一定的搜索路线，依次访问数据结构中的全部节点，且每个节点仅访问一次。图的遍历是指从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列。

　　图的遍历过程中，根据搜索方法的不同，又可分为深度优先搜素(Depth First Search,DFS)和广度优先搜素(Breadth First Search,BFS)。

　　图结构的深度优先遍历是指从图中的某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和ⅴ有路径相通的顶点都被访问到。若此时尚有其他顶点未被访间到，则另选一个未被访问的顶点做起始点，重复上述过程，直至图中所有顶点都被访问到为止。

　　图结构的广度优先遍历是指从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止，两种遍历方式的对比如下图所示。

　　在往前检查顶点时，过滤掉已遍历过的顶点。下面的代码只是一次遍历，并没有考虑一次遍历后还有顶点没遍历的情况。

　　邻接矩阵深度优先遍历

　　程序代码（无向图）：

　　运行结果：

　　程序代码（有向图）：

　　运行结果：

　　邻接表深度优先遍历

　　程序代码（无向图）：

　　运行结果：

　　程序代码（有向图）：

　　运行结果：

　　邻接矩阵广度优先遍历

　　和树的分层遍历相似，逐层邻接顶点遍历。

　　程序代码（无向）：

　　运行结果：

　　程序代码（有向）：

　　运行结果：

　　邻接表广度优先遍历

　　程序代码（无向）：

　　运行结果：

　　程序代码（有向）：

　　运行结果：

　　练习题１：修改上面的代码，使它们适合一次遍历没完的情况。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社