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

news/2024/9/17 16:33:12/ 标签: 图论, 数据结构, python

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

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

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

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

渐进式介绍概念

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

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

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

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

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

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

代码示例与分析

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

python">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)。

python">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算法是一个很好的选择。它使用优先队列来优化路径搜索过程。

python">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上的图论问题

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

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


http://www.ppmy.cn/news/1524247.html

相关文章

LTE PSS搜索阶段频偏估计MATLAB实现

上期讲到PSS阶段频偏估计,包括整数倍频偏估计和小数倍频偏估计,但是未用MATLAB给大家实现,本期用MATLAB实现: function [freq_offet,N_ID_2,frameHead] = PSS_det(rxSig_init,params) % % % % coding time 2024.09.11 pssThr = 25; N = 128; root_set = [25 29 34]; …

服务器数据恢复—OneFS文件系统下数据被删除的数据恢复案例

服务器数据恢复环境&故障&#xff1a; EMC NAS&#xff08;Isilon S200&#xff09;&#xff0c;共3个节点&#xff0c;每个节点配置12块STAT硬盘。数据分两部分&#xff1a;一部分数据为vmware虚拟机&#xff08;WEB服务器&#xff09;&#xff0c;通过NFS协议共享到ESX主…

Origin画图——误差棒的制作

1.示例数据如下&#xff0c;x轴数据可以是自己的溶液浓度&#xff0c;不同模型等&#xff0c;y轴数据由自己的具体数据而定。 2.选中三列数据&#xff0c;选择统计&#xff0c;描述统计&#xff0c;行统计&#xff0c;选择输出量&#xff0c;标准差与均值。 3.输出数据如下。…

什么是嵌入式?行业前景如何?

目录 什么是嵌入式&#xff1f; 主要特点 常见应用场景 1. 工业自动化 2. 交通运输 3. 智能家居 4. 消费电子 5. 医疗设备 6. 航空航天 7. 物联网&#xff08;IoT&#xff09; 8. 能源管理 行业前景如何&#xff1f; 市场需求强劲 物联网&#xff08;IoT&#xff09;的爆发 汽车…

数据集火焰检测 >> DataBall

数据集 火焰检测 目标检测 深度学习 人工智能 ---------------------------------------------------------- 火焰检测数据集&#xff1a;2000 样本

每天一道面试题(4):Spring Boot 的“约定优于配置”理解

Spring Boot 的“约定优于配置”理解 普通人的回答 在 Spring Boot 中&#xff0c;"约定优于配置"的理念可以减少大量的配置工作&#xff0c;让开发者专注于业务代码的编写。这意味着 Spring Boot 默认提供了许多开箱即用的配置和功能&#xff0c;使得我们不需要手…

为虚拟机配置固定的IP地址(CentOS9)

配置虚拟网卡 首先关闭虚拟机 打开虚拟网络编辑器 选择更改配置 选择VMnet8&#xff0c;选择子网的IP和掩码 &#xff08;这里的子网掩码为255.255.255.0&#xff0c;表示前24位为网络号&#xff0c;后8位为主机号&#xff09;然后点击DHCP设置 设置开始IP地址和结束IP地址&…

论文120:Giga-SSL: Self-supervised learning for gigapixel images (2023, CVPR, 开源)

文章目录 1 要点2 方法2.1 算法设计2.2 设计选择 1 要点 题目&#xff1a;用于千兆像素图像的自监督学习 (Giga-SSL: Self-Supervised Learning for Gigapixel Images) 代码&#xff1a;https://github.com/trislaz/gigassl 研究目的&#xff1a; 现有的WSI分类方法依赖于有…

win10任务栏透明如何调整?——详解Windows任务栏设置与优化技巧

在这个数字化时代&#xff0c;电脑已经成为我们日常办公和生活中的。关于win10任务栏透明的设置方法&#xff0c;身边很多同事都在咨询。 本文就来简单介绍下关于电脑任务栏个性化设置的方法&#xff0c;毕竟任务栏影响着用户体验。这时&#xff0c;一款优秀的任务栏优化工具就…

DBA实战手记,技术书的黑神话

