深度优先遍历的顺序

Question

为什么这个图的遍历顺序会是：v1,v2,v5,v10,v6,v7,v3,v12,v11,v8,v4,v9？
怎么也搞不明白，简单图的深度优先看的懂，一到复杂的就懵圈了

Answer 1

这得看具体代码实现了吧，深度优先只规定了往沉挖，没规定同级别的节点间怎么排序。

Answer 2

首先，不管图的表示方式是邻接链表还是邻接矩阵，每个结点寻找与之相连的节点的顺序是固定的，看这个便利顺序应该是从小到大。
然后就是遍历过程的原则了：

1. 遍历过的结点标记，标记过的结点不会再次遍历
2. 当没有结点可以遍历时，原路返回直到有其它结点可以遍历

接下来我们看看这个图，
v1,v2,v5,v10的遍历应该没问题，这时候v1,v2,v5,v10都被标记了，V10没有其它结点相连，所以返回，一直返回到结点V2，
与V2相连的按照顺序有V1，V5，V6，V7，其中V1，V5被标记了，所以到V6
与V6相连的按照顺序有V2，V7，V11，其中V2被标记了，所以到V7
与V7相连的按照顺序有V2，V3，V6，V12，其中V2被标记了，所以到V3
与V3相连的按照顺序有V1，V7，其中V1，V7都被标记了，所以返回到V7，
与V7相连的按照顺序有V2，V3，V6，V12，其中V2，V3，V6被标记了，所以到V12
与V12相连的都被标记了，所以返回，一直返回到V6
与V6相连的按照顺序有V2，V7，V11，其中V2，V7被标记了，所以到V11
与V11相连的按照顺序有V6，V8，其中V6被标记了，所以到V8
与V8相连的按照顺序有V4，V11，所以到V4
与V4相连的按照顺序有V1，V8，V9，，其中V1，V8被标记了，所以到V9
与V9相连的都被标记了，所以返回，发现所有的结点都被标记了，结束。

上面加粗的就是便利顺序了