【华为机试 Python实现】图的遍历

---

图的遍历

我们希望从图中某一顶点出发遍历图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历。
图的遍历算法是求解图的最小路径问题的基础。

图的任意一顶点都可能与其他顶点相连，在遍历图时，可能沿着一条路径遍历下来，又回到了原顶点。
为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已经访问过的顶点。

通常有两种遍历图的路径，深度优先搜索和广度优先搜索。

深度优先搜索

深度优先搜索（Depth First Search）遍历类似于树的先根遍历，是树先根遍历的衍生。

深度优先搜索可以从图中任一顶点出发，然后依次从V未被访问的领接顶点发起深度优先搜索遍历，直至图中所有和V有路径想通的顶点都被访问到。

我们上图为例，从v1进行深度优先搜索；
访问v1后选择相邻顶点v4，v4没有未被访问的相邻顶点&#