详细解释**图的邻接矩阵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或wij0如果顶点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邻接矩阵表示012300110110012100130110有向图的邻接矩阵特点矩阵不一定对称A[i][j]1A[i][j]1A[i][j]1表示从iii到jjj有边0 → 1 ↑ ↙ 2 ← 3邻接矩阵表示012300100100102100030010带权图的邻接矩阵对于带权图矩阵元素存储边的权重无边时用∞\infty∞或 0 表示012005∞\infty∞15032∞\infty∞30Java 实现示例publicclassAdjacencyMatrixGraph{privateint[][]matrix;// 邻接矩阵privateintnumVertices;// 顶点数privatebooleanisDirected;// 是否有向privatebooleanisWeighted;// 是否带权// 初始化publicAdjacencyMatrixGraph(intn,booleandirected,booleanweighted){this.numVerticesn;this.isDirecteddirected;this.isWeightedweighted;this.matrixnewint[n][n];// 带权图初始化对角线为0其他为无穷大if(weighted){for(inti0;in;i){for(intj0;jn;j){matrix[i][j](ij)?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;// 无向图对称}}// 获取邻居节点publicListIntegergetNeighbors(intvertex){ListIntegerneighborsnewArrayList();for(inti0;inumVertices;i){if(matrix[vertex][i]!0matrix[vertex][i]!Integer.MAX_VALUE){neighbors.add(i);}}returnneighbors;}// 打印矩阵publicvoidprintMatrix(){for(inti0;inumVertices;i){for(intj0;jnumVertices;j){System.out.printf(%4d ,matrix[i][j]Integer.MAX_VALUE?-1:matrix[i][j]);}System.out.println();}}}复杂度分析操作时间复杂度空间复杂度添加边O(1)O(1)O(1)O(n2)O(n^2)O(n2)删除边O(1)O(1)O(1)O(n2)O(n^2)O(n2)查询边O(1)O(1)O(1)O(n2)O(n^2)O(n2)获取所有邻居O(n)O(n)O(n)O(n2)O(n^2)O(n2)适用场景✅ 适合使用❌ 不适合稠密图边数接近n2n^2n2稀疏图边数远小于n2n^2n2需要频繁查询边是否存在顶点数很大内存消耗大实现简单的图算法如Floyd-Warshall需要频繁增删顶点与邻接表对比特性邻接矩阵邻接表空间O(V2)O(V^2)O(V2)O(VE)O(VE)O(VE)查边O(1)O(1)O(1)O(V)O(V)O(V)或O(degree)O(\text{degree})O(degree)遍历邻居O(V)O(V)O(V)O(degree)O(\text{degree})O(degree)适合图类型稠密图稀疏图如果你对分子算法Molecular Algorithm中的图结构表示感兴趣邻接矩阵也常用于表示分子拓扑结构比如原子间的键连关系。
图的领接矩阵表示法
详细解释**图的邻接矩阵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或wij0如果顶点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邻接矩阵表示012300110110012100130110有向图的邻接矩阵特点矩阵不一定对称A[i][j]1A[i][j]1A[i][j]1表示从iii到jjj有边0 → 1 ↑ ↙ 2 ← 3邻接矩阵表示012300100100102100030010带权图的邻接矩阵对于带权图矩阵元素存储边的权重无边时用∞\infty∞或 0 表示012005∞\infty∞15032∞\infty∞30Java 实现示例publicclassAdjacencyMatrixGraph{privateint[][]matrix;// 邻接矩阵privateintnumVertices;// 顶点数privatebooleanisDirected;// 是否有向privatebooleanisWeighted;// 是否带权// 初始化publicAdjacencyMatrixGraph(intn,booleandirected,booleanweighted){this.numVerticesn;this.isDirecteddirected;this.isWeightedweighted;this.matrixnewint[n][n];// 带权图初始化对角线为0其他为无穷大if(weighted){for(inti0;in;i){for(intj0;jn;j){matrix[i][j](ij)?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;// 无向图对称}}// 获取邻居节点publicListIntegergetNeighbors(intvertex){ListIntegerneighborsnewArrayList();for(inti0;inumVertices;i){if(matrix[vertex][i]!0matrix[vertex][i]!Integer.MAX_VALUE){neighbors.add(i);}}returnneighbors;}// 打印矩阵publicvoidprintMatrix(){for(inti0;inumVertices;i){for(intj0;jnumVertices;j){System.out.printf(%4d ,matrix[i][j]Integer.MAX_VALUE?-1:matrix[i][j]);}System.out.println();}}}复杂度分析操作时间复杂度空间复杂度添加边O(1)O(1)O(1)O(n2)O(n^2)O(n2)删除边O(1)O(1)O(1)O(n2)O(n^2)O(n2)查询边O(1)O(1)O(1)O(n2)O(n^2)O(n2)获取所有邻居O(n)O(n)O(n)O(n2)O(n^2)O(n2)适用场景✅ 适合使用❌ 不适合稠密图边数接近n2n^2n2稀疏图边数远小于n2n^2n2需要频繁查询边是否存在顶点数很大内存消耗大实现简单的图算法如Floyd-Warshall需要频繁增删顶点与邻接表对比特性邻接矩阵邻接表空间O(V2)O(V^2)O(V2)O(VE)O(VE)O(VE)查边O(1)O(1)O(1)O(V)O(V)O(V)或O(degree)O(\text{degree})O(degree)遍历邻居O(V)O(V)O(V)O(degree)O(\text{degree})O(degree)适合图类型稠密图稀疏图如果你对分子算法Molecular Algorithm中的图结构表示感兴趣邻接矩阵也常用于表示分子拓扑结构比如原子间的键连关系。
