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

Python数据结构高级：图的表示与遍历

news 来源：原创 2025/9/16 11:33:36

Python数据结构高级：图的表示与遍历

一、图的基本概念

1.1 图的定义与分类

图（Graph）是由顶点（Vertex）集合和边（Edge）集合组成的数据结构，形式化表示为 G = (V, E)

主要分类：

无向图 vs 有向图

# 无向图示例：A-B-C
# 有向图示例：A→B→C

权重图 vs 非权重图

# 权重图示例：A-(5)-B-(3)-C
# 非权重图示例：A-B-C

1.2 典型应用场景

社交网络：用户为顶点，关注关系为边
交通网络：城市为顶点，路线为带权边
知识图谱：实体为顶点，关系为边
推荐系统：用户-商品交互关系建模

二、图的表示方法

2.1 邻接矩阵

使用二维数组表示顶点间的连接关系

class AdjMatrixGraph:def __init__(self, vertices):self.size = len(vertices)self.vertices = verticesself.matrix = [[0]*self.size for _ in range(self.size)]self.index_map = {v:i for i,v in enumerate(vertices)}def add_edge(self, u, v, weight=1):i = self.index_map[u]j = self.index_map[v]self.matrix[i][j] = weight# 若是无向图需添加反向# self.matrix[j][i] = weight

时间复杂度分析：

查询相邻节点：O(1)
遍历所有边：O(V²)
空间复杂度：O(V²)

2.2 邻接表

使用字典+链表存储连接关系（更节省空间）

from collections import defaultdictclass Graph:def __init__(self):self.adj_list = defaultdict(list)def add_edge(self, u, v, weight=None):self.adj_list[u].append((v, weight))# 若是无向图需添加反向# self.adj_list[v].append((u, weight))

时间复杂度分析：

查询相邻节点：O(1)平均
遍历所有边：O(V+E)
空间复杂度：O(V+E)

三、图的遍历算法

3.1 深度优先搜索（DFS）

def dfs(graph, start):visited = set()stack = [start]while stack:vertex = stack.pop()if vertex not in visited:print(vertex, end=' ')visited.add(vertex)# 逆序压栈保证顺序一致性for neighbor in reversed(graph.adj_list[vertex]):if neighbor[0] not in visited:stack.append(neighbor[0])

应用场景：

拓扑排序
检测环路
寻找连通分量

3.2 广度优先搜索（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, end=' ')visited.add(vertex)for neighbor in graph.adj_list[vertex]:if neighbor[0] not in visited:queue.append(neighbor[0])

应用场景：

最短路径查找（未加权图）
社交网络的好友推荐
网页爬虫的URL遍历

四、完整代码示例

class Graph:def __init__(self):self.adj_list = defaultdict(list)def add_edge(self, u, v, weight=None):self.adj_list[u].append((v, weight))def dfs(self, start):visited = set()self._dfs_recursive(start, visited)def _dfs_recursive(self, vertex, visited):if vertex not in visited:print(vertex, end=' ')visited.add(vertex)for neighbor in self.adj_list[vertex]:self._dfs_recursive(neighbor[0], visited)def bfs(self, start):visited = set()queue = deque([start])while queue:vertex = queue.popleft()if vertex not in visited:print(vertex, end=' ')visited.add(vertex)for neighbor in self.adj_list[vertex]:if neighbor[0] not in visited:queue.append(neighbor[0])# 使用示例
if __name__ == "__main__":g = Graph()g.add_edge('A', 'B')g.add_edge('A', 'C')g.add_edge('B', 'D')g.add_edge('C', 'E')g.add_edge('D', 'E')print("DFS遍历结果：")g.dfs('A')  # 输出：A B D E C print("\nBFS遍历结果：")g.bfs('A')  # 输出：A B C D E

五、每日挑战：路径存在性判断

def has_path(graph, start, end):visited = set()stack = [start]while stack:current = stack.pop()if current == end:return Trueif current not in visited:visited.add(current)for neighbor in graph.adj_list[current]:if neighbor[0] not in visited:stack.append(neighbor[0])return False# 测试用例
g = Graph()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.add_edge('C', 'D')print(has_path(g, 'A', 'D'))  # 输出：True
print(has_path(g, 'D', 'A'))  # 输出：False

