在计算机科学中，图遍历(也称为图搜索)是指在图中访问(检查/或更新)每个顶点的过程。这样的遍历是按访问顶点的顺序进行分类的。比如，树遍历就是图遍历的一个特例。
与树遍历不同，图遍历可能需要多次访问某些顶点，因为在转换到一个已经被探索的顶点之前，它并不一定是已知的。随着图形变得越来越密集，这种冗余变得更加普遍，导致计算时间增加;随着图形变得越来越稀疏，相反的情况也成立。
因此，通常需要记住哪些顶点已经被算法探索过了，这样就可以尽可能少地重新访问顶点(或者在最坏的情况下，防止遍历无限延续)。这可以通过将图中的每个顶点与在遍历期间的“颜色”或“访问”状态相关联来完成，然后在算法访问每个顶点时检查和更新。如果顶点已经被访问过，它就被忽略了，路径就不再被继续了;否则，算法会检查/更新顶点，并继续它当前的路径。
常见的图搜索算法包括深度优先搜索（depth-first search，DFS）和广度优先搜索（breadth-first search，BFS）。
DFS是一种遍历有限图的技术。DFS在访问兄弟节点之前访问子顶点; 也就是说，在探索它的宽度之前，它会穿越任何特定的路径。在实现算法时，通常使用一个堆栈(通常是通过递归调用程序的调用堆栈)。算法从一个选定的“根”顶点开始;然后，它会迭代地从当前的顶点过渡到一个相邻的、未访问的顶点，直到它再也找不到一个未被探索的顶点来从它当前的位置转换。然后，算法会沿着之前访问过的顶点进行回溯，直到它找到一个连接到更多未知领域的顶点。然后，它会像以前一样沿着新路径前进，当它遇到死路时回溯，并且只有当算法从第一个步骤回溯到原来的“根”顶点时才会结束。
BFS是另一种遍历有限图的技术。BFS在访问子顶点之前访问邻居的顶点，并且在搜索过程中使用一个队列。该算法通常用于寻找从一个顶点到另一个顶点的最短路径。
[描述来源：Wikipedia；URL：https://en.wikipedia.org/wiki/Graph_traversal]
在AI领域中，相当一部分问题要涉及对状态空间进行搜索，寻找最优解。很多时候，这等同于一个图搜索问题。比如，经典的启发式搜索算法A*算法就是一种图搜索算法。
发展历史
描述
图搜索属于图论的研究范畴，大致可以分为四大类，即遍历完所有的边而不能有重复的“一笔画问题”或“欧拉路径”；遍历完所有的顶点而没有重复的“哈密尔顿问题”；遍历完所有的边而可以有重复的“中国邮递员问题”；以及遍历完所有的顶点而可以重复的“旅行商问题”。
欧拉路径问题起源于数学家欧拉(Euler)对于著名的哥尼斯堡七桥问题（Seven Bridges of Königsberg）的研究。1736年，欧拉关于该问题发表的一篇论文也被认为是图论的起源。欧拉路径问题已经得到了解决，并总结为了著名的欧拉定理。
哈密尔顿问题由天文学家哈密尔顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。这个问题和著名的七桥问题的不同之处在于，过桥只需要确定起点，而不用确定终点。哈密尔顿问题寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。哈密尔顿路径问题在上世纪七十年代初，被证明是NP完全问题（NP-complete problem）。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。
1962年中国数学家管梅谷提出中国邮递员问题（Chinese Postman Problem，CPP），是著名图论问题之一。一个邮递员从邮局出发，要走完他所管辖的每一条街道，可重复走一条街道，然后返回邮局。任选择一条尽可能短的路线。如果邮递员所通过的街道都是单向道，则对应的图应为有向图。埃德蒙兹（J.Edmonds）和约翰逊（L.Johnson)在1973年给出了这种情况下CPP问题求解的多项式时间算法。帕帕季米特里屋（C.H.Papadimitriou）在1976年证明，如果既有双向道，又有单向道，则CPP是NP困难的。
旅行商问题，即TSP问题（Traveling Salesman Problem）。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。该问题可以被证明具有NPC计算复杂性。TSP的研究历史很久，最早的描述是1759年欧拉研究的骑士环游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。1954年，G.Danzig等人用线性规划的方法取得了旅行商问题的历史性的突破——解决了美国49个城市的巡回问题。
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1736 | Euler发表关于哥尼斯堡七桥问题的论文 | Euler, L. . Solutio problematis ad geometriam situs pertinentis. Commetarii Academiae Scientiarum Imperialis Petropolitanae, 8(8), 128-140. |
| 1859 | William Rowan Hamilton提出哈密尔顿问题 | |
| 1954 | G.Danzig等人用线性规划的方法解决了美国49个城市的巡回问题,取得了旅行商问题的历史性的突破 | Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. (1954). Solution of a Large-Scale Traveling-Salesman Problem. Operations Research, 2(4), 393-410. |
| 1962 | 管梅谷提出中国邮递员问题（Chinese Postman Problem，CPP） | Kwan, M. K. (1962). Graphic programming using odd or even points. Chinese Math, 1, 263-266. |
| 1968 | P.Hart等人提出了A*算法，成为状态空间搜索中广泛应用的经典启发式搜索算法 | Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. |
| 1973 | 埃德蒙兹（J.Edmonds）和约翰逊（L.Johnson)在1973年给出了这种情况下CPP问题求解的多项式时间算法 | Edmonds, J., & Johnson, E. L. (1973). Matching, euler tours and the chinese postman.Mathematical Programming, 5(1), 88-124. |
| 1976 | 帕帕季米特里屋（C.H.Papadimitriou）证明，如果既有双向道，又有单向道，则CPP是NP困难的 | Papadimitriou, C. H. (1976). The np-completeness of the bandwidth minimization problem. Computing, 16(3), 263-270. |
发展分析
瓶颈
相当一部分图搜索问题被证明是NP完全问题，无法给出多项式时间的解法。同时，随着时间的推移，由现实场景抽象出的图规模越来越大，结构越来越复杂，因此图的搜索就变得更加困难，尤其对于已经被证明属于NP完全问题的图。
未来发展方向
基于上述瓶颈，对NP完全或搜索复杂度极高的图搜索问题的研究方向将转为对于其求解的简化和近似算法或启发式算法研究。任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。
Contributor: Han Hao