图的遍历算法:DFS、BFS

在图的基本算法中,最初需要接触的就是图的遍历算法,根据访问节点的顺序,可分为深度优先搜索(DFS)和广度优先搜索(BFS)。

DFS(深度优先搜索)算法

Depth-First-Search

深度优先算法,是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。

当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。 这一过程一直进行到已发现从源节点可达的所有节点为止。

如果还存在未被发现的节点, 则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

图的遍历算法:DFS、BFS

DFS可用堆栈(Stack)和递归(Recursive)两种方法实现

如何跟踪下一步搜索的位置?

使用Stack: 列表中只从一端添加和移除:

  • Push:添加元素
  • Pop:删除一个元素

如何跟踪访问过的内容?

HashSet::常量添加,删除和搜索

如何跟踪从开始到目标的路径?

HashMap:将每个节点链接到发现它的节点

堆栈和递归实现过程(伪代码):

图的遍历算法:DFS、BFS                    图的遍历算法:DFS、BFS

BFS (广度优先搜索)算法

Breadth-First-Search

BFS是从根节点开始,沿着树的宽度遍历树的节点。

如果所有节点均被访问,则算法中止。 广度优先搜索的实现本篇笔记采用队列。

图的遍历算法:DFS、BFS

如何跟踪下一步搜索的位置?

Queue:列出你只从一端添加和移除的地方

  • enqueue:添加一个元素
  • deque:删除一个元素

如何跟踪访问过的内容?

HashSet:定时添加,删除和搜索

如何跟踪从开始到目标的路径?

HashMap:将每个节点链接到发现它的节点

和DFS唯一不同的是BFS使用队列来实现,伪代码如下:

图的遍历算法:DFS、BFS

学习参考资料:

深度优先和广度优先的Python实现

【Python算法】遍历(Traversal)、深度优先(DFS)、广度优先(BFS)

搜索思想——DFS & BFS(基础基础篇)

 
上一篇:聊聊算法——BFS和DFS


下一篇:【数据结构与算法】自己动手实现图的BFS和DFS(附完整源码)