算法选择建议：

最短路径问题 → BFS
拓扑排序 → DFS
存在性判断 → 两者均可

六、扩展应用

加权图的最短路径（Dijkstra算法）
最小生成树（Prim/Kruskal算法）
社交网络分析（使用NetworkX库）
图数据库应用（Neo4j的Python接口）

# Dijkstra算法示例
import heapqdef dijkstra(graph, start):distances = {vertex: float('inf') for vertex in graph}distances[start] = 0heap = [(0, start)]while heap:current_dist, current_vertex = heapq.heappop(heap)if current_dist > distances[current_vertex]:continuefor neighbor, weight in graph[current_vertex]:distance = current_dist + weightif distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(heap, (distance, neighbor))return distances

学习建议：

使用可视化工具（如Graphviz）辅助理解
在LeetCode上练习相关题目（如207.课程表、133.克隆图）
阅读NetworkX库源码学习工业级实现
尝试实现A*算法等高级图算法

掌握图的表示与遍历是理解复杂算法的基础，后续可继续学习强连通分量、最大流等高级主题。

Python数据结构高级：图的表示与遍历

Python数据结构高级：图的表示与遍历一、图的基本概念 1.1 图的定义与分类图（Graph）是由顶点（Vertex）集合和边（Edge）集合组成的数据结构，形式化表示为 G (V, E) 主要分类&…...

编程日记 2025/9/16 11:33:36

登录-10.Filter-登录校验过滤器

一.登录校验过滤器的实现思路我们要实现登录校验过滤器，就要首先明白登录校验过滤器的实现思路。登录校验过滤器是用来实现登录校验的。那么首先思考第一个问题，所有的请求都需要校验吗？ 答案是否定的，因为login请求就不需要过滤…...

编程日记 2025/9/16 11:32:27

《Keras 3 ：使用迁移学习进行关键点检测》：此文为AI自动翻译

《Keras 3 ：使用迁移学习进行关键点检测》作者：Sayak Paul，由 Muhammad Anas Raza 转换为 Keras 3 创建日期：2021/05/02 最后修改时间：2023/07/19 描述：使用数据增强和迁移学习训练关键点检测器。（i）此示例使用 Keras 3 在 Colab 中查看 GitHub 源关键点检测包…...

编程日记 2025/9/14 10:31:44

【Deepseek】AnythingLLM + Ollama

1. 下载安装 anythingllm 下载地址：https://anythingllm.com/desktop 2. 启动anything 点击 Get started 3.创建工作空间 4.选择Ollama大语言模型聊天设置当前只有一个1.5b的模型下载完成7b模型后选择后记得点击更新到工作空间！&…...

编程日记 2025/9/16 11:32:48

VMware17下Ubuntu22.04设置本地共享文件夹

VMware17下使用Ubuntu22.04设置共享文件夹在日常的开发与学习中，我们常常需要在主机（通常是Windows系统）和虚拟机（如Ubuntu 22.04）之间进行文件交换。为了简化这一过程，VMware提供了共享文件夹的功能&…...

编程日记 2025/9/16 11:32:28

【GreenHills】GHS合并库文件

1、文档目标解决Green Hills对于多个库文件合并问题 2、问题场景客户具有多个工程库文件。但是，客户想要在项目最终交付的时候，通过将多个库文件打包成一个库文件，进行交付。 3、软硬件环境 1）、软件版本：MULTI…...

编程日记 2025/9/16 11:32:49

mysql-统计表占内存大小

在 MySQL 中，统计表占用的内存大小（或者更准确地说，是表占用的磁盘空间大小）并非一个简单的任务，因为MySQL的数据存储涉及多种文件，包括数据文件、索引文件等。不过，有几种方法可以帮助你估算一…...

编程日记 2025/9/15 17:27:32

基于SpringBoot和Leaflet的邻省GDP可视化实战

目录前言一、技术实现路径 1、空间数据检索 2、数据展示检索流程二、SpringBoot后台实现 1、模型层实现 2、控制层实现三、WebGIS前端实现 1、控制面展示 2、成果展示四、总结前言在数字化浪潮席卷全球的今天，数据已成为驱动社会经济发展、指导政策…...

