数据结构：邻接矩阵-育师

邻接矩阵

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

一、邻接矩阵的定义

邻接矩阵是图的一种基础存储方式，通过一个二维数组来表示图中顶点之间的邻接关系。对于包含n个顶点的图，邻接矩阵是一个n×n的矩阵adj，矩阵中的元素adj[i][j]用于标识顶点i和顶点j之间是否存在边，以及边的相关属性（如权重）。

邻接矩阵可同时存储无向图、有向图和加权图，仅需调整矩阵元素的取值规则。

二、邻接矩阵的取值规则

1. 无权无向图

若顶点i和顶点j之间存在无向边，则adj[i][j] = 1，adj[j][i] = 1（矩阵对称）；
若不存在边，则adj[i][j] = 0，adj[j][i] = 0；
顶点自身无环时，adj[i][i] = 0（允许自环的场景可设为1）。

2. 无权有向图

若存在从顶点i指向顶点j的有向边，则adj[i][j] = 1；
若不存在该方向的边，则adj[i][j] = 0；
矩阵非对称（adj[i][j]与adj[j][i]无必然相等关系）。

3. 加权图

若顶点i到j存在边且权重为w，则adj[i][j] = w；
若不存在边，则adj[i][j] = ∞（通常用一个极大值表示，如float('inf')）；
无向加权图的矩阵对称，有向加权图的矩阵非对称。

三、邻接矩阵的核心特性

对称性
- 无向图的邻接矩阵是对称矩阵，即adj[i][j] = adj[j][i]；
- 有向图的邻接矩阵通常非对称，仅在两顶点间存在双向边时对应位置元素相等。
空间复杂度
- 固定为O(n²)，其中n为顶点数量，与图的边数无关；
- 对于稀疏图（边数远小于n²），会造成大量空间浪费；对于稠密图（边数接近n²），空间利用率较高。
操作效率
- 查询边是否存在：时间复杂度为O(1)，可直接通过矩阵下标访问；
- 查询顶点的度：
  - 无向图中，顶点i的度为第i行（或第i列）所有元素的和；
  - 有向图中，顶点i的出度为第i行元素和，入度为第i列元素和；
- 添加/删除边：时间复杂度为O(1)，仅需修改对应矩阵元素的值；
- 遍历顶点邻接边：时间复杂度为O(n)，需遍历该行所有n个元素，效率低于邻接表。

四、邻接矩阵的实现示例

1. 无权无向图的邻接矩阵实现

classAdjMatrixUndirectedGraph:def__init__(self,num_vertices):self.num_vertices=num_vertices# 初始化n×n的零矩阵self.adj_matrix=[[0for_inrange(num_vertices)]for_inrange(num_vertices)]defadd_edge(self,u,v):"""添加无向边(u, v)"""if0<=u<self.num_verticesand0<=v<self.num_vertices:self.adj_matrix[u][v]=1self.adj_matrix[v][u]=1defremove_edge(self,u,v):"""删除无向边(u, v)"""if0<=u<self.num_verticesand0<=v<self.num_vertices:self.adj_matrix[u][v]=0self.adj_matrix[v][u]=0defhas_edge(self,u,v):"""判断是否存在边(u, v)"""if0<=u<self.num_verticesand0<=v<self.num_vertices:returnself.adj_matrix[u][v]==1returnFalsedefget_vertex_degree(self,v):"""获取顶点v的度"""if0<=v<self.num_vertices:returnsum(self.adj_matrix[v])return-1defdfs(self,start,visited=None):"""深度优先搜索（基于邻接矩阵）"""ifvisitedisNone:visited=[False]*self.num_vertices visited[start]=Trueprint(start,end=" ")foriinrange(self.num_vertices):ifself.adj_matrix[start][i]==1andnotvisited[i]:self.dfs(i,visited)

2. 加权有向图的邻接矩阵实现

classAdjMatrixWeightedDigraph:def__init__(self,num_vertices):self.num_vertices=num_vertices INF=float('inf')# 初始化n×n矩阵，默认无无边（权重为无穷大），自身到自身权重为0self.adj_matrix=[[INFfor_inrange(num_vertices)]for_inrange(num_vertices)]foriinrange(num_vertices):self.adj_matrix[i][i]=0defadd_edge(self,u,v,weight):"""添加有向边<u, v>，权重为weight"""if0<=u<self.num_verticesand0<=v<self.num_vertices:self.adj_matrix[u][v]=weightdefget_edge_weight(self,u,v):"""获取边<u, v>的权重"""if0<=u<self.num_verticesand0<=v<self.num_vertices:returnself.adj_matrix[u][v]returnfloat('inf')deffloyd_warshall(self):"""Floyd-Warshall算法求解多源最短路径"""n=self.num_vertices# 初始化距离矩阵为邻接矩阵dist=[row[:]forrowinself.adj_matrix]# 遍历中间顶点kforkinrange(n):# 遍历起点iforiinrange(n):# 遍历终点jforjinrange(n):# 通过中间顶点k优化i到j的路径ifdist[i][k]+dist[k][j]<dist[i][j]:dist[i][j]=dist[i][k]+dist[k][j]returndist

使用示例

# 无权无向图示例undir_graph=AdjMatrixUndirectedGraph(5)undir_graph.add_edge(0,1)undir_graph.add_edge(0,2)undir_graph.add_edge(1,3)print("顶点0的度:",undir_graph.get_vertex_degree(0))# 输出2print("是否存在边(0,1):",undir_graph.has_edge(0,1))# 输出Trueprint("DFS遍历结果:")undir_graph.dfs(0)# 输出0 1 3 2# 加权有向图示例weighted_digraph=AdjMatrixWeightedDigraph(4)weighted_digraph.add_edge(0,1,2)weighted_digraph.add_edge(0,2,4)weighted_digraph.add_edge(1,2,1)weighted_digraph.add_edge(1,3,7)weighted_digraph.add_edge(2,3,3)shortest_dist=weighted_digraph.floyd_warshall()print("\n多源最短路径矩阵:")forrowinshortest_dist:print(row)

五、邻接矩阵与邻接表的对比

特性	邻接矩阵	邻接表
空间复杂度	O(n²)，与边数无关	O(
边存在性查询	O(1)，效率高	O(deg(v))，需遍历邻接表
邻接边遍历	O(n)，需遍历整行	O(deg(v))，仅遍历邻接顶点
边添加/删除	O(1)，直接修改元素	链表/数组操作，效率视结构而定
适用场景	稠密图、顶点数少的图	稀疏图、顶点数多的图