文章目录邻接矩阵邻接矩阵法存储带权图网邻接矩阵的性质邻接矩阵邻接矩阵法 是图的存储结构它利用 “二维数组矩阵” 来保存顶点间的邻接关系。结点数为n nn的图G ( V , E ) G(V,E)G(V,E)的邻接矩阵A AA是n × n n\times nn×n的。将G GG的顶点编号为v 1 , v 2 , … , v n v_1,v_2,\dots,v_nv1,v2,…,vn则A [ i ] [ j ] { 1 , 若 ( v i , v j ) 或 v i , v j 是 E ( G ) 中的边 0 , 若 ( v i , v j ) 或 v i , v j 不是 E ( G ) 中的边 A[i][j] \begin{cases} 1, \text{若 }(v_i,v_j)\text{ 或}v_i,v_j\text{ 是 }E(G)\text{ 中的边}\\[4pt] 0, \text{若 }(v_i,v_j)\text{ 或}v_i,v_j\text{ 不是 }E(G)\text{ 中的边} \end{cases}A[i][j]{1,0,若(vi,vj)或vi,vj是E(G)中的边若(vi,vj)或vi,vj不是E(G)中的边#defineMaxVertexNum100// 顶点数目的最大值#defineINFINITY最大的int值// 宏定义常量“无穷” 可用int的上限值表示无穷typedefcharVertexType;// 顶点的数据类型typedefintEdgeType;// 带权图中边上权值的数据类型typedefstruct{VertexType Vex[MaxVertexNum];// 顶点表一维数组EdgeType Edge[MaxVertexNum][MaxVertexNum];// 邻接矩阵边表/二维数组 100*100intvexnum,arcnum;// 图的当前顶点数和边数弧数}MGraph;邻接矩阵存储特点空间复杂度O ( ∣ V ∣ 2 ) O(|V|^2)O(∣V∣2)——只和顶点数相关和实际的边数无关适合用于存储稠密图无向图的邻接矩阵是对称矩阵可以压缩存储只存储上三角区/下三角区邻接矩阵法存储带权图网邻接矩阵的性质设图G GG的邻接矩阵为A AA矩阵元素为0/1则A n A^nAn的元素A n [ i ] [ j ] A^n[i][j]An[i][j]等于由顶点i ii到顶点j jj的长度为n nn的路径的数目。路径长度指路径上边的条数。A 1 [ i ] [ j ] A^1[i][j]A1[i][j]直接边长度为1的路径数量就是邻接矩阵本身。A 2 [ i ] [ j ] A^2[i][j]A2[i][j]从i ii走2条边到达j jj的路径总数。既适用于无向图也适用于有向图。注意路径允许重复经过顶点、重复经过边。
)