编程日记 2025/9/16 11:32:29

DeepSeek-R1本地部署保姆级教程

一、DeepSeek-R1本地部署配置要求 （一）轻量级模型 ▌DeepSeek-R1-1.5B 内存容量：≥8GB 显卡需求：支持CPU推理（无需独立GPU） 适用场景：本地环境验证测试/Ollama集成调试 （二&a…...

编程日记 2025/9/16 11:32:48

DeepSeek + Mermaid编辑器——常规绘图

下面这张图出自：由清华大学出品的《DeepSeek：从入门到精通》。作为纯文本生成模型，DeepSeek虽不具备多媒体内容生成接口，但其开放式架构允许通过API接口与图像合成引擎、数据可视化工具等第三方系统进行协同工作，最终…...

编程日记 2025/9/16 11:32:49

推送项目之解决冲突

文章目录为什么会发生冲突？如何解决这些冲突？1. **查看冲突文件**2. **解决二进制文件冲突**3. **解决文本文件冲突**4. **标记冲突已解决**5. **完成合并**6. **推送更改** 注意事项总结问题：我们在git pusll拉取远程仓库的代码到本地对比…...

编程日记 2025/9/16 2:17:17

蓝桥杯——lcd显示

一：复制文件从官方参考文件中复制相关文件，Src中的lcd.c，Inc中的lcd.h，fonts.h复制到自己创建的文件中二：lcd初始化在lcd.h中找到四个初始化函数，将其写到main文件中三：写lcd显示函数在…...

编程日记 2025/9/14 2:48:59

1_安装JDK和Hadoop

一、解压jdk和hadoop安装包下载通过百度网盘分享的文件：jdk-8u172-linux-x64.tar.gz 链接：https://pan.baidu.com/s/1VjhdpfyqdC7ivEBIjTn8tA 提取码：iz25 二、配置环境变量 vi /root/.bashrc添加 #set java environment export JAVA_H…...

编程日记 2025/8/16 13:05:11

