“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度

简介: 【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**

在Python的广阔世界里,数据结构是构建高效算法的基石。当谈及复杂的数据关系与交互时,图(Graph)这一高级数据结构无疑占据了举足轻重的地位。不同于线性结构如列表和树,图通过节点(Vertex)和边(Edge)的任意连接,展现了数据间错综复杂的关系。解锁图的表示与遍历技巧,不仅能让你的算法思维跃升至新高度,还能在解决实际问题时游刃有余。

图的表示
在Python中,图可以通过多种方式表示,其中最常见的是邻接矩阵(Adjacency Matrix)和邻接表(Adjacency List)。

邻接矩阵:使用一个二维数组(或列表的列表)来存储图中每对顶点之间是否存在边。如果顶点i与顶点j之间有边,则对应位置为1(或边的权重),否则为0。这种方法简单直观,但空间复杂度较高,特别是对于稀疏图。

python

邻接矩阵表示法

graph = [
[0, 1, 0, 0, 1],
[1, 0, 1, 1, 1],
[0, 1, 0, 1, 0],
[0, 1, 1, 0, 1],
[1, 1, 0, 1, 0]
]
邻接表:使用字典(或列表的列表)来存储每个顶点的所有邻接点。这种方法空间效率高,特别适用于稀疏图。

python

邻接表表示法

graph = {
'A': ['B', 'E'],
'B': ['A', 'C', 'D', 'E'],
'C': ['B', 'D'],
'D': ['B', 'C', 'E'],
'E': ['A', 'B', 'D']
}
图的遍历
图的遍历是理解图结构和解决图问题的关键步骤,主要有深度优先搜索(DFS)和广度优先搜索(BFS)两种策略。

深度优先搜索(DFS):从某一顶点出发,尽可能深地搜索图的分支,直到该顶点所在的路径到达末尾,再回溯到前一个顶点继续搜索其他路径。

python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for next_node in graph[start]:
if next_node not in visited:
dfs(graph, next_node, visited)

调用DFS

dfs(graph, 'A')
广度优先搜索(BFS):从某一顶点开始,先访问其所有邻接点,再逐层向外访问,直到访问完所有可达的顶点。

python
from collections import deque

def bfs(graph, start):
visited = set()
queue = deque([start])

while queue:  
    vertex = queue.popleft()  
    if vertex not in visited:  
        print(vertex, end=' ')  
        visited.add(vertex)  
        queue.extend(set(graph[vertex]) - visited)  

调用BFS

bfs(graph, 'A')
总结
通过对比邻接矩阵与邻接表的不同表示方式,我们可以根据图的稀疏程度选择最适合的存储方式。而深度优先搜索与广度优先搜索则各有千秋,DFS更适合于寻找解的路径或判断图中是否存在环,BFS则常用于求解最短路径问题。掌握这些高级数据结构的表示与遍历方法,无疑能让你的算法思维更加灵活多变,为解决复杂问题提供有力支持。

相关文章
|
Java 数据挖掘 数据处理
(Pandas)Python做数据处理必选框架之一!(一):介绍Pandas中的两个数据结构;刨析Series:如何访问数据;数据去重、取众数、总和、标准差、方差、平均值等;判断缺失值、获取索引...
Pandas 是一个开源的数据分析和数据处理库,它是基于 Python 编程语言的。 Pandas 提供了易于使用的数据结构和数据分析工具,特别适用于处理结构化数据,如表格型数据(类似于Excel表格)。 Pandas 是数据科学和分析领域中常用的工具之一,它使得用户能够轻松地从各种数据源中导入数据,并对数据进行高效的操作和分析。 Pandas 主要引入了两种新的数据结构:Series 和 DataFrame。
924 0
|
存储 算法 容器
set_map的实现+set/map加持秒杀高频算法题锻炼算法思维
`set`基于红黑树实现,支持有序存储、自动去重,增删查效率为O(logN)。通过仿函数可自定义排序规则,配合空间配置器灵活管理内存。不支持修改元素值,迭代器失效需注意。`multiset`允许重复元素。常用于去重、排序及查找场景。
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
940 1
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
653 10
 算法系列之数据结构-二叉树
|
机器学习/深度学习 算法 Python
matlab思维进化算法优化BP神经网络
matlab思维进化算法优化BP神经网络
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
390 0
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
577 3
 算法系列之数据结构-Huffman树
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
758 22
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
804 30

推荐镜像

更多