当前位置: 首页 > 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 算法...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...