网站架构演变过程,网站域名解析时间,自己开设计工作室,广州网站排名优化费用文章目录 理解图的基本概念学习图的遍历算法学习最短路径算法案例分析#xff1a;使用 Dijkstra 算法找出最短路径结论 #x1f389;欢迎来到数据结构学习专栏~探索图结构#xff1a;从基础到算法应用 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒#x1f379;✨博客主页#xff1a;I… 文章目录 理解图的基本概念学习图的遍历算法学习最短路径算法案例分析使用 Dijkstra 算法找出最短路径结论 欢迎来到数据结构学习专栏~探索图结构从基础到算法应用 ☆* o(≧▽≦)o *☆嗨~我是IT·陈寒✨博客主页IT·陈寒的博客该系列文章专栏数据结构学习其他专栏Java学习路线 Java面试技巧 Java实战项目 AIGC人工智能 数据结构学习文章作者技术和水平有限如果文中出现错误希望大家能指正 欢迎大家关注 ❤️ 图结构是计算机科学中的一项重要内容它能够模拟各种实际问题并在网络、社交媒体、地图等领域中具有广泛的应用。本文将引导你深入了解图的基本概念、遍历算法以及最短路径算法的实际应用。
理解图的基本概念
顶点和边 图由一组顶点vertices和连接这些顶点的边edges构成。边可以带有权重weight代表两个顶点之间的关系强度或成本。 有向图与无向图 有向图中的边是有方向的从一个顶点指向另一个顶点无向图中的边没有方向是双向的。 权重图 权重图中的边带有权重用于表示顶点之间的距离、代价等信息。
学习图的遍历算法
深度优先搜索DFS DFS 是一种遍历图的算法它从一个起始顶点开始递归地访问相邻顶点直到无法继续为止。DFS 的应用包括查找连通分量、拓扑排序等。 广度优先搜索BFS BFS 也是一种遍历图的算法它从起始顶点开始逐层访问其邻居顶点。BFS 的应用包括查找最短路径、社交网络中的“六度分隔”等。
学习最短路径算法
Dijkstra 算法 Dijkstra 算法用于查找带权重的图中从一个起始顶点到其他顶点的最短路径。它采用贪心策略每次选择当前距离最近的顶点进行拓展。Dijkstra 算法的应用包括路由算法、地图导航等。 Bellman-Ford 算法 Bellman-Ford 算法也用于查找图中的最短路径但与 Dijkstra 算法不同它适用于带有负权边的图。Bellman-Ford 算法通过进行多次松弛操作逐步逼近最短路径。
案例分析使用 Dijkstra 算法找出最短路径
假设我们有一个城市之间的道路网络每条道路都有对应的时间权重。我们想要找到从起始城市到目标城市的最短时间路径。以下是使用 Dijkstra 算法实现这个目标的示例代码
import java.util.*;public class ShortestPath {public MapString, Integer findShortestPath(MapString, MapString, Integer graph, String start, String end) {PriorityQueueString pq new PriorityQueue(Comparator.comparingInt(graph.get(start)::get));MapString, Integer distances new HashMap();MapString, String predecessors new HashMap();distances.put(start, 0);graph.keySet().forEach(city - {if (!city.equals(start)) {distances.put(city, Integer.MAX_VALUE);predecessors.put(city, null);}pq.offer(city);});while (!pq.isEmpty()) {String current pq.poll();for (Map.EntryString, Integer neighbor : graph.get(current).entrySet()) {int newDistance distances.get(current) neighbor.getValue();if (newDistance distances.get(neighbor.getKey())) {distances.put(neighbor.getKey(), newDistance);predecessors.put(neighbor.getKey(), current);}}}MapString, Integer shortestPath new HashMap();String current end;while (current ! null) {shortestPath.put(current, distances.get(current));current predecessors.get(current);}return shortestPath;}public static void main(String[] args) {ShortestPath shortestPath new ShortestPath();MapString, MapString, Integer graph new HashMap();graph.put(A, Map.of(B, 5, C, 2));graph.put(B, Map.of(D, 1, E, 6));graph.put(C, Map.of(B, 1, D, 4));graph.put(D, Map.of(E, 1));graph.put(E, Collections.emptyMap());String start A;String end E;MapString, Integer result shortestPath.findShortestPath(graph, start, end);System.out.println(Shortest path from start to end : result);}
}结论
图结构在现实世界中有着丰富的应用从社交网络到交通系统。了解图的基本概念、遍历算法以及最短路径算法可以让你更好地理解和处理与图相关的问题。通过学习这些知识你将能够在解决实际问题时更加灵活和高效地运用图结构和算法。 结尾 ❤️ 感谢您的支持和鼓励 您可能感兴趣的内容 【Java面试技巧】Java面试八股文 - 掌握面试必备知识目录篇【Java学习路线】2023年完整版Java学习路线图【AIGC人工智能】Chat GPT是什么初学者怎么使用Chat GPT需要注意些什么【Java实战项目】SpringBootSSM实战打造高效便捷的企业级Java外卖订购系统【数据结构学习】从零起步学习数据结构的完整路径
