广度和深度优先搜索(BFS和DFS)

news/2025/6/21 15:37:41/

1. 广度和深度优先搜索(BFS和DFS)

1.1. Python实现BFS和DFS

from collections import dequeclass Graph:"""无向图类,支持添加边,并实现了 BFS(广度优先搜索)和 DFS(深度优先搜索)用于查找从一个顶点到另一个顶点的路径。"""def __init__(self, v):self.v = v                            # 顶点数self.adj = [[] for _ in range(v)]     # 邻接表,初始化为空列表self.found = False                    # DFS 中用于标记是否已经找到目标节点def add_edge(self, s, t):self.adj[s].append(t)self.adj[t].append(s)  # 因为是无向图,所以两个方向都要添加def bfs(self, s, t):if s == t:print(s)returnvisited = [False] * self.v     # 标记每个节点是否访问过visited[s] = Truequeue = deque()queue.append(s)prev = [-1] * self.v           # 用于记录路径,prev[i] 表示访问 i 节点的前一个节点while queue:w = queue.popleft()for q in self.adj[w]:if not visited[q]:prev[q] = wif q == t:self._print_path(prev, s, t)returnvisited[q] = Truequeue.append(q)print("No path found.")def dfs(self, s, t):self.found = Falsevisited = [False] * self.vprev = [-1] * self.vself._recur_dfs(s, t, visited, prev)if self.found:self._print_path(prev, s, t)else:print("No path found.")def _recur_dfs(self, w, t, visited, prev):    # DFS的递归辅助函数if self.found:returnvisited[w] = Trueif w == t:self.found = Truereturnfor q in self.adj[w]:if not visited[q]:prev[q] = wself._recur_dfs(q, t, visited, prev)def _print_path(self, prev, s, t):    # 打印从 s 到 t 的路径,基于 prev 反向回溯。if prev[t] != -1 and t != s:self._print_path(prev, s, prev[t])print(t, end=' ')

1.2. 广度优先搜索(BFS)

BFS的定义:

广度优先搜索(Breadth-First-Search),简称为 BFS。它其实就是一种“地毯式”层层推进的搜索策略,即先查找离起始顶点最近的,然后是次近的,依次往外搜索。

核心辅助变量:

  1. visited是用来记录已经被访问的顶点,用来避免顶点被重复访问。如果顶点 q 被访问,那相应的 visited[q] 会被设置为 true。
  2. queue是一个队列,用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的,也就是说,我们只有把第 k 层的顶点都访问完成之后,才能访问第 k+1 层的顶点。当我们访问到第 k 层的顶点的时候,我们需要把第 k 层的顶点记录下来,稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以,我们用这个队列来实现记录的功能。
  3. prev用来记录搜索路径。当我们从顶点 s 开始,广度优先搜索到顶点 t 后,prev 数组中存储的就是搜索的路径。不过,这个路径是反向存储的。prev[w] 存储的是,顶点 w 是从哪个前驱顶点遍历过来的。比如,我们通过顶点 2 的邻接表访问到顶点 3,那 prev[3] 就等于 2。为了正向打印出路径,我们需要递归地来打印,你可以看下 print() 函数的实现方式。

时间和空间复杂度:

V 表示顶点的个数,E 表示边的个数。

  • 时间复杂度:O(V + E) ,简写为 O(E)

对于一个连通图来说,也就是说一个图中的所有顶点都是连通的,E 肯定要大于等于 V-1,所以,广度优先搜索的时间复杂度也可以简写为 O(E)

  • 空间复杂度:O(V)

1.3. 深度优先搜索(DFS)

DFS的概念:

  • 类似“走迷宫”;
  • 一路走到底,走不通就回退,再尝试其他路径;
  • 非最短路径,但能遍历所有可能路径。

特点:

  • 用递归方式实现,体现回溯思想;
  • 辅助变量同 BFS,额外用 found 控制递归终止。

时间和空间复杂度:

  • 时间复杂度: O(E)
  • 空间复杂度:O(V)

BFS vs DFS:

特性

BFS

DFS

搜索策略

按层次,逐层推进

一路深入,回退再尝试

是否找最短路径

✅ 是

❌ 不一定

实现方式

通常用队列实现

通常用递归或栈实现

时间复杂度

O(V + E)

O(V + E)

空间复杂度

O(V)

O(V)

推荐使用场景

路径最短查找、三度好友推荐等

遍历所有可能路径、连通性检


http://www.ppmy.cn/news/1669808.html

相关文章

Redis6为什么引入了多线程?

大家好,我是锋哥。今天分享关于【Redis6为什么引入了多线程?】面试题。希望对大家有帮助; Redis6为什么引入了多线程? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 Redis 6 引入多线程的主要目的是提升性能&#xf…

QML学习01(设置宽度、高度、坐标点、标题,信号与槽,键盘事件)

QML学习 1、前言2、QML3、QML和QWidget的区别3、QtQuick下的Windows应用4、总结 1、前言 记录一下QML学习的过程,方便自己日后回顾,也可以给有需要的人提供帮助。 2、QML QML是 Qt 框架中的一种声明式编程语言,专门用于快速设计和开发用户…

Windows软件插件-写mp3

下载本插件 本插件将PCM音频流编码为MP3,写入MP3音频文件。插件类型为DLL,可以在win32和MFC程序中使用。 使用方法 首先,加载本“写mp3”DLL,获得DLL模块句柄。 HMODULE hMp3 LoadLibrary(L"写mp3.dll");//加载写mp3…

《算法导论(第4版)》阅读笔记:p59-p75

《算法导论(第4版)》学习第 15 天,p59-p75 总结,总计 17 页。 一、技术总结 1. floor(向下取整) and ceiling(向上取整) For any real number x, we denote the greatest integer less than or equal to x by ⌊x⌋ (read ‘the floor of x’) and th…

红黑树和递归树

1. 红黑树(R-B Tree) 1.1. 平衡二叉查找树 背景: 普通二叉查找树(BST)问题: 在频繁插入/删除的动态更新场景下,BST 可能退化为链表,时间复杂度从 O(logn) 退化到 O(n)。 解决方…

深入探索 UTF-8 编码:从 Unicode 到字节的转换之旅

引言 为什么需要 UTF-8? 在计算机世界中,字符编码是连接人类语言与机器逻辑的桥梁。早期的 ASCII 编码仅支持英文字符,而 Unicode 的诞生解决了多语言兼容性问题。然而,Unicode 的定长编码(如 UTF-16 需 2-4 字节&…

[ctfshow web入门] web75

信息收集 scandir被禁用了 解题 cforeach(new DirectoryIterator("glob:///*") as $a){echo($a->__toString(). ); } ob_flush();cif ( $a opendir("glob:///*") ) {while ( ($file readdir($a)) ! false ) {echo $file."<br>";}c…

WordPress_Relevanssi Sql注入漏洞复现(CVE-2025-4396)

免责申明: 本文所描述的漏洞及其复现步骤仅供网络安全研究与教育目的使用。任何人不得将本文提供的信息用于非法目的或未经授权的系统测试。作者不对任何由于使用本文信息而导致的直接或间接损害承担责任。如涉及侵权,请及时与我们联系,我们将尽快处理并删除相关内容。 前…