一、什么是图的遍历

图的遍历是指从图中某一个节点出发，沿着边访问图中其他节点，使每一个节点仅被访问一次，最终访问完所有节点的过程。一般而言，遍历图的方法有深度优先搜索（Depth-First-Search，DFS）和广度优先搜索（Breadth-First-Search，BFS）两种。

二、深度优先搜索

深度优先搜索（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

三、广度优先搜索

广度优先搜索（Breadth-First-Search，BFS）是一种从源节点开始，沿着树的宽度遍历树的节点的搜索算法。它的基本思想是：从根节点开始，沿着树的宽度遍历树的节点，如果所有节点均被访问，则算法中止。广度优先搜索是一种盲目搜索，它没有考虑搜索路径的长度，它每次搜索都是按照层次来搜索的，即先搜索所有距离根节点距离为 1 的节点，然后搜索距离根节点距离为 2 的节点，以此类推。