浅谈DFS

引言

遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且每个顶点仅被访问一次，实质：找每个顶点的邻接点的过程

问题描述

按深度优先写出顶点的访问顺序

算法描述

1、首先选择一个顶点作为起始顶点（任意一个顶点皆可为起始顶点），为了方便书写，我们选择V1作为起始顶点。2、然后由V1出发去访问它的任意邻接点，这里V1的邻接点有V2、V3，我们可以任选其一（这里我选择V2）。3、再由V2出发，访问与V2邻接但还未被访问的顶点，即V4和V5,这里同样可以任选一个邻接顶点（这里我选择V4）。4、再由V4出发，访问与V4邻接但还未被访问的顶点，但是V4没有下一个邻接顶点，所以这时我们需要退回上一个顶点，V2。5、再重新由V2出发，访问与V2邻接但未被访问的顶点，所以访问V5（因为V4已经被访问了）6、右边也是同理。最终访问顺序为：V1→V2→V4→V5→V3→V6→V8→V7

方法：1）确定访问图中的起始顶点VA，由VA出发，访问它的任意邻接顶点VB；2）再从VB出发，访问与VB邻接但未被访问的顶点VC；3）再从VC出发，进行类似的访问…；4）重复以上步骤，直到所有的邻接顶点都被访问过的顶点K为止；5）退后一步，退到上一次刚访问过的顶点，看其他邻接顶点是否访问完毕；6）若有未被访问的顶点，则从该顶点出发，进行上述的访问；若没有，则继续退后一步，进行搜索，重复上述步骤，直到所有顶点都被访问为止。

结语

图的深度优先遍历算法类似于树的先根算法，但仅仅是类似于，二者不可混为一谈。

实习编辑：李欣容

稿件来源：深度学习与文旅应用实验室（DLETA）