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

22_图论中的高级数据结构

菜鸟:老鸟,我最近在处理一个网络节点数据的问题,发现代码运行得特别慢。你能帮我看看有什么优化的方法吗?

老鸟:当然可以。你处理的是图结构对吗?你是如何存储和操作这些节点的?

菜鸟:是的,我用的是邻接矩阵存储的方式,但是在查询和更新时,感觉性能很糟糕。

老鸟:邻接矩阵在某些情况下确实会有性能瓶颈。今天我可以给你介绍几个图论中的高级数据结构,比如邻接表、优先队列、和Dijkstra算法等等,这些可以大大提升你的操作效率。

渐进式介绍概念

菜鸟:听起来不错,能先讲讲邻接表吗?

老鸟:好的。邻接表是一种更为内存友好的图表示方法。相比邻接矩阵,邻接表的空间复杂度是O(V + E),其中V是顶点数,E是边数。

在邻接表中,每个顶点都会有一个列表,列表中存储与该顶点相邻的所有顶点。以下是一个简单的示例:

# 邻接表的表示方法
graph = {'A': ['B', 'C'],'B': ['A', 'D', 'E'],'C': ['A', 'F'],'D': ['B'],'E': ['B', 'F'],'F': ['C', 'E']
}

菜鸟:这个看起来更直观一些,查询一个顶点的邻居也很方便。

老鸟:是的,而且插入和删除操作也相对简单。让我们继续深入一些,看看如何使用邻接表进行图的遍历。

代码示例与分析

老鸟:以下是一个使用邻接表进行深度优先搜索(DFS)的示例:

def dfs(graph, start, visited=None):if visited is None:visited = set()visited.add(start)print(start)for next in graph[start] - visited:dfs(graph, next, visited)return visited# 使用DFS遍历图
dfs(graph, 'A')

菜鸟:这里的visited是用来记录访问过的节点吗?

老鸟:没错,通过这个集合,我们可以避免重复访问节点,从而防止死循环。类似地,我们还可以实现广度优先搜索(BFS)。

from collections import dequedef bfs(graph, start):visited = set()queue = deque([start])while queue:vertex = queue.popleft()if vertex not in visited:print(vertex)visited.add(vertex)queue.extend(graph[vertex] - visited)return visited# 使用BFS遍历图
bfs(graph, 'A')

问题与优化

菜鸟:这些遍历方法确实很有效,那在处理更复杂的图问题时,比如最短路径,该怎么优化呢?

老鸟:对于最短路径问题,Dijkstra算法是一个很好的选择。它使用优先队列来优化路径搜索过程。

import heapqdef dijkstra(graph, start):pq = [(0, start)]distances = {vertex: float('infinity') for vertex in graph}distances[start] = 0while pq:current_distance, current_vertex = heapq.heappop(pq)if current_distance > distances[current_vertex]:continuefor neighbor in graph[current_vertex]:distance = current_distance + graph[current_vertex][neighbor]if distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(pq, (distance, neighbor))return distances# 定义图,边的权重
weighted_graph = {'A': {'B': 1, 'C': 4},'B': {'A': 1, 'D': 2, 'E': 5},'C': {'A': 4, 'F': 1},'D': {'B': 2},'E': {'B': 5, 'F': 2},'F': {'C': 1, 'E': 2}
}# 计算最短路径
print(dijkstra(weighted_graph, 'A'))

菜鸟:这个算法看起来很复杂,但也很强大。优先队列在这里起到了很大的作用。

老鸟:是的,优先队列帮助我们有效地找到当前最短路径,从而优化了整体算法的性能。

适用场景与误区

菜鸟:这些高级数据结构有什么特定的应用场景吗?

老鸟:当然有。比如,Dijkstra算法适用于加权无负边的图,广泛应用于网络路由、地图导航等领域。而邻接表适用于稀疏图,它在空间复杂度和遍历效率上都非常优秀。

至于误区,常见的一个误区是没有考虑到算法的适用范围,比如在负权图中使用Dijkstra算法就会导致错误结果。在这种情况下,应该使用Bellman-Ford算法。

总结与延伸阅读

老鸟:今天我们讨论了邻接表、DFS、BFS、以及Dijkstra算法。这些都是图论中的高级数据结构和算法,适用于各种复杂的图处理场景。你可以参考以下资源继续深入学习:

  • 《算法导论》 - Thomas H. Cormen
  • 《数据结构与算法分析》 - Mark Allen Weiss
  • LeetCode上的图论问题