说明： 用angular实现计算器效果，ui风格为暗黑效果图： step1: C:\Users\Administrator\WebstormProjects\untitled4\src\app\calnum\calnum.component.ts import { Component } from angular/core;Component({selector: app-calnum,import…...

编程日记 2025/9/14 7:11:56

python 程序

gif调整尺寸.py import sys from PIL import Image,ImageSequence import os ##print(sys.argv[0]) ##print(sys.argv[1]) def gifresize(file_name): gf Image.open(file_name) ## lifetime gf.info[duration] imglist [] imgnew [] for i in ImageSequence.…...

编程日记 2025/9/10 0:53:27

vue3响应式数据原理

Vue 3 的响应式系统与 Vue 2 有显著不同，Vue 3 使用了 Proxy 替代了 Vue 2 中的 Object.defineProperty，这使得 Vue 3 的响应式系统更加灵活和强大 Vue 3 响应式原理的核心 Proxy： Vue 3 使用 Proxy 来拦截对象的操作（如读取、赋值…...

编程日记 2025/9/15 22:33:22

【Godot4.3】自定义圆角容器

概述 Godot控件想要完全实现现代UI风格，需要进行大量的自定义组件设计。本篇就依托于笔者自己对现代UI设计中的圆角面板元素模仿来制作圆角容器组件。圆角容器圆角元素在现代的扁平UI设计中非常常见，在Godot中可以通过改进PanelContainer来或者自定…...

编程日记 2025/9/13 23:00:52

远程部署 Qt 应用程序套件错误原因

构建套件报红色警告错误： 图一： 改图二：...

编程日记 2025/8/16 11:54:48

vue3学习4-pinia+组件通信

集中式状态管理，vue2用vuex，vue3用pinia，相当于react中的redux 引入pinia pinia的具体存储都放到src/store目录下，每个store.js具体存储实现如下： 修改pinia中的数据 3种方式： 1、可以直接修改从pinia中读…...

编程日记 2025/9/12 6:01:57

GEE中的Map对象

在Google Earth Engine (GEE) 中，Map 是一个非常重要的对象，它用于显示地理数据和控制地图的交互。Map 对象提供了一系列函数，允许你操作和控制地图显示。以下是一些常用的 Map 函数及其使用方法： 1. Map.addLayer() 功能&#x…...

编程日记 2025/9/2 13:33:44

【AI学习笔记】2月10日李飞飞巴黎AI峰会演讲：探索 AI 的历史、现状与未来

【AIGC学习笔记】2月10日李飞飞巴黎AI峰会演讲：探索 AI 的历史、现状与未来 AI 的历史根基与发展历程生命起源与智能诞生：5 亿年前视觉概念的出现推动了智能的诞生。最初的感知仅仅是被动的体验，只是但随着神经系统的活跃，视觉…...

编程日记 2025/9/12 8:24:50

Vue.js组件开发：从基础到进阶

在现代前端开发中，Vue.js因其简洁、灵活和易上手的特点，成为了众多开发者首选的框架之一。组件化是Vue.js的核心思想之一，它让我们能够更高效、模块化地开发应用。在本文中，我们将从Vue.js的组件开发的基础知识开始，逐…...

编程日记 2025/9/13 19:09:36

Elasticsearch索引设计与分片策略深度优化-手记

一、索引设计的黄金法则（从踩坑到精通的必经之路） 1. 字段类型显式声明原则动态映射是新手最易踩的坑，某金融平台曾因金额字段被自动识别为text类型，导致聚合查询时触发OOM。正确做法应显式声明核心字段： PUT /fin…...

编程日记 2025/9/15 8:42:16

嵌入式学习|C语言篇进程间通信（IPC）全面解析与示例

一、进程通信基础概念 1.1 进程隔离原理现代操作系统通过虚拟内存技术为每个进程创建独立的地址空间，这种隔离机制保障了系统的安全性，但也导致进程无法直接访问彼此的内存数据。进程间通信（IPC）正是为解决这一矛盾而设计的核心…...

编程日记 2025/9/11 11:20:31

2020年蓝桥杯Java B组第二场题目+部分个人解析

#A：门牌制作 624 解一： public static void main(String[] args) {int count0;for(int i1;i<2020;i) {int ni;while(n>0) {if(n%102) {count;}n/10;}}System.out.println(count);} 解二： public static void main(String[] args) {…...

编程日记 2025/9/15 0:13:23

3. Spring Cloud LoadBalancer 入门与使用

一、什么是 LoadBalancer? LoadBalancer(负载均衡器)是一种网络设备或软件机制，用于分发传入的网络流量负载(请求)到多个后端目标服务器上，从而实现系统资源的均衡利用和提高系统的可用性和性能。 1.1 负载均衡分类服务器负载均衡是在服务端通过硬件…...

编程日记 2025/9/15 22:31:47

基于TensorFlow.js与Web Worker的智能证件照生成方案

功能简介本文基于TensorFlow.js与Web Worker实现了常用的“证件照”功能，可以对照片实现抠图并替换背景。值得一提的是，正常抠图的操作应该由后端进行，这里只是主要演示该功能实现步骤，并不建议该功能由前端全权处理。限于个人技…...

编程日记 2025/9/10 21:39:25

jupyterhub on k8s 配置用户名密码简单版

如果只是小组内使用不想共用密码也不想搞复杂认证方案那么就直接通过map(用户名,密码md5值)来制定密码 config.yaml部分内容 hub:config:JupyterHub:shutdown_on_logout: true # 用户logout 自动stop jupyter pod,家目录下所有文件会被保存到pvc 即启动后之前家目录下…...

编程日记 2025/9/13 18:12:28

Logic-RL:Unleashing LLM Reasoning with Rule-Based Reinforcement learning

1.Introduction deepseek-r1，kimi-k1.5和openai-o1效果都很好。deepseek-r1引入了一种简单而有效的基于规则的强化学习，无需依赖传统的支撑技术，如蒙特卡洛书树搜索MCTS或者过程奖励模型PRM，便能出现新兴的推理模式。deepseek-r1开源了权重，但是并未发布训练或数据集，这…...

编程日记 2025/9/11 0:42:54

算法-数据结构-图的构建（邻接矩阵表示）

数据定义 //邻接矩阵表示图 //1.无向图是对称的 //2.有权的把a,到b 对应的位置换成权的值/*** 无向图* A B* A 0 1* B 1 0*/ /*** 有向图* A B* A 0 1* B 0 0*/import java.util.ArrayList; import java.util.List;/*** 带权图* A B* A 0 1* B 0 0*/ p…...

编程日记 2025/9/15 15:40:04

使用 Grafana 监控 Spring Boot 应用

随着软件开发领域的不断发展，监控和可观测性已成为确保系统可靠性和性能的关键实践。Grafana 是一个功能强大的开源工具，能够为来自各种来源的监控数据提供丰富的可视化功能。在本篇博客中，我们将探讨如何将 Grafana 与 Spring Boot 应用程序…...

编程日记 2025/9/10 18:47:29

使用S32DS部署Tensorflow lite到S32K3

一、概述 1、本文主要介绍如何用S32DS在NXP S32K344 中部署Tensorflow； 2、示例使用了Tensorflow入门代码，主要功能是识别28 * 28 的手写图片的数字； 3、在MCU上开启DSP功能后，最终运行时间在 7ms（64神经元&#xf…...

编程日记 2025/9/14 3:47:05

AWS S3深度解析：十大核心应用场景与高可用架构设计实践

摘要：作为全球领先的对象存储服务，Amazon S3凭借其高扩展性、持久性和安全性，已成为企业云原生架构的核心组件。本文将深入探讨S3的典型技术场景，并揭秘其背后的架构设计逻辑。一、AWS S3核心技术特性解析 Amazon Simple Storag…...

编程日记 2025/9/11 19:53:55

系统学习算法：专题十二记忆化搜索

什么是记忆化搜索，我们先用一道经典例题来引入，斐波那契数题目一： 相信一开始学编程语言的时候，就一定碰到过这道题，在学循环的时候，我们就用for循环来解决，然后学到了递归，我们又…...

编程日记 2025/9/11 18:08:16

Redis基操

redis 存储在内存中 key-value存储主要存储热点数据(短时间大量的访客去访问) 启动命令 redis-server.exe redis.windows.conf 客户端链接redis服务器 redis-cli.exe redis-cli.exe -h localhost -p 6379 redis-cli.exe -h localhost -p 6379 -a 123456 退出 exit keys * 命…...

编程日记 2025/9/16 4:35:21

基于 GEE 计算并下载研究区年均叶面积指数 LAI 和光合有效辐射分量 FPAR

目录 1 完整代码 2 运行结果 1 完整代码 var table table; var collection ee.ImageCollection(MODIS/061/MOD15A2H).filterDate(2023-01-01, 2023-12-30).filterBounds(table); // LAI配色 var colorLai {min: 0,max: 100,palette: [ffffff, fde0d4, fcc4ac, faa784, f…...

编程日记 2025/9/15 13:57:00

软考——WWW与HTTP

1.万维网（world wide web） 是一个规模巨大的、可以资源互联的资料空间。由URL进行定位，通过HTTP协议传送给使用者，又由HTML来进行文件的展现。它的主要组成部分是：URL、HTTP、HTML。 （1）URL…...

编程日记 2025/9/15 0:42:49

sqli-labs-master第46关

目录报错注入直接注入数据库名数据库中的表名 users表结构： users表数据： python脚本注入直接注入获取数据库名获取表名获取表结构获取数据布尔盲注获取数据库名获取表名获取表结构获取数据报错注入直接注入数据库名…...

编程日记 2025/9/16 7:51:35

opencv交叉编译报错：undefined reference to `png_riffle_palette_neon

序偶NEON 概述 NEON（Nested Enhanced Vector Instruction Set）是 ARM 架构中的一种高级 SIMD（Single Instruction, Multiple Data，单指令多数据）扩展技术。它专为加速多媒体和信号处理任务而设计，允许在单…...

编程日记 2025/9/15 12:38:18

代码随想录算法训练day63---图论系列7《prim算法kruskal算法》

代码随想录算法训练 —day63 文章目录代码随想录算法训练前言一、53. 寻宝—prim算法打印出来最小生成树的每条边二、53. 寻宝—kruskal算法打印出来最小生成树的每条边总结前言今天是算法营的第63天，希望自己能够坚持下来！ 今天继续图论part&…...

编程日记 2025/9/10 18:53:39

算法日常刷题笔记（2）

为保持刷题的习惯计划一天刷3-5题然后一周总计汇总一下这是第二篇笔记笔记时间为2月17日到2月23日第一天找到初始输入字符串找到初始输入字符串 Ihttps://leetcode.cn/problems/find-the-original-typed-string-i/ Alice 正在她的电脑上输入一个字符串。但是她打字技…...

编程日记 2025/9/13 22:53:42

C# httpclient 和 Flurl.Http 的测试

关于C#调用接口或Post,Flurl封装了httpclient, CSDN有哥们提供了一个公网的测试网站，可以测试Post调用，我写了2个函数，测试httpclient和Flurl使用Post: async 和 await 是成对使用的，为了接受web异步返回的数据，winfor…...

编程日记 2025/9/14 1:47:35

关于ES中text类型时间字段范围查询的结构化解决方案

前言有关es中text类型的时间字段范围查询的问题，比如： {"query": {"range": {"insertTime": {"gte": "2025-02-01T00:00:00","lte": "2025-11-30T23:59:59","format&quo…...

编程日记 2025/9/15 7:32:36

四元数欧拉角

orientation 是表示物体在三维空间中的旋转姿态的数据结构。它通常使用四元数（Quaternion） 来表示旋转。四元数是一种数学工具，用于描述三维空间中的旋转，相比欧拉角（Euler Angles）和旋转矩阵&#xff0…...

编程日记 2025/9/16 8:00:33

Linux项目自动化构建工具-make/Makeﬁle (linux第六课)

目录背景介绍依赖关系的格式依赖方法的格式原理背景会不会写makeﬁle，从一个侧面说明了一个人是否具备完成大型工程的能力一个工程中的源文件不计数，其按类型、功能、模块分别放在若干个目录中，makeﬁle定义了一系列的规则来指定…...

编程日记 2025/9/14 3:06:50

Java 登录框架

Java框架中常用的几种成熟的token生成框架对比 - 白露~ - 博客园 SpringBoot整合sa-token，jwt登录及拦截器鉴权Demo_只有在集成 sa-token-jwt 插件后才可以使用 extra 扩展参数-CSDN博客推荐一款轻量级权限认证框架Sa-Token，集成JWT和Redis轻松实现认…...

编程日记 2025/9/10 15:43:25

人工智能、机器学习、深度学习和大语言模型之间的关系

人工智能（AI）、机器学习（ML）、深度学习（DL）和大语言模型（LLM）之间是逐层包含且技术递进的关系，具体如下： 1. 层级关系人工智能（AI）…...

编程日记 2025/9/13 13:26:12

项目组合管理：优化项目选择与资源分配——从战略到实战的全流程指南

在复杂的商业环境中，企业往往需要同时推进多个项目以支撑战略目标。然而，资源有限、目标冲突、优先级模糊等问题常导致项目失败或资源浪费。项目组合管理（Project Portfolio Management, PPM） 正是解决这一痛点的系统性方法。它通…...

编程日记 2025/9/16 4:00:50

zabbix排障-zabbix监控的主机出现可用性灰色或者红色问题

目录解决zabbix-agent可用性灰色的办法: 解决zabbix可用性红色的方法: 在zabbix日常的使用中我们会遇到很多的问题就比如今天我做好zabbix-server和zabbix-agent两台机器的配置然后在wen页面上发现两台主机都有可用性的问题如下图解决zabbix-agent可用性灰色的办法: …...

编程日记 2025/9/15 10:29:48

C语言（13）------------＞do-while循环

1.do-while循环的语法我们知道C语言有三大结构，顺序、选择、循环。我们可以使用while循环、for循环、do-while循环实现循环结构。之前的博客中提及到了前两者的技术实现。可以参考： C语言（11）-------------＞while循…...

编程日记 2025/9/15 5:03:51

Python数据结构高级：图的表示与遍历

一、图的基本概念

1.1 图的定义与分类

1.2 典型应用场景

二、图的表示方法

2.1 邻接矩阵

2.2 邻接表

三、图的遍历算法

3.1 深度优先搜索（DFS）

3.2 广度优先搜索（BFS）

四、完整代码示例

五、每日挑战：路径存在性判断

六、扩展应用

相关文章：