欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 汽车 > 新车 > 【Python 数据结构 14.邻接表】

【Python 数据结构 14.邻接表】

2025/3/15 19:37:04 来源:https://blog.csdn.net/m0_73983707/article/details/146157034  浏览:    关键词:【Python 数据结构 14.邻接表】

希望你的眼睛可以一直笑,想要的都得到

                                                        —— 25.3.11

一、邻接表的概念

1.邻接表的定义

        邻接表是一种表示图的数据结构。邻接表的主要概念是:对于图中的每个顶点维护一个由与其相邻的顶点组成的列表。这个列表可以用数组、链表或其他数据结构来实现。

        实际上,邻接表可以用于有向图、无向图、带权图、无权图。这里只考虑无权图的情况,带权图只需要多存储一个边权的数据就可以了


2.邻接表的顺序表结构

        可以用二维列表模拟实现

adjSize[maxn]:adjSize[i] 代表从 i 出发,能够直接到达的点的数量

adj[maxn][maxn]:adjSize[i][j] 代表从 i 出发,能够到达的第 j 个顶点

在一个 n 个顶点的图上,由于任何一个顶点最多都有 n - 1 个顶点相连,所以 maxn = n - 1 


3.邻接表的链表存储

        用链表来实现邻接表,实际上就是对于每一个顶点,它能够到达的顶点,都被存储在以它为头结点的链表上

对于上述的图,存储的是四个链表:

        ① 0 —> 3 —> 2 —> NULL

        ② 1 —> 0

        ③ 2 —> NULL

        ④ 3 —> 1          

这就是用链表表示的邻接表。注意:这里实际上每个链表的头结点是存储在一个顺序表中的,所以严格意义上来说是 顺序表 +链表 的实现。


4.邻接表的应用

        邻接表一般应用在图的遍历算法,比如:深度优先搜索、广度优先搜索。更加具体的,应用在最短路上,比如 Dijkstra、Bellman-Ford、SPFA;以及最小生成树,比如 Kruskal、Prim;还有拓扑排序、强连通分量、网络流、二分图最大匹配 等等问题。


5.邻接表的优点

        邻接表表示法的优点主要有:空间效率、遍历效率

        空间利用率高:邻接表通常比邻接矩阵更节省空间,尤其是对于稀疏图。因为邻接表仅需要存储实际存在的边,而邻接矩阵需要存储所有的边。

        遍历速度:邻接表表示法在遍历与某个顶点相邻的所有顶点时,时间复杂度与顶点的度成正比。对于稀疏图,这比邻接矩阵表示法的时间复杂度要低。


6.邻接表的缺点

        不适合存储稠密图:对于稠密图(即图中边的数量接近于n ^ 2),导致每个顶点的边列表过长,从而降低存储和访问效率

        代码复杂:相比于邻接矩阵,实现代码会更加复杂


二、Python中的邻接表

EdgeNode:边结点,表示邻接表中的一条边,每个边结点记录目标顶点和权重,类似于链表中的结点结构

        v:边指向的顶点编号(弧尾结点)

        w:边的权重值,用于带权图的场景

VertexNode:顶点结点,管理该顶点的所有出边,每个顶点维护一个边列表edges,存储从该顶点出发的所有边,形成链式结构

        v:当前顶点的唯一标识符(通常为整数索引)

Graph:图结构,创建 n 个顶点结点VertexNode对象,构成邻接表的基础结构

        n:图的顶点数量

addEdge:添加边,在顶点u的邻接边列表中追加新的EdgeNode,完成边的添加

        u:边的起始顶点编号(弧头顶点)

        v:边的目标顶点编号(弧尾顶点)

        w:边的权重值

printGraph:打印邻接表,遍历每个顶点的邻接边列表,输出其连接的顶点及权重

# 弧尾结点
class EdgeNode:def __init__(self, v, w):# 边结点的弧尾self.vertex = v# 边结点的权重self.weight = w# 弧头结点
class VertexNode:def __init__(self, v):# 弧头结点self.vertex = v# 一个边结点EdgeNode的列表self.edges = []class Graph:def __init__(self, n):# n 个结点self.n = n# 每个结点都有一个弧头节点VertexNodeself.nodes = [VertexNode(i) for i in range(n)]# 结点u 到 结点v 权重w的边def addEdge(self, u, v, w):self.nodes[u].edges.append(EdgeNode(v, w))def printGraph(self):for i in range(self.n):print("Vertex", i, end=":")for edge in self.nodes[i].edges:print(edge.vertex, "(", edge.weight, ")", end=" ")print()def Text():graph = Graph(5)graph.addEdge(0, 1, 1)graph.addEdge(0, 2, 2)graph.addEdge(1, 2, 3)graph.addEdge(1, 3, 4)graph.addEdge(2, 3, 5)graph.addEdge(2, 4, 6)graph.addEdge(3, 4, 7)graph.printGraph()Text()

代码运行结果:

结点0 到 结点1 有一条边

结点0 到 结点2 有两条边

结点1 到 结点2 有三条边

结点1 到 结点3 有四条边

结点2 到 结点3 有五条边

结点2 到 结点4 有六条边

结点3 到 结点4 有七条边

结点4 没有出边


三、邻接表和邻接矩阵的对比

        邻接矩阵是一个 n × n 的矩阵,矩阵的值为由 横坐标 i 点出发到 j 点这条路径的权值,n 是图中的结点数量

        为每个顶点维护一个邻接边列表,高效地存储图的连接关系

对比维度邻接表邻接矩阵支持来源
空间复杂度O(V+E),适合稀疏图(边数远小于顶点数平方)O(V²),适合稠密图(边数接近顶点数平方)

1

2

5

边的查找效率O(degree(V)),需遍历链表O(1),直接访问矩阵元素

1

2

4

遍历邻居效率O(degree(V)),仅遍历实际存在的邻接边O(V),需扫描整行/列(即使无邻接边)

2

4

6

添加边操作O(1)(头插法)O(1)(直接修改矩阵值)

1

2

5

删除边操作O(degree(V)),需遍历链表定位O(1)(直接修改矩阵值)

2

5

6

存储方式顶点数组 + 链表/动态数组(记录邻接顶点)二维数组(元素表示边存在性/权重)

1

5

6

适用场景社交网络、网页链接、稀疏图、动态图(顶点/边频繁变化)稠密图、带权图、需要频繁判断边存在的场景(如路径规划)

2

5

7

特殊场景支持可存储重复边和多重边只能表示单一边(无重复边)

8

10

无向图处理每条边存储两次(双向链表)矩阵对称,仅需存储一次

3

4

10

实现复杂度较高(需维护链表或动态数组)简单(固定大小二维数组)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词