希望这些内容对你有所帮助,如果有任何问题,随时来找我讨论!

菜鸟:谢谢老鸟,我会继续学习这些高级数据结构的!

相关文章:

22_图论中的高级数据结构

菜鸟&#xff1a;老鸟&#xff0c;我最近在处理一个网络节点数据的问题&#xff0c;发现代码运行得特别慢。你能帮我看看有什么优化的方法吗&#xff1f; 老鸟&#xff1a;当然可以。你处理的是图结构对吗&#xff1f;你是如何存储和操作这些节点的&#xff1f; 菜鸟&#xf…...

axure判断

在auxre中我们也可以实现判断的功能&#xff0c;当目标等于什么内容时则执行下方的功能。 一、判断输入框中是否有值 画布添加一个输入框、一个文本标签删除其中内容&#xff0c;添加一个按钮&#xff0c;输入框命名为【文本显示】文本标签命名为【提示】 给按钮新增一个交互…...

【开源大模型生态7】华为的盘古大模型

鹏程盘古模型是全球首个全开源2000亿参数的自回归中文预训练语言大模型&#xff0c;在知识问答、知识检索、知识推理、阅读理解等文本生成领域表现突出。 2070亿参数&#xff0c;64层。 这里注意几个概念。 参数&#xff08;Parameters&#xff09;&#xff1a; 参数是指构成模…...

SprinBoot+Vue远程教育网站的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍&#xff1a;CSDN认证博客专家&#xff0c;CSDN平台Java领域优质…...

docker的基本操作

目录 一&#xff0c;应用部署 创建容器 进入容器 创建有端口的容器 通过ssh进入容器 二、镜像操作 搜索镜像 拉取镜像 查看本地镜像 删除镜像 导入镜像 三、容器操作 创建并启动容器 使用 docker run 命令创建并启动一个容器 创建一个有端口号的容器 查看正在运…...

理解 RabbitMQ:生产者、连接、通道、交换机、队列与消费者的消息流

在分布式消息系统中&#xff0c;RabbitMQ 是一个非常流行的消息代理。它的核心理念是解耦应用程序的生产者和消费者&#xff0c;使得消息能够可靠地从一方传递到另一方。本文将带你深入了解 RabbitMQ 中 生产者、连接、通道、交换机、队列 和 消费者 之间的消息流&#xff0c;并…...

【截图服务 +打包】pkg打包 puppeteer

目录 最后结论 windows打包成服务 定制executablePath 服务遇到的问题 使用java开一个线程启动 遇到的问题与解决 版本匹配问题 打出包后的运行报错问题 linux下的安装 安装n 库缺少 程序运行后的报错 制作 运行报错与修改后成功 参考文档 最后结论 pkg -t win…...

深入理解Servlet的并发处理机制小波制图流程图

在Java Web开发中&#xff0c;Servlet是处理HTTP请求的核心组件。理解Servlet如何处理并发请求对于开发高性能Web应用至关重要。本文将深入探讨Servlet的生命周期、实例化过程以及多线程处理机制。 Servlet的生命周期和实例化 Servlet遵循单例模式&#xff0c;对于每个Servle…...

Ajax和XMLHttpRequest之间的关系

Ajax和XMLHttpRequest之间的关系是非常密切的。Ajax&#xff08;Asynchronous JavaScript and XML&#xff09;是一种网页开发技术&#xff0c;用于创建交互式的应用程序或网站。而XMLHttpRequest是Ajax的核心技术之一。 XMLHttpRequest&#xff1a;这是一个JavaScript对象&…...

Linxu系统:kill命令

1、命令详解&#xff1a; kill命令是用于向进程发送信号&#xff0c;通常用来终止某个指定PID服务进程&#xff0c;kill命令可以发送不同的信号给目标进程&#xff0c;来实现不同的操作&#xff0c;如果不指定信号&#xff0c;默认会发送 TERM 信号&#xff08;15&#xff09;&…...

解决缺少genconfig

编译鸿蒙L0系统时&#xff0c;遇到报错&#xff1a; [OHOS INFO] Returned 127. [OHOS INFO] stderr: [OHOS INFO] [OHOS INFO] env: “genconfig”: 没有那个文件或目录 [OHOS INFO] [OHOS INFO] See //kernel/liteos_m/BUILD.gn:34:1: whence it was imported. [OHOS INFO] …...

百易云资产管理运营系统 house.save.php SQL注入漏洞

