Java图搜索算法详解:探索图论中的奥秘

embedded/2024/9/23 21:21:32/

图搜索算法是图论领域的重要内容,它在解决各种实际问题中起着关键作用。本文将详细介绍几种常见的Java图搜索算法,包括深度优先搜索(DFS)、广度优先搜索(BFS)以及Dijkstra算法,帮助读者深入理解图搜索算法的原理和应用。

1. 深度优先搜索(DFS)

深度优先搜索是一种递归的搜索算法,它从图的某一顶点出发,沿着一条路径尽可能深地搜索,直到到达最远的顶点,然后再回溯到上一个顶点,继续搜索其他路径。DFS通常使用栈来实现,其时间复杂度为O(V+E),其中V是顶点数,E是边数。

import java.util.*;public class DepthFirstSearch {private boolean[] visited;private List<List<Integer>> graph;public DepthFirstSearch(int n) {visited = new boolean[n];graph = new ArrayList<>();for (int i = 0; i < n; i++) {graph.add(new ArrayList<>());}}public void addEdge(int u, int v) {graph.get(u).add(v);}public void dfs(int u) {visited[u] = true;System.out.print(u + " ");for (int v : graph.get(u)) {if (!visited[v]) {dfs(v);}}}public static void main(String[] args) {DepthFirstSearch dfs = new DepthFirstSearch(5);dfs.addEdge(0, 1);dfs.addEdge(0, 2);dfs.addEdge(1, 3);dfs.addEdge(1, 4);dfs.dfs(0); // 从节点0开始深度优先搜索}
}

2. 广度优先搜索(BFS)

广度优先搜索是一种迭代的搜索算法,它从图的某一顶点出发,逐层地搜索,直到找到目标顶点或者遍历完所有顶点。BFS通常使用队列来实现,其时间复杂度同样为O(V+E)。

import java.util.*;public class BreadthFirstSearch {private boolean[] visited;private List<List<Integer>> graph;public BreadthFirstSearch(int n) {visited = new boolean[n];graph = new ArrayList<>();for (int i = 0; i < n; i++) {graph.add(new ArrayList<>());}}public void addEdge(int u, int v) {graph.get(u).add(v);}public void bfs(int u) {Queue<Integer> queue = new LinkedList<>();visited[u] = true;queue.offer(u);while (!queue.isEmpty()) {int cur = queue.poll();System.out.print(cur + " ");for (int v : graph.get(cur)) {if (!visited[v]) {visited[v] = true;queue.offer(v);}}}}public static void main(String[] args) {BreadthFirstSearch bfs = new BreadthFirstSearch(5);bfs.addEdge(0, 1);bfs.addEdge(0, 2);bfs.addEdge(1, 3);bfs.addEdge(1, 4);bfs.bfs(0); // 从节点0开始广度优先搜索}
}

3. Dijkstra算法

Dijkstra算法是一种用于计算图中单源最短路径的贪心算法,它通过维护一个优先队列来选择下一个要访问的顶点,并不断更新顶点到源顶点的最短距离。Dijkstra算法适用于边权值非负的有向图或无向图,其时间复杂度为O(V^2),其中V是顶点数。

import java.util.*;public class Dijkstra {private int[] dist;private boolean[] visited;private List<List<int[]>> graph;public Dijkstra(int n) {dist = new int[n];visited = new boolean[n];Arrays.fill(dist, Integer.MAX_VALUE);graph = new ArrayList<>();for (int i = 0; i < n; i++) {graph.add(new ArrayList<>());}}public void addEdge(int u, int v, int w) {graph.get(u).add(new int[] { v, w });}public void dijkstra(int src) {PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));dist[src] = 0;pq.offer(new int[] { src, 0 });while (!pq.isEmpty()) {int[] cur = pq.poll();int u = cur[0];if (visited[u]) continue;visited[u] = true;for (int[] edge : graph.get(u)) {int v = edge[0];int w = edge[1];if (!visited[v] && dist[u] + w < dist[v]) {dist[v] = dist[u] + w;pq.offer(new int[] { v, dist[v] });}}}}public static void main(String[] args) {Dijkstra dijkstra = new Dijkstra(5);dijkstra.addEdge(0, 1, 10);dijkstra.addEdge(0, 2, 5);dijkstra.addEdge(1, 3, 2);dijkstra.addEdge(2, 1, 3);dijkstra.addEdge(2, 3, 9);dijkstra.dijkstra(0); // 从节点0开始Dijkstra算法}
}

结论

Java图搜索算法是图论中的重要内容,掌握这些算法对于解决各种实际问题至关重要。通过本文的介绍和实例演示,读者可以更加深入地理解深度优先搜索、广度优先搜索和Dijkstra算法的原理和应用,为解决实际问题提供了强有力的工具和思路。

  感谢您阅读本文,欢迎“一键三连”。作者定会不负众望,按时按量创作出更优质的内容。
❤️ 1. 毕业设计专栏,毕业季咱们不慌,上千款毕业设计等你来选。


http://www.ppmy.cn/embedded/26108.html

相关文章

ES6之rest参数、扩展运算符

文章目录 前言一、rest参数二、扩展运算符 1.将数组转化为逗号分隔的参数序列2.应用总结 前言 rest参数与arguments变量相似。ES6引入rest参数代替arguments&#xff0c;获取函数实参。扩展运算符能将数组转化为参数序列。 一、rest参数 function namelist1() {console.log(ar…

Nginx从入门到精通

第一章> 1、概述 2、正反向代理 3、负载均衡 4、Nginx安装 第二章> 5、常用命令 6、实战总结 7、前端部署 ***************************************…

cartographer问题处理

问题1 : CMake Error: The following variables are used in this project, but they are set to NOTFOUND. Please set them or make sure they are set and tested correctly in the CMake files: GMOCK_LIBRARY (ADVANCED)linked by target "time_conversion_test&quo…

Android Studio的settings.gradle配置

pluginManagement { repositories { maven { url ‘https://maven.aliyun.com/nexus/content/groups/public/’} maven { url ‘https://maven.aliyun.com/nexus/content/repositories/gradle-plugin’} maven { url ‘https://maven.aliyun.com/nexus/content/repositories/ap…

Rust中的并发性:Sync 和 Send Traits

在并发的世界中&#xff0c;最常见的并发安全问题就是数据竞争&#xff0c;也就是两个线程同时对一个变量进行读写操作。但当你在 Safe Rust 中写出有数据竞争的代码时&#xff0c;编译器会直接拒绝编译。那么它是靠什么魔法做到的呢&#xff1f; 这就不得不谈 Send 和 Sync 这…

Flutter笔记:Widgets Easier组件库(3)使用按钮组件

Flutter笔记 Widgets Easier组件库&#xff08;3&#xff09;&#xff1a;使用按钮组件 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddre…

头歌:Spark案例剖析 - 谷歌网页排名引擎PageRank实战

第1关:海量数据导入:SparkSQL大数据导入处理 任务描述 工欲善其事必先利其器,大数据分析中最重要的是熟练掌握数据导入工具的使用方法。Spark SQL是Spark自带的数据库,本关你将应用Spark SQL的数据导入工具实现文本数据的导入。其中,graphx-wiki-vertices.txt文件中含有网…

Docker数据管理和Dockerfile

目录 一.数据管理 1.作用 &#xff08;1&#xff09;修改配置文件例如&#xff0c;nginx.conf /usr/local/nginx/conf/nginx.conf —>/container_nginx/conf/nginx.conf &#xff08;2&#xff09;容器内部产生的日志&#xff0c;如何收集将容器内部存方日志文件的目录挂…