图的领接矩阵表示法

详细解释**图的邻接矩阵（Adjacency Matrix）**这一核心数据结构。

邻接矩阵定义

邻接矩阵是表示图（Graph）的一种经典方式，使用一个二维数组来存储图中顶点之间的连接关系。

对于一个具有nnn个顶点的图，邻接矩阵是一个n×nn \times nn×n的方阵AAA，其中：

A[i][j]={1 或 wij如果顶点 i 和 j 之间有边0如果顶点 i 和 j 之间没有边A[i][j] = \begin{cases} 1 \text{ 或 } w_{ij} & \text{如果顶点 } i \text{ 和 } j \text{ 之间有边} \\ 0 & \text{如果顶点 } i \text{ 和 } j \text{ 之间没有边} \end{cases}A[i][j]={1或wij​0​如果顶点i和j之间有边如果顶点i和j之间没有边​

无向图的邻接矩阵

特点：矩阵关于主对角线对称（A[i][j]=A[j][i]A[i][j] = A[j][i]A[i][j]=A[j][i]）

0 —— 1 | | 2 —— 3

邻接矩阵表示：

有向图的邻接矩阵

特点：矩阵不一定对称，A[i][j]=1A[i][j]=1A[i][j]=1表示从iii到jjj有边

0 → 1 ↑ ↙ 2 ← 3

邻接矩阵表示：

带权图的邻接矩阵

对于带权图，矩阵元素存储边的权重，无边时用∞\infty∞或 0 表示：

Java 实现示例

publicclassAdjacencyMatrixGraph{privateint[][]matrix;// 邻接矩阵privateintnumVertices;// 顶点数privatebooleanisDirected;// 是否有向privatebooleanisWeighted;// 是否带权// 初始化publicAdjacencyMatrixGraph(intn,booleandirected,booleanweighted){this.numVertices=n;this.isDirected=directed;this.isWeighted=weighted;this.matrix=newint[n][n];// 带权图初始化：对角线为0，其他为无穷大if(weighted){for(inti=0;i<n;i++){for(intj=0;j<n;j++){matrix[i][j]=(i==j)?0:Integer.MAX_VALUE;}}}}// 添加边publicvoidaddEdge(intfrom,intto){addEdge(from,to,1);// 无权图默认权重为1}publicvoidaddEdge(intfrom,intto,intweight){matrix[from][to]=weight;if(!isDirected){matrix[to][from]=weight;// 无向图对称}}// 获取邻居节点publicList<Integer>getNeighbors(intvertex){List<Integer>neighbors=newArrayList<>();for(inti=0;i<numVertices;i++){if(matrix[vertex][i]!=0&&matrix[vertex][i]!=Integer.MAX_VALUE){neighbors.add(i);}}returnneighbors;}// 打印矩阵publicvoidprintMatrix(){for(inti=0;i<numVertices;i++){for(intj=0;j<numVertices;j++){System.out.printf("%4d ",matrix[i][j]==Integer.MAX_VALUE?-1:matrix[i][j]);}System.out.println();}}}

复杂度分析

适用场景

与邻接表对比

如果你对分子算法（Molecular Algorithm）中的图结构表示感兴趣，邻接矩阵也常用于表示分子拓扑结构，比如原子间的键连关系。