2023考研：数据结构之BFS和DFS基础知识

今天小编为各位2023考研的考生整理了数据结构考试的一些知识点——BFS和DFS基础知识，包括定义、性质等信息，希望能够帮助大家更好地备考数据结构，取得好成绩。

BFS：(1)访问起始顶点v。

(2)依次访问v的未访问过的邻接顶点w1，w2，…，wi。

(3)再从这些访问过的顶点出发，再访问它们所有未被访问过的邻接顶点，以此类推，直到图中所有和v连通的顶点都被访问过为止。

(4)另选一个未被访问过的顶点作为起始顶点v，重复步骤(1)、(2)和(3)，直至所有顶点都被访问。

DFS：(1)访问图中某一起始顶点v。

(2)由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2，重复该过程。

(3)当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问，则从该顶点开始重复步骤(2)，直到图中所有顶点均被访问过为止。

BSF和DFS的一些性质：

(1)深度优先遍历使用栈这种数据结构，广度优先遍历使用队列这种数据结构

(2)每个连通分量调用一次遍历算法，那么调用遍历算法的次数等于连通分量的数量

(3)使用邻接矩阵的遍历结果是唯一的;使用邻接表时，由于邻接表不是唯一的，所以遍历结果不是唯一的，但是一旦给定邻接表，遍历结果唯一，即必须按照邻接表的顺序遍历。

(4)使用邻接矩阵的时间复杂度是O(n^2),使用邻接表的时间复杂度是O(n+e)

(5)两种遍历算法会得到深度优先遍历树和广度优先遍历树。

以上就是数据结构之BFS和DFS基础知识的相关介绍，大家可以继续关注启航教育考研备考栏目，获取更多实用备考信息。

点击查看：2023考研：金融硕士考研院校解析（汇总）>>

                  2023考研，考生都面临哪些问题？

                  这些研招院校的A+学科，你知道吗?