【小算法】图的遍历之深度优先(DFS)
谈到算法，图的操作是避免不了。
而我们一般谈到图时，又必定会谈到图的遍历。
图的遍历通常有 2 种，深度优先(DFS) 和广度优先(BFS)。
本篇博文讲解深度优先(DFS)。
图的表示
图有两种表示方式
1. 临接矩阵
其实就是一个权重矩阵，用 1 代表两个结点有连接，0 表示没有连接，这样的表示方式通俗易懂，特别适合稠密图，也就是大多数结点是亮亮连接的情况。
2. 临接表
用一个数组储存所有的顶点的信息，每个顶点又用一个链表或者是数组存放与它相临的结点的信息。
这样的表示方式特别适合稀疏图，也就是比较少的结点之间相互有连接。
本文示例代码用 Python 表示，为了简便，用临接表这种形式表示
DFS 算法思路
其实 DFS 的思路非常简单。
如果你哪天钱包忘记在哪里了，以 DFS 的思路就是，一个房间一个房间找。
先选定一个房间，大致扫一眼，发现没有。
然后，就选择房间里面的办公桌，桌子上没有的话，再去桌子上的柜子里面找。
如果桌子没有，就去床上着。
如果翻遍了所有的角落，也没有那就换个房间。
DFS 图例
上面是一张图，如果要遍历图中所有的结点，又不重复。
可以先选择一个顶点作为根结点，然后沿着路径一条一条遍历下去。
关键词是递归，因为递归需要终止条件，所以另外需要用一个数组记录已经访问过的结点，当一个结点它的临结点都已经访问时，它就需要回溯，这样能避免重复及陷入死循环。
我们首先选择 A.
A 有 2 个临接结点 B 和 C,我们选择先从 B 出发，所以此时路径是
A--->B
现在在 B 结点位置，B 有 3 个临接结点，C、D、F，按照优先往右边走的原则，我们选择 F,所以此时的路径是
A--->B--->F
F 也有 3 个临接点B,D,E，按照从最右边的顺序遍历，我们选择 E，现在路径是：
A--->B--->F--->E
同样的逻辑，在 E 点会选择右边的 C,这时候路径是
A--->B--->F--->E--->C
到达 C 点时，情况有些不同，它的临接点 A 和 B 都已经访问过了，代表这条路径到头了，需要向上回溯。
回溯的过程也是顺着路径往回撤，路径是
A--->B--->F--->E--->C--->E
E 有 2 个临接点，因为 C 点已经访问了，所以 E 可以访问 D.
到了 D 点，D 的临接点都已经访问过，所以 D 也需要往回溯，这种回溯是递归的，最终会回溯到节点 A.
A 是从 B 出发的，按照算法逻辑，这个时候应该从 C 出发了，但是 C 已经被访问了，所以最终整个遍历就结束了。
Python 代码
dfs.py
# G 是临接表的方式表达图形
G={}
G[0] = {1,2}
G[1] = {2,3,5}
G[2] = {0,1,3}
G[3] = {2,4,5}
G[4] = {1,3,5}
G[5] = {1,3,4}
# 记录访问过的结点
visited = [False,False,False,False,False,False]
# 结点的别名
names=['A','B','C','D','E','F']
def dfs(v):
# 打印访问的点
print("--->",names[v])
visited[v] = True
for i,value in enumerate(G[v]):
# 如果可以访问，最沿着路径一直访问
if not visited[value]:
dfs(value)
if __name__ == "__main__":
# 打印图
print("Graphy:",G)
dfs(0)最终结果如下：
Graphy: {0: {1, 2}, 1: {2, 3, 5}, 2: {0, 1, 3}, 3: {2, 4, 5}, 4: {1, 3, 5}, 5: {1, 3, 4}}
---> A
---> B
---> C
---> D
---> E
---> F可以看到，代码可以正常执行，大家亲手实践一下吧。