作者&#xff1a;IT邦德 中国DBA联盟(ACDU)成员&#xff0c;10余年DBA工作经验&#xff0c; Oracle、PostgreSQL ACE CSDN博客专家及B站知名UP主&#xff0c;全网粉丝10万 擅长主流Oracle、MySQL、PG、 高斯及Greenplum备份恢复&#xff0c; 安装迁移&#xff0c;性能优化、故障…

线性方程组求解——预处理Preconditioning介绍

为什么需要预处理&#xff1f; 工程中出现的大规模线性方程组往往是病态的, 对数值求解带来很大的困难: ▶ 使得迭代法(比如Krylov 子空间迭代法) 收敛变得非常缓慢 ▶ 对数值解的精度产生很大的影响(在有限精度计算情形下) 对于第一个问题, 当前的有效处理方法是预处理, 预处…

day43(9/4)——k8s

一、前期准备 1、配置主机映射 [rootk8s-master ~]# vim /etc/hosts 192.168.8.168 k8s-master 192.168.8.176 k8s-node1 192.168.8.177 k8s-node2 [rootk8s-master ~]# ping k8s-master 2、配置yum源 [rootk8s-master yum.repos.d]# vim kubernetes.repo [kubernetes…

高职人工智能训练师边缘计算实训室解决方案

一、引言 随着物联网&#xff08;IoT&#xff09;、大数据、人工智能&#xff08;AI&#xff09;等技术的飞速发展&#xff0c;计算需求日益复杂和多样化。传统的云计算模式虽在一定程度上满足了这些需求&#xff0c;但在处理海量数据、保障实时性与安全性、提升计算效率等方面…

深圳建站公司-如何做网站

深圳建站公司&#xff1a;如何制作一个成功的网站 在信息化快速发展的今天&#xff0c;企业和个人越来越重视网络形象&#xff0c;网站成为了展示品牌、推广产品和服务的重要平台。深圳作为科技创新和经济发展的前沿城市&#xff0c;涌现出许多专业的建站公司&#xff0c;能够为…

CATH标识符解读

在CATH数据库中&#xff0c;标识符如1a0rB00、1a0rP01、1a0rP02代表的是蛋白质结构的具体信息&#xff0c;主要涉及PDB编号、链ID以及结构域。让我们具体解释这些标识符的含义。 CATH标识符的组成 CATH标识符通常由以下几个部分组成&#xff1a; PDB ID&#xff1a;代表蛋白…

基于SpringBoot的家具销售电商平台

你好呀&#xff0c;我是计算机学姐码农小野&#xff01;如果有相关需求&#xff0c;可以私信联系我。 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBootMyBatis 工具&#xff1a;IDEA/Eclipse、Navicat、Maven 系统展示 首页 管理员功能界面…

MongoDB日志级别

日志 查看当前的日志级别 根据你提供的 MongoDB 命令结果&#xff0c;命令 db.adminCommand({ getParameter: "logComponentVerbosity" }) 返回了 "ok" : 0&#xff0c;这意味着命令执行失败&#xff0c;没有成功获取到日志级别的配置信息。错误信息 &quo…

PHP函数如何传递数组参数

php 函数可以使用数组参数传递大量数据。语法&#xff1a;参数类型前加上方括号 ([])。例如&#xff1a;myfunction(array $arr)。实战案例&#xff1a;计算数组元素平均值。注意&#xff1a;数组参数默认为引用传递&#xff0c;类型提示可提高代码可读性&#xff0c;数组解构可…

vue面试题2*

vue.js的两个核心是什么&#xff1f; 数据驱动、组件系统 v-on可以监听多个方法吗&#xff1f; 可以。 <input type"text" :value"name" v-on{ input:"onInput", focus:"onFocus",blur:"onBlur"} /> v-on 常用修…

java设计模式(行为型模式:状态模式、观察者模式、中介者模式、迭代器模式、访问者模式、备忘录模式、解释器模式)

6&#xff0c;行为型模式 6.5 状态模式 6.5.1 概述 【例】通过按钮来控制一个电梯的状态&#xff0c;一个电梯有开门状态&#xff0c;关门状态&#xff0c;停止状态&#xff0c;运行状态。每一种状态改变&#xff0c;都有可能要根据其他状态来更新处理。例如&#xff0c;如果…