当前位置: 首页 > news >正文

探索图结构:从基础到算法应用

文章目录

      • 理解图的基本概念
      • 学习图的遍历算法
      • 学习最短路径算法
      • 案例分析:使用 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 Map<String, Integer> findShortestPath(Map<String, Map<String, Integer>> graph, String start, String end) {PriorityQueue<String> pq = new PriorityQueue<>(Comparator.comparingInt(graph.get(start)::get));Map<String, Integer> distances = new HashMap<>();Map<String, 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.Entry<String, 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);}}}Map<String, 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();Map<String, Map<String, 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";Map<String, 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实战项目】SpringBoot+SSM实战:打造高效便捷的企业级Java外卖订购系统
  • 【数据结构学习】从零起步:学习数据结构的完整路径

在这里插入图片描述

相关文章:

探索图结构:从基础到算法应用

文章目录 理解图的基本概念学习图的遍历算法学习最短路径算法案例分析&#xff1a;使用 Dijkstra 算法找出最短路径结论 &#x1f389;欢迎来到数据结构学习专栏~探索图结构&#xff1a;从基础到算法应用 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒&#x1f379;✨博客主页&#xff1a;I…...

Redis之GEO类型解读

目录 基本介绍 基本命令 geoadd 命令 geopos 命令 geodist 命令 georadius 命令 georadiusbymember 命令 geohash 命令 基本介绍 GEO 主要用于存储地理位置信息&#xff08;纬度、经度、名称&#xff09;添加到指定的key中。该功能在 Redis 3.2 版本新增。 GEO&…...

uniapp 微信小程序 路由跳转

保留当前页面&#xff0c;跳转到应用内的某个页面&#xff0c;使用uni.navigateBack可以返回到原页面 //在起始页面跳转到test.vue页面并传递参数 uni.navigateTo({url: test?id1&name"lisa" }); uni.redirectTo(OBJECT) 关闭当前页面&#xff0c;跳转到应用…...

【android12-linux-5.1】【ST芯片】HAL移植后没调起来

ST传感器芯片HAL按官方文档移植后&#xff0c;测试一直掉不起来&#xff0c;加的日志没出来。经过分析&#xff0c;是系统自带了一个HAL&#xff0c;影响的。 按照官方文档&#xff0c;移植HAL后&#xff0c;在/device/<vendor\>/<board\>/device.mk*路径增加PROD…...

Redis Lua脚本执行原理和语法示例

Redis Lua脚本语法示例 文章目录 Redis Lua脚本语法示例0. 前言参考资料 1. Redis 执行Lua脚本原理1.1. 对Redis源码中嵌入Lua解释器的简要解析&#xff1a;1.2. Redis Lua 脚本缓存机制 2. Redis Lua脚本示例1.1. 场景示例1. 请求限流2. 原子性地从一个list移动元素到另一个li…...

百望云华为云共建零售数字化新生态 聚焦数智新消费升级

零售业是一个充满活力和创新的行业&#xff0c;但也是当前面临很大新挑战和新机遇的行业。数智新消费时代&#xff0c;数字化转型已经成为零售企业必须面对的重要课题。 8 月 20 日-21日&#xff0c;以“云上创新 韧性增长”为主题的华为云数智新消费创新峰会2023在成都隆重召…...

JMETER基本原理

Jmeter基本原理是建立一个线程池&#xff0c;多线程运行取样器产生大量负载&#xff0c;在运行过程中通过断言来验证结果的正确性&#xff0c;可以通过监听来记录测试结果&#xff1b; JMETER是运行在JVM虚拟机上的&#xff0c;每个进程的开销比loadrunner的进程开销大&#x…...

elementUI自定义上传文件 前端后端超详细过程

下面是使用Element UI自定义上传文件的前后端详细过程&#xff1a; 前端过程&#xff1a; 引入Element UI组件库&#xff1a;在前端项目中引入Element UI库&#xff0c;可以通过CDN引入或者通过npm安装并导入。 创建上传组件&#xff1a;在前端代码中创建一个上传组件&#x…...

快速排序笔记

