数据词典：深度优先搜索（Depth First Search）

赵老师

与广度优先搜索不同，深度优先搜索（Depth First Search，DFS）类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。

它的基本思想如下：首先访问图中某一个起始顶点v，然后由v出发，访问与v邻接且未被访问过的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2......，重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

【出处】王道论坛.王道数据结构考研复习指导,电子工业出版社，2020年1月第1版。