Java图的广度优先搜索实现代码
学习文章要努力,但是不要急!今天的这篇文章《Java实现图的广度优先搜索基础代码》将会介绍到等等知识点,如果你想深入学习文章,可以关注我!我会持续更新相关文章的,希望对大家都能有所帮助!
答案:在Java中构建适合BFS的图结构通常采用邻接表,如Map
>,它高效支持稀疏图的边操作;BFS适用于最短路径等分层搜索场景,而DFS更适合路径存在性、环检测等深度探索任务;优化大型图BFS性能可选用ArrayDeque和HashSet、减少对象创建,并根据需要考虑并行化或分布式方案。

说起图的遍历,广度优先搜索(BFS)在Java里其实挺直观的,核心就是用队列(Queue)来管理待访问的节点,一层一层地往外探索,直到找到目标或者遍历完所有可达的节点。它就像水波纹一样,从中心向外扩散,确保你总是先访问离起点最近的节点。
解决方案
要实现BFS,我通常会先搭一个图的结构,邻接表是个不错的选择,因为它直观且效率高。然后,你需要一个队列来存放那些“等着被看一眼”的节点,再来一个集合记录“我已经来过”的节点,防止原地打转。
以下是一个基本的Java BFS实现:
import java.util.*;
public class GraphBFS {
// 使用邻接表表示图
private Map> adjList;
public GraphBFS() {
adjList = new HashMap<>();
}
// 添加节点
public void addNode(int node) {
adjList.putIfAbsent(node, new ArrayList<>());
}
// 添加边
public void addEdge(int source, int destination) {
// 确保节点存在
addNode(source);
addNode(destination);
// 对于无向图,双向添加
adjList.get(source).add(destination);
adjList.get(destination).add(source); // 如果是有向图,则只加这一行
}
// BFS实现
public void bfs(int startNode) {
if (!adjList.containsKey(startNode)) {
System.out.println("起始节点 " + startNode + " 不存在于图中。");
return;
}
Queue queue = new LinkedList<>(); // 存储待访问节点
Set visited = new HashSet<>(); // 存储已访问节点
queue.offer(startNode);
visited.add(startNode);
System.out.println("BFS遍历从节点 " + startNode + " 开始:");
while (!queue.isEmpty()) {
int currentNode = queue.poll(); // 取出队列头部节点
System.out.print(currentNode + " "); // 访问当前节点
// 遍历当前节点的所有邻居
for (int neighbor : adjList.getOrDefault(currentNode, Collections.emptyList())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor); // 将未访问的邻居加入队列
}
}
}
System.out.println("\nBFS遍历结束。");
}
public static void main(String[] args) {
GraphBFS graph = new GraphBFS();
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(2, 6);
graph.addEdge(3, 7);
graph.addEdge(4, 7); // 增加一个连接,让图更复杂
// 也可以添加一些孤立的节点,看看会不会被访问到 (如果不是从它们开始遍历的话)
graph.addNode(8);
graph.bfs(0); // 从节点0开始BFS
// graph.bfs(8); // 如果从8开始,它将是孤立的
}
} 如何在Java中构建适合BFS的图数据结构?
构建图结构,这事儿看似简单,但对后续的算法效率影响挺大。我个人偏爱用邻接表,特别是处理那些节点多但边不那么密集的图(也就是稀疏图)。想象一下,如果一个节点只有几个邻居,你用邻接矩阵,那一大片零矩阵看着就心累,空间浪费不说,遍历起来也得跳过好多无用的地方。
邻接表通常用 Map 来实现,键是节点,值是它所有邻居节点的列表。这种结构在添加边和查询邻居时都非常高效。比如,上面的代码里我就用了 Map 来存储图。如果你需要存储更复杂的节点对象或者边的属性,那么可以考虑 Map 或者 Map,其中 NodeObject 和 EdgeObject 是你自定义的类,包含节点ID、名称、权重等信息。关键在于,当你需要获取某个节点的所有邻居时,它能快速返回一个列表,而不是遍历整个矩阵。
BFS与DFS在图遍历中的应用场景有何不同?
说起来,BFS和DFS就像是图遍历领域的两位“老搭档”,各自有各自的脾气和擅长的活儿。
BFS嘛,它就像个“慢性子”,一层一层地往外摸索,所以找最短路径(尤其是在边权都一样的情况下)它可是一把好手。比如,你想知道从你家到最近的咖啡馆要经过几条街,BFS就能告诉你最少要走几步。它还常用于:
- 最短路径问题:在无权图中,BFS能找到从起点到所有可达节点的最短路径。
- 社交网络分析:找出某个用户在多少步内能接触到哪些人。
- Web爬虫:从一个页面开始,一层层地抓取所有链接到的页面。
- 迷宫求解:找出从起点到终点的最短路径。
DFS呢,它就显得更“激进”,一条路走到黑,不撞南墙不回头。所以,当你需要探索一条完整的路径,或者检查图里有没有环这种事,DFS就显得更有优势。它通常用于:
- 路径查找:判断两个节点之间是否存在路径。
- 拓扑排序:对有向无环图(DAG)进行线性排序。
- 检测环:在有向图或无向图中检测是否存在环。
- 连通分量:找出图中的所有连通分量(无向图)或强连通分量(有向图)。
- 回溯算法:很多回溯问题都可以看作是图的DFS遍历。
简单来说,BFS是“广度优先”,适用于需要找到最短路径或分层探索的场景;DFS是“深度优先”,适用于需要探索完整路径、检测循环或进行拓扑排序的场景。选择哪个,就看你的具体需求了。
如何优化Java中大型图的BFS性能?
当图的规模变得巨大时,原先那套“朴素”的BFS实现可能就有点吃力了。我碰到过好几次,一开始觉得代码没问题,一跑大数据就卡顿。这时候,优化就得提上日程了。
首先,数据结构的选择至关重要。我一般会倾向于用ArrayDeque来做队列,它比LinkedList在作为队列时性能更好,因为它内部是数组实现,避免了链表节点频繁创建和垃圾回收的开销。至于已访问集合,HashSet是我的首选,它的平均查找效率是O(1),这在大图里能省下不少时间。
其次,要考虑内存管理。频繁的对象创建和销毁会给JVM的垃圾回收器带来很大压力。如果你的节点或边对象很复杂,考虑使用对象池或者复用机制,减少不必要的对象实例化。对于特别大的图,如果能把图数据本身优化一下存储,比如用更紧凑的表示(例如,直接用数组存储邻接信息,而不是Map),或者考虑内存映射文件,那效果会更明显。
再者,如果图是静态的(不经常变化),并且你需要从多个起点执行BFS,可以考虑预计算一些信息,或者将图序列化到磁盘,需要时再加载。当然,如果图真的大到单机都搞不定,那可能就得考虑分布式BFS或者并行化了,比如使用多线程并行处理不同分支的搜索,或者将图数据分片存储在多台机器上,利用像Apache Giraph这样的图计算框架。不过这通常会带来额外的复杂性,得看具体场景值不值得投入。总之,优化是多方面的,没有一劳永逸的方案,得根据你的图的特性和应用场景来权衡。
今天关于《Java图的广度优先搜索实现代码》的内容介绍就到此结束,如果有什么疑问或者建议,可以在golang学习网公众号下多多回复交流;文中若有不正之处,也希望回复留言以告知!
谷歌邮箱后缀格式是什么?
- 上一篇
- 谷歌邮箱后缀格式是什么?
- 下一篇
- 即梦AI循环动画制作与无缝技巧详解
-
- 文章 · java教程 | 4小时前 | nio · Java教程 · 文件系统 · java FileStore supportsFileAttributeView 文件属性视图
- Java FileStore.supportsFileAttributeView 怎样判断存储卷支持哪些文件属性视图
- 176浏览 收藏
-
- 文章 · java教程 | 4小时前 | Java · 日期时间 · java locale LocalDate WeekFields weekOfMonth DayOfWeek
- Java WeekFields.weekOfMonth 怎样按地区规则计算月份中的周数
- 274浏览 收藏
-
- 文章 · java教程 | 5小时前 | Java · java MethodType lastParameterType
- Java MethodType.lastParameterType 怎样读取方法类型的最后一个参数
- 267浏览 收藏
-
- 文章 · java教程 | 6小时前 | 反射 · 迁移 · Java教程 · java 方法句柄 MethodHandle MethodType MethodHandles.empty
- Java MethodHandles.empty 怎样构造接受参数但不执行操作的方法句柄
- 387浏览 收藏
-
- 文章 · java教程 | 6小时前 |
- Java MethodHandles.arrayConstructor 怎样构造指定类型的数组创建句柄
- 296浏览 收藏
-
- 文章 · java教程 | 7小时前 | Java · 字符集 · java 字符集编码 CharsetEncoder isLegalReplacement 替代字节
- Java CharsetEncoder.isLegalReplacement 怎样检查替代字节序列能否被编码器接受
- 365浏览 收藏
-
- 文章 · java教程 | 8小时前 | Java · nio · java FileStore getBlockSize 文件系统块大小
- Java FileStore.getBlockSize 怎样查询文件系统块大小
- 428浏览 收藏
-
- 文章 · java教程 | 9小时前 | Java教程 · 日期时间 · java LocalDate WeekFields weekBasedYear weekOfWeekBasedYear ISO周
- Java WeekFields.weekBasedYear 怎样读取周所属年份而不是日历年份
- 401浏览 收藏
-
- 文章 · java教程 | 9小时前 | Java教程 · java optional JPMS Mainclass ModuleDescriptor module-info.class
- Java ModuleDescriptor.mainClass 怎样读取模块声明的主类名称
- 109浏览 收藏
-
- 文章 · java教程 | 10小时前 | Java · java ThreadMXBean ThreadInfo isInNative
- Java ThreadInfo.isInNative 怎样判断线程是否在执行本地方法
- 132浏览 收藏
-
- 文章 · java教程 | 11小时前 | 标准库 · Java教程 · java 反射 MethodHandle MethodType parameterArray
- Java MethodType.parameterArray 怎样复制方法类型的参数类型数组
- 397浏览 收藏
-
- 文章 · java教程 | 12小时前 | 标准库 · Java教程 · java 默认值 ZeRO MethodHandles MethodHandle
- Java MethodHandles.zero 怎样生成返回指定类型零值的方法句柄
- 206浏览 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 543次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 516次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 500次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 485次学习
-
- PubMedQA
- 深入了解PubMedQA生物医学问答数据集,涵盖其核心功能、使用方法及在临床决策、药物研发等场景的应用,助力提升NLP模型性能。
- 1100次使用
-
- H2O EvalGPT
- H2O EvalGPT是H2O.ai推出的开源LLM评估平台,提供详细的大模型性能排行榜、行业特定基准测试及A/B测试功能,助您快速选择最适合项目的高性能大语言模型。
- 1095次使用
-
- LMArena
- LMArena是加州大学伯克利分校推出的AI模型匿名评测平台。通过盲测投票机制,用户可对比不同大模型回答并生成实时排行榜,助力开发者优化模型及用户选择最佳AI工具。
- 1266次使用
-
- HELM
- 深入了解斯坦福推出的HELM(Holistic Evaluation of Language Models)大模型评测体系。本文解析其核心功能、安装配置步骤及应用场景,涵盖准确性、公平性、鲁棒性等多维度指标,助力开发者全面优化语言模型性能。
- 1205次使用
-
- MMBench
- MMBench是由上海人工智能实验室等机构联合推出的多模态基准测试平台,提供细粒度能力评估、大规模数据集及VLMEvalKit工具。本文详细介绍其核心功能、安装使用方法及应用场景,助力开发者全面评估多模态模型性能。
- 1051次使用
-
- Java 时间格式兼容多个输入格式的方法
- 2026-10-18 501浏览
-
- Java try-with-resources 多个资源关闭顺序是什么
- 2026-09-10 501浏览
-
- 矩阵主副对角线快速定位技巧
- 2026-05-31 501浏览
-
- Java多态优化流程代码与行为分发改进
- 2026-05-26 501浏览
-
- JVM 类元数据双亲委派链表深度解析
- 2026-05-21 501浏览

