【数据结构与算法学习】图的深度优先遍历（DFS算法）

作者：我家自动化 | 2024-04-29 20:49:32

踩

图的深度优先遍历

图的遍历，指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。
在这里插入图片描述

二、深度优先遍历（DFS）的基本思想

深度优先遍历（death first search）即DFS，从初始结点出发，初始结点可能会有多个邻接结点，访问完初始结点后，将其标记为已访问，再任意选择一个未被访问的邻接结点，然后再以这个被选择的邻接结点作为初始结点，再任意选择它的下一个未被访问邻接结点，以此类推。大概可以先理解为：每次都在访问完当前结点后首先访问的是未被访问的邻接结点，并任意选择一个邻接结点视为初始结点，继续遍历下去。

在这里插入图片描述
想必在这时候，很多小伙伴已经发现问题了。当下一个结点的全部邻接结点都已经被访问过了，该怎么继续遍历下去呢？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/509752

【数据结构与算法学习】图的深度优先遍历（DFS算法）

目录

一、什么是图的遍历

二、深度优先遍历（DFS）的基本思想