一、quick_sort方法中如果 il,jr 会死循环的分析 1、示例代码 void quick_sort(int a[],int l,int r){if(l>r) return;int il,jr; //此处设置会导致死循环int x num[(lr)>>1];while(i<j){while(a[i] <x); //死循环的地方while(a[--j] >x);if(i<j) swap(a…...

JAVA:(JSON反序列化Long变成了Integer)java.lang.Integer cannot be cast to java.lang.Long

困扰了好几个小时。。。 场景&#xff1a;mybatisplus从数据库取数据&#xff0c;只是用了最基础的 LambdaQueryWrapper 来查询&#xff0c;实体类如下。 TableField(typeHandler JacksonTypeHandler.class) private Set<Long> ids; 得到的Set数据却是Set<Integer…...

ui设计师简历自我评价(合集)

UI设计最新面试题及答案 1、说说你是怎么理解UI的? UI是最直观的把产品展示展现在用户面前的东西&#xff0c;是一个产品的脸面。人开始往往是先会先喜欢上美好的事物后&#xff0c;在去深究内在的东西的。 那么也就意味着一个产品的UI首先要做的好看&#xff0c;无论风格是…...

Nginx 反向代理

一. Nginx 反向代理 1.1 反向代理介绍 在计算机网络中&#xff0c;反向代理一般指代理服务器&#xff0c;其首先代替内网的服务器接收客户端请求 并从一个或多个服务器检索资源&#xff0c;然后将这些资源返回给客户端。在客户端看来&#xff0c;这些资 源就好像来自代理服务…...

[论文阅读笔记25]A Comprehensive Survey on Graph Neural Networks

这是一篇GNN的综述, 发表于2021年的TNNLS. 这篇博客旨在对GNN的基本概念做一些记录. 论文地址: 论文 1. 引言, 背景与定义 对于图像数据来说, CNN具有平移不变性和局部连接性, 因此可以在欧氏空间上良好地学习. 然而, 对于具有图结构的数据(例如社交网络 化学分子等)就需要用…...

iview时间控件 动态不可选日期 可选择24小时范围内 时间往后退24小时

演示 html 设定 起始时间 触发on-change 方法结束时间 options 动态设置不可选择的日期。 <!-- 起始时间 --> <FormItem :label"$t(startTime)" prop"startTime"><DatePickertransfertype"datetime":placeholder"$t(pleas…...

Rest学习环境搭建:服务消费者

建一个子模块 导入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache…...

JVM内存模型介绍

内存模型 内存模型如下图所示 堆 堆是Java虚拟机所管理的内存最大一块。堆是所有线程共享的一块内存区域&#xff0c;在虚拟机启动时创建。此内存区域唯一的目的就是存放对象实例。所有的对象实例都在这里分配内存 Java堆是垃圾收集器管理的主要区域。从内存回收的角度来看&am…...

2000-2021年地级市产业升级、产业结构高级化面板数据

2000-2021年地级市产业升级、产业结构高级化面板数据 1、时间&#xff1a;2000-2021年 2、范围&#xff1a;地级市 3、指标&#xff1a;年份、地区、行政区划代码、地区、所属省份、地区生产总值、第一产业增加值、第二产业增加值、第三产业增加值、第一产业占GDP比重、第二…...

Java实现密码加密实现步骤【bcrypt算法】

一、SpringBoot和SSM框架均可实现密码加密的方法 在Spring Boot和SSM中实现密码加密可以使用bcrypt算法。bcrypt是一种密码哈希函数&#xff0c;通过将密码与随机生成的盐值进行混合&#xff0c;然后再进行多次迭代的计算&#xff0c;最终生成一个安全的哈希密码。 下面是使用…...

商城-学习整理-集群-K8S(二十三)

目录 一、k8s 集群部署1、k8s 快速入门1&#xff09;、简介2&#xff09;、架构1、整体主从方式2、Master 节点架构3、Node 节点架构 3&#xff09;、概念4&#xff09;、快速体验1、安装 minikube2、体验 nginx 部署升级 5&#xff09;、流程叙述 2、k8s 集群安装1、kubeadm2、…...

MATLAB算法实战应用案例精讲-【深度学习】强化学习

目录 基础知识点 马尔科夫决策过程 策略梯度定理 蒙特卡洛策略梯度定理 REINFORCE 算法...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...