深度优先搜索是一种图遍历算法,它沿着一条路径尽可能深入,直到不能再深入为止,然后回溯到前一个节点,继续探索其他路径。
深度优先搜索(Depth-First Search, DFS)是一种图遍历算法,它从图的某一顶点开始,沿着一条路径一直走到底,直到不能继续为止,然后回溯到上一个还有未访问邻居的顶点,继续沿着另一条路径走到底,依此类推,直到访问完图中所有可达顶点。DFS的特点是"先进后出",类似于栈的操作特性。
比如有一个包含8个顶点(0-7)的无向图,边的关系如下:
...
扫码关注 算法导航公众号