鱼C论坛

 找回密码
 立即注册
查看: 717|回复: 70

[技术交流] 新手必看·BFS快速入门(鱼币~~~)

[复制链接]
回帖奖励 8 鱼币 回复本帖可获得 1 鱼币奖励! 每人限 1 次(中奖概率 20%)
发表于 2024-2-1 17:10:10 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 学习编程中的Ben 于 2024-2-1 22:43 编辑


Hello everyone!我寒假暂时回归嘻嘻! 顺手就写个BFS教程吧(其实是想赶紧升级,想到资深鱼油,多评点分吧!)

评分

参与人数 19荣誉 +71 鱼币 +46 贡献 +43 收起 理由
青出于蓝 + 3 + 3 + 3 感谢楼主无私奉献!
Mike_python小 + 8 + 5 鱼C有你更精彩^_^
Ewan-Ahiouy + 5 + 5 鱼C有你更精彩^_^
Gordon1 + 3
琅琊王朝 + 5 这么点鱼币?
sfqxx_小 + 5 + 3 申请精华吧
陈尚涵 + 5 + 5 + 1
python爱好者. + 5 + 3 鱼C有你更精彩^_^
liuhongrun2022 + 5 + 5 + 3
zhangjinxuan + 5 鱼C有你更精彩^_^

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-2-1 17:11:50 | 显示全部楼层
哈喽!欢迎来到编程的奇妙世界!BFS(广度优先搜索)是一种常用的图算法,可以用于解决许多问题。现在,让我来帮你快速入门BFS吧!

2.什么是BFS?

BFS是一种图遍历算法,它从图的某个指定顶点开始,逐层地遍历图中的所有顶点。具体来说,BFS首先遍历指定顶点的邻居顶点,然后再遍历邻居顶点的邻居顶点,以此类推。这种遍历过程类似于“波纹扩散”,所以叫做广度优先搜索。

3.如何实现BFS?

要实现BFS算法,我们需要使用一个队列来管理待遍历的顶点。具体步骤如下:

- 创建一个空队列,并将起始顶点入队。
- 创建一个空集合,用来记录已经被访问过的顶点。
- 当队列非空时,重复以下步骤:
  - 从队列中取出一个顶点,并标记为已访问。
  - 访问该顶点,并处理它。
  - 将该顶点的未访问邻居顶点加入队列。

4.举个例子吧!

假设我们有一个图,用邻接矩阵表示:

  1. graph = [[0, 1, 1, 0],
  2.          [1, 0, 0, 1],
  3.          [1, 0, 0, 0],
  4.          [0, 1, 0, 0]]
复制代码


其中,顶点0、1、2、3分别代表A、B、C、D。我们从顶点0(A)开始进行BFS遍历。

  1. from collections import deque

  2. def bfs(graph, start):
  3.     visited = set()  # 记录已访问的顶点
  4.     queue = deque()  # 创建队列
  5.     queue.append(start)  # 起始顶点入队
  6.    
  7.     while queue:
  8.         vertex = queue.popleft()  # 取出队首顶点
  9.         visited.add(vertex)  # 标记为已访问
  10.         
  11.         print("Visiting vertex:", vertex)  # 处理顶点
  12.         
  13.         neighbors = graph[vertex]  # 获取邻居顶点
  14.         for i in range(len(neighbors)):
  15.             if neighbors[i] == 1 and i not in visited:  # 如果邻居未访问过,则入队
  16.                 queue.append(i)

  17. # 测试代码
  18. graph = [[0, 1, 1, 0],
  19.          [1, 0, 0, 1],
  20.          [1, 0, 0, 0],
  21.          [0, 1, 0, 0]]
  22. bfs(graph, 0)
复制代码


上述代码会按照BFS的顺序输出访问的顶点。

希望这个简单的例子可以帮助你理解BFS算法!如果还有疑问,请随时提问哦!

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-2-1 17:12:42 | 显示全部楼层
这是挖坑还没写完吗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2024-2-1 17:13:35 | 显示全部楼层
中英文泡椒 发表于 2024-2-1 17:12
这是挖坑还没写完吗

是......

评分

参与人数 2荣誉 +10 贡献 +6 收起 理由
liuhongrun2022 + 5 + 3
陶远航 + 5 + 3 升级

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-2-1 17:14:48 | 显示全部楼层

哈哈哈这ai好烦
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-2-1 17:15:40 | 显示全部楼层
AI:我帮你写了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2024-2-1 18:10:10 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-2-1 18:20:20 | 显示全部楼层
支持
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-2-1 18:24:05 | 显示全部楼层
学习编程中的Ben 发表于 2024-2-1 18:10
@sfqxx @~风介~ @中英文泡椒 @人造人 @isdkz @琅琊王朝 @KeyError @Ewan-Ahiouy @yinda_peng

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2024-2-1 18:24:11 | 显示全部楼层

真看懂了吗?我自己都在反思要不要多讲一两个示例

评分

参与人数 3荣誉 +5 鱼币 +5 贡献 +6 收起 理由
rachel王 + 5 鱼C有你更精彩^_^
陶远航 + 3
liuhongrun2022 + 5 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2024-2-1 18:26:03 | 显示全部楼层

评个分吧!我想升级

点评

我很赞同!: 5.0
我很赞同!: 5
  发表于 2024-2-5 11:20

评分

参与人数 2荣誉 +4 贡献 +6 收起 理由
陶远航 + 3
liuhongrun2022 + 4 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-2-1 18:35:35 | 显示全部楼层
搬好板凳,围观中
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-2-1 18:54:55 | 显示全部楼层
宽度优先和广度优先是一个东西
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-2-1 18:56:10 | 显示全部楼层
DFS是深度优先搜索
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-2-1 18:56:54 | 显示全部楼层
另外,有人给我也评点分吗?马上就要到中级了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-2-1 19:00:31 | 显示全部楼层
学习编程中的Ben 发表于 2024-2-1 18:10
@sfqxx @~风介~ @中英文泡椒 @人造人 @isdkz @琅琊王朝 @KeyError @Ewan-Ahiouy @yinda_peng

这么快写好啦!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2024-2-1 19:14:43 | 显示全部楼层

所以叫做快速入门
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2024-2-1 19:15:25 | 显示全部楼层

包快不包会嘿嘿
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-2-1 19:16:03 | 显示全部楼层

效率忒高了,毕竟我刚刚看还是空白页哈哈
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-2-1 20:30:39 From FishC Mobile | 显示全部楼层
~来评分了~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-2-23 06:06

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表