邻接矩阵计算器

邻接矩阵计算器

邻接矩阵计算器是一个图论工具，可在三种规范图表示形式——邻接矩阵、边列表和邻接列表——之间进行转换，并提供丰富的结构分析结果：度序列、图密度、连通分量和矩阵幂。它能自动检测您的输入描述的是有向图还是无向图，并在每个结果旁边渲染实时 SVG 可视化图形。

什么是邻接矩阵？

给定一个具有 n 个顶点的图 G = (V, E)，其邻接矩阵是一个 n × n 的方阵 A，如果从顶点 i 到顶点 j 有一条边，则条目 A[i][j] 为 1，否则为 0。

对于无向图，邻接矩阵总是对称的：每条边 {u, v} 同时贡献 A[u][v] = 1 和 A[v][u] = 1。对于有向图（digraph），矩阵可能是不对称的，反映了每个弧的方向。

三种表示形式 — 选择适合您问题的形式

计算的关键指标

度序列

对于无向图，顶点的度是与之相连的边数（自环计两次）。对于有向图，每个顶点都有一个入度（进入的弧）和一个出度（发出的弧）。排序后的度列表是一个经典的图不变量，用于同构测试和 Erdős–Gallai 可实现性定理。

图密度

密度衡量图相对于 n 个顶点上可能的最大边数有多“满”。

密度为 0 表示没有边，1 表示图是完全图，低于 0.1 的值通常表示稀疏图，此时邻接列表比矩阵更节省空间。

连通分量

连通分量是顶点的极大子集，使得每一对顶点都由一条路径连接。对于有向图，此计算器报告弱连通分量（忽略箭头方向）——这与将每个弧视为无向边所得到的子集相同。

矩阵幂 (A², A³ ... )

代数图论的一个基本定理指出，A^k 的 (i, j) 条目等于从顶点 i 到顶点 j 长度恰好为 k 的通路数量。因此：

• A²[i][i] 等于顶点 i 的度（无向图），因为从 i 到自身的 2 步通路是“去邻居再回来”。
• A³ 的迹除以 6 等于无向图中的三角形数量。
• Aⁿ⁻¹ 是否有零条目可以告诉你图是否连通。

支持的输入格式

1. 边列表

每行一个边或用逗号分隔。这些分隔符均有效：A-B, A B, A,B, A->B, A--B。如果您想强制进行有向解释，请使用 ->。

2. 邻接列表

每行一个顶点，格式为 顶点: 邻居1, 邻居2, ...。顺序无关紧要；缺失的顶点会自动从邻居列表中添加。

3. 邻接矩阵

每行一个行向量，使用空格或逗号分隔 0/1 值。矩阵必须是方阵。可以在“矩阵标签”字段中提供自定义标签（否则使用 A, B, C…）。

如何使用此计算器

1. 使用选项卡选择输入格式：边列表、邻接列表或邻接矩阵。
2. 在文本区域粘贴或输入您的图。对于矩阵输入，可在矩阵标签字段中添加可选标签。
3. 选择图类型 — 保持为“自动检测”，计算器将根据箭头 (->) 或矩阵对称性推断有向性。如果您想覆盖，请强制设为“有向”或“无向”。
4. 点击“转换并分析图”。结果页面会显示邻接矩阵、交互式 SVG 渲染、另外两种文本表示形式、度统计信息、连通分量，以及当图足够小时显示通路计数矩阵 A² 和 A³。
5. 悬停在矩阵行或图节点上，对应的行/列和关联边将亮起 — 瞬间直观证明每种格式编码的都是相同的信息。

应用实例

考虑一个顶点集为 {A, B, C, D}，边为 AB, BC, CA, CD 的无向图。邻接矩阵为：

计算器得出的关键事实：

• 对称？ 是 — 确认是无向图。
• 度序列： (3, 2, 2, 1) — 顶点 C 是枢纽。
• 密度： 2·4 / (4·3) = 0.667 — 适度稠密的图。
• 连通？ 是，单个分量。
• 三角形： 恰好一个 (A–B–C)，通过 tr(A³) = 6 确认。

常见应用

• 社交网络分析 — 好友 / 关注者图，中心性分析。
• 网页与引用图 — PageRank 和 HITS 直接基于 A 和 A^T 工作。
• 路由与网络 — 最短路径、最小割、最大流。
• 化学 — 以原子为顶点、键为边的分子图。
• 调度与依赖解析 — 构建系统中的有向无环图 (DAG)。
• 马尔可夫链 — 从图派生的行随机矩阵编码转移概率。

常见问题解答

什么是邻接矩阵？

邻接矩阵是一个用于表示有限图的 n × n 方阵。如果从顶点 i 到顶点 j 有一条边，则每个单元格 A[i][j] 为 1，否则为 0。对于无向图，矩阵是对称的，因此 A[i][j] = A[j][i]。矩阵使得在常数时间内检查两个顶点是否相连变得容易，且矩阵幂编码了顶点之间的通路数量。

如何从邻接矩阵判断图是否有向？

如果邻接矩阵是对称的，即对于每一对索引，A[i][j] 都等于 A[j][i]，则该图是无向的。如果至少有一对 A[i][j] 与 A[j][i] 不同，则该图是有向的。当您选择“自动检测”选项时，此计算器会自动执行对称性检查。

邻接矩阵的 k 次幂代表什么？

矩阵 A^k 的条目 (i, j) 计算从顶点 i 到顶点 j 的长度恰好为 k 的通路数量。例如，A²[i][j] 是 2 步路径的数量，在无向图中等于 i 和 j 的共同邻居数量。此属性用于三角形计数、可达性和 PageRank 式计算的算法中。

什么是图密度？

图密度是现有边数与最大可能边数的比率。对于具有 n 个顶点的无向简单图，密度 = 2m / (n(n-1))。对于有向图，密度 = m / (n(n-1))。密度接近 0 表示稀疏图；密度为 1 表示完全图。

邻接矩阵与邻接列表有什么不同？

邻接矩阵使用 n² 位存储每一对顶点的连通性，使邻居查找复杂度为 O(1)，但内存使用量为 O(n²)。邻接列表仅存储每个顶点的实际邻居，内存占用为 O(n + m)，对于稀疏图来说要小得多，但邻居查找需要线性扫描。矩阵更适合稠密图和矩阵代数运算；列表更适合稀疏图和 BFS/DFS 等遍历算法。

该工具能处理带权图吗？

目前的计算器专注于具有 0/1 条目的无权邻接矩阵。如果您粘贴具有非零数值权重的矩阵，每个非零单元格在结构分析中都会被视为 1。对于最短路径等带权图计算，请考虑使用专门的带权图工具。

延伸阅读

• 邻接矩阵 — 维基百科
• 度序列 — 维基百科
• 图密度 — 维基百科
• 连通分量 — 维基百科