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