1 产品简介 百易云资产管理运营系统&#xff0c;是专门针对企业不动产资产管理和运营需求而设计的一套综合解决方案。该系统能够覆盖资产的全生命周期管理&#xff0c;包括资产的登记、盘点、评估、处置等多个环节&#xff0c;同时提供强大的运营分析功能&#xff0c;帮助企业…...

【安卓13 源码】Input子系统(3) - EventHub增加设备的流程

由前面的分析知道&#xff0c;在创建inputreader 线程的时候&#xff0c;会去循环执行 looponce 方法。主要的处理工作是&#xff1a; 通过 getEvents() 从 EventHub 获取未处理的事件&#xff0c;这些事件分为两类&#xff1a;一类是原始输入事 件即从设备节点中读取出的原始…...

基于JAVA+SpringBoot+Vue的网上商城系统的设计与实现

基于JAVASpringBootVue的网上商城系统的设计与实现 前言 ✌全网粉丝20W,csdn特邀作者、博客专家、CSDN[新星计划]导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末附源码下载链接&#x1…...

Mysql基础练习题 1729.求关注者的数量 (力扣)

编写解决方案&#xff0c;对于每一个用户&#xff0c;返回该用户的关注者数量。 #按 user_id 的顺序返回结果表 题目链接&#xff1a; https://leetcode.cn/problems/find-followers-count/description/ 建表插入语句&#xff1a; Create table If Not Exists Followers(us…...

【鸿蒙HarmonyOS NEXT】页面和自定义组件生命周期

【鸿蒙HarmonyOS NEXT】页面和自定义组件生命周期 一、环境说明二、页面和自定义组件生命周期三、示例代码加以说明四、小结 一、环境说明 DevEco Studio 版本&#xff1a; API版本&#xff1a;以12为主 二、页面和自定义组件生命周期 需要明确几个概念&#xff1a; 页面…...

Node.js Express 框架

Node.js Express 框架 介绍 Express 是一个快速、开放、极简的 Node.js Web 框架。它为构建 Web 应用程序和服务提供了一个强大的工具集,使得开发过程更加高效和便捷。Express 的设计哲学是提供一个最小的 API,让开发者可以轻松地构建自定义的 Web 应用程序。它被广泛用于构…...

生日贺卡录放音芯片,多段音频录音ic生产厂商,NVF04M-32minute

可以录音播放的生日贺卡与传统的纸质贺卡相比&#xff0c;它有着创意以及个性的特点&#xff0c;仅需少量的电子元器件&#xff0c;即可实现录音功能&#xff0c;搭配上文字&#xff0c;让声音存储在生日贺卡里&#xff0c;让贺卡也变得有温度&#xff0c;祝福我想亲口对TA说。…...

电影《西施新传》首映礼,九月金秋全国正式公映

2024年9月1日&#xff0c;古装谋略情感影片《西施新传》在无锡大世界影城中山路IMAX激光店举办首映礼。电影《西施新传》根据作家沈雅琴、笔名一蝶的同名小说改编&#xff0c;以家喻户晓四大美人之首的西施为主人公&#xff0c;讲述了春秋末期吴越战争的故事。越国败于吴国&…...

【H2O2|全栈】关于CSS(1)CSS基础(一)

目录 CSS基础知识 前言 准备工作 啥是CSS&#xff1f; 如何引用CSS&#xff1f; 选择器 通配符选择器 类名&#xff08;class&#xff09;选择器 id选择器 CSS解析顺序&#xff08;优先级&#xff09; 常见CSS标签&#xff08;一&#xff09; 字体属性 font-style…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...

aardio 自动识别验证码输入

技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”&#xff0c;于是尝试整合图像识别与网页自动化技术&#xff0c;完成了这套模拟登录流程。核心思路是&#xff1a;截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...

SpringCloud优势

目录 完善的微服务支持 高可用性和容错性 灵活的配置管理 强大的服务网关 分布式追踪能力 丰富的社区生态 易于与其他技术栈集成 完善的微服务支持 Spring Cloud 提供了一整套工具和组件来支持微服务架构的开发,包括服务注册与发现、负载均衡、断路器、配置管理等功能…...

Modbus转ETHERNET IP网关:快速冷却系统的智能化升级密钥

现代工业自动化系统中&#xff0c;无锡耐特森Modbus转Ethernet IP网关MCN-EN3001扮演着至关重要的角色。通过这一技术&#xff0c;传统的串行通讯协议Modbus得以在更高速、更稳定的以太网环境中运行&#xff0c;为快速冷却系统等关键设施的自动化控制提供了强有力的支撑。快速冷…...