(转)BFS与DFS

发布网友发布时间：2023-05-25 20:55

共1个回答

热心网友时间：2024-11-15 22:30

广度优先搜索（BFS）和深度优先搜索（DFS）都是图遍历算法中的重要成员。BFS采用的策略是：越早被访问到的顶点，其邻居越优先被访问。类似于树的层次遍历。DFS采用的策略是：优先选取最后一个被访问到的顶点的邻居。类似于树的前序遍历。

BFS算法的时间比较简单。
顶点的状态有三种：（1）visited；（2）discovered；（3）undiscovered；
采用辅助队列Q存放已经遍历的顶点。每一次迭代都从Q中取出当前的首顶点v；在逐一核对其邻居状态u的状态并做相应的处理，最后将顶点v置为visited，即可进入下一步迭代。

DFS算法是优先选取最后一个被访问到的顶点的邻居。因此可以栈作为辅助的数据结构（当然不用也行，只是为了好实现）。DFS的每一次迭代中，都先将当前节点v标记为discovered状态，再逐一核对其各邻居u的状态并做相应的处理，待其所有邻居均已处理完毕之后，将顶点v设置为visited状态，然后进行回溯。

DFS算法重要的有一个活跃期的时间区间。通过活跃期可以判断两个顶点之间是否是祖先-后代关系，判断的充要条件是两个顶点的活跃期是否相互包含。

BFS和DFS的时间复杂度都是O(n+e)，其中n是顶点数，e是边的数量。

参考：
https://www.cnblogs.com/brucekun/p/8503042.html