深度优先搜索

图算法

深度优先搜索是一种图遍历算法,它沿着一条路径尽可能深入,直到不能再深入为止,然后回溯到前一个节点,继续探索其他路径。

时间复杂度:最佳 O(V + E) | 平均 O(V + E) | 最差 O(V + E)
空间复杂度:O(V)
图类型:无向图

应用场景/前提条件

  • 适用于探索所有可能的路径
  • 适用于拓扑排序
  • 适用于检测环

算法讲解

深度优先搜索

介绍

深度优先搜索(Depth-First Search, DFS)是一种图遍历算法,它从图的某一顶点开始,沿着一条路径一直走到底,直到不能继续为止,然后回溯到上一个还有未访问邻居的顶点,继续沿着另一条路径走到底,依此类推,直到访问完图中所有可达顶点。DFS的特点是"先进后出",类似于栈的操作特性。

算法步骤

  1. 选择图中的一个起始顶点,将其标记为已访问
  2. 访问该顶点的一个未访问过的相邻顶点,将其标记为已访问,并递归地对该顶点执行DFS
  3. 如果当前顶点没有未访问的相邻顶点,则回溯到上一个顶点
  4. 重复步骤2和3,直到图中所有可达顶点都被访问

算法详解

比如有一个包含8个顶点(0-7)的无向图,边的关系如下:

  • 0与1、2相邻
  • 1与0、3、4相邻
  • 2与0、5、6相邻
  • 3与1、7相邻
  • 4与1相邻
  • 5与2相邻
  • 6与2相邻

...