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

server/2024/9/22 15:42:36/

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

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

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

老鸟:邻接矩阵在某些情况下确实会有性能瓶颈。今天我可以给你介绍几个图论中的高级数据结构,比如邻接表、优先队列、和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/server/117530.html

相关文章

websocket消息推送修改

WebSocket支持同时给app端和pc端发送消息 (1) WebSocket操作类 通过修改该类WebSocket可以进行同一用户多端的消息推送 Component Slf4j ServerEndpoint("/websocket/{userId}") public class WebSocket {//省略部分代码//1.增加app端标识private String APP_SESSIO…

说说synchronized的锁升级过程

在 JDK 1.6之前&#xff0c;synchronized 是一个重量级、效率比较低下的锁&#xff0c;但是在JDK 1.6后&#xff0c;JVM 为了提高锁的获取与释放效&#xff0c;,对 synchronized 进行了优化&#xff0c;引入了偏向锁和轻量级锁&#xff0c;至此&#xff0c;锁的状态有四种&…

JQuery:后台接收Json串与对象

一、接收对象 @RequestParam可以处理get 方式中queryString的值,也可以处理post方式中 body data的值。@RequestParam用来处理Content-Type: 为 application/x-www-form-urlencoded编码的内容,提交方式GET、POST。 <script src="http://libs.baidu.com/jquery/1.9.…

vue-router + el-menu

1. el-menu的router属性 在el-menu中有一属性&#xff1a;router&#xff0c;默认是false 1.1 使用默认配置&#xff0c;即false 这时候需要自己在点击子菜单的时候进行导航&#xff0c;在el-menu添加方法&#xff0c;里边有三个参数 index: 选中菜单项的 index,indexPath…

四、(JS)JS中常见的加载事件

一、文档加载监听 &#xff08;1&#xff09;抛出疑惑&#xff0c;什么是文档加载监听&#xff1f;为什么要有这个东西&#xff1f; 老样子&#xff0c;我们先讲一个场景&#xff0c;带着大家熟悉为什么会有文档加载监听&#xff0c;是来解决什么问题来着的。 我们先看下这段…

使用QT编写有图形界面的TCP局域网聊天室(app)

服务器&#xff1a; 实现方法&#xff1a; 1.使用QTcpServer类实例化一个对象&#xff0c;就得到了一个服务器端 2.调用该类对象的成员函数 listen 将服务器启动监听&#xff0c;该函数会进行绑定ip和端口号 ip地址可以指定也可以由系统自动绑定&#xff0c;端口号也可以自…

Vue 中常用的基础指令

一. 什么是 Vue 指令 指令的定义和作用 指令是通过 Vue 实例的directives选项进行定义的。在指令的定义中&#xff0c;需要提供一个bind函数&#xff0c;它在指令第一次绑定到元素时被调用&#xff0c;可以执行一些初始化的操作。还可以提供update函数&#xff0c;它在指令所…

PHP函数如何传递数组参数

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