图的遍历

图的遍历：指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。

图的遍历可分为四类：
1、遍历完所有的边而不能有重复，即所谓“一笔画问题”或“欧拉路径”；
（每条边只经过一次，而且回到起点）

2、遍历完所有的顶点而没有重复，即所谓“哈密尔顿问题”。
（是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径）

3、遍历完所有的边而可以有重复，即所谓“中国邮递员问题”；
（邮递员在某一地区的信件投递路程问题。邮递员每天从邮局出发，走遍该地区所有街道再返回邮局，问题是他应如何安排送信的路线可以使所走的总路程最短）

4、遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。
（假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值）

图的遍历是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

两条遍历图的路径：深度优先搜索和广度优先搜索。

深度优先搜索：
类似树的先序遍历

微信图片_20180403150446.png

因此访问顺序是：A -> C -> B -> D -> F -> G -> E

广度优先搜索:

微信图片_20180403161804.png

因此访问顺序是：A -> B -> C -> E -> D -> F -> G