BFS和DFS学习笔记

2023-02-15,,

1 算法介绍

1.1 BFS

Breadth First Search(广度优先搜索),将相邻的节点一层层查找,找到最多的

以上图为例,首先确定一个根节点,然后依次在剩下的节点中找已找出的节点的相邻节点,特别注意顺序为依次寻找

(1)A为根节点,结果为ABCDEF或ACBEDF

(2)B为根节点,结果为BACDEF或BDACFE或......

(3)D为根节点,结果为DBEFAC或......

(4)F为根节点,结果为FDBEAC或......

1.2 DFS

Deep FIrst Search(深度优先搜索),一直往下寻找,若没有剩余相邻节点时,回走一步,再查找剩余的下一个相邻节点,直到回到起始点

以上图为例,举例说明:A为根节点,A --> B --> D --> E --> C --> 发现C没有相邻的未使用点,回退 --> E(E还是没有),继续回退 --> D --> F --> 发现F没有相邻的未使用点了,继续回退 --> D,继续回退 --> B,继续回退 --> A,到根节点了,结束。则结果为ABDECF

2 算法数据结构

2.1 BFS

queue

2.2 DFS

stack

3 代码实现

3.1 BFS

未完待续......

3.2 DFS

未完待续......

参考文献

B站up主【正月点灯笼】视频,地址: https://www.bilibili.com/video/BV1Ks411579J?from=search&seid=8959770473739025997&spm_id_from=333.337.0.0

BFS和DFS学习笔记的相关教程结束。

《BFS和DFS学习笔记.doc》

下载本文的Word格式文档,以方便收藏与打印。