图的深度优先遍历

x33g5p2x  于2022-06-27 转载在 其他  
字(0.7k)|赞(0)|评价(0)|浏览(167)

一 点睛

深度优先搜索是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直搜索下去,在无法搜索时,回退到刚刚访问过的节点。深度优先遍历是按照深度优先搜索方式对图进行遍历的。

深度优先遍历的秘籍:后被访问的节点,其邻接点先被访问。

根据深度优先遍历秘籍,后来者先服务,这可以借助栈实现。递归本身就是使用栈实现的,因此使用递归的方法更方便。

二 算法步骤

1 初始化图中的所有节点都未被访问。

2 从图中的某个节点 v 出发,访问 v 并标记其已被访问。

3 依次检查 v 的所有邻接点 w,如果 w 未被访问,则从 w 出发进行深度优先遍历(递归调用,重复步骤 2~3)。

三 图解

1 初始化所有节点都未被访问,visited[i] = false,i=[1,8]。

2 从节点1出发,标记其已被访问,visited[1] = true。

3 从节点1出发访问邻接点2,然后从2节点出发访问节点4,从节点4出发访问节点5,从节点5出发,没有节点再可访问。

4 回退到刚刚访问过的节点4,节点4也没有未被访问的邻接点,回退到最近访问过的节点2,从节点2出发访问下一个未被访问的邻接点6。

5 从节点6出发访问没有被访问的邻接点,回退到刚刚访问过的节点2,节点2没有被访问的邻接点,回退到最近访问过的节点1。从节点1出发访问下一个未被访问的邻接点3,从节点3出发访问节点7,从节点7出发访问节点8,从节点8出发再没被访问的邻接点。

6 回退到刚刚访问过的节点7,节点7没有未被访问的邻接点,回退到最近访问过的节点3,节点3也没有未被访问过的邻接点,回退到最近访问过的节点1,节点1也没有未被访问的邻接点,遍历结束。

深度优先遍历序列为 1 2 4 5 6 3 7 8

相关文章

微信公众号

最新文章

更多