illegalCreed

中文

English

中文

English

Appearance

三种表示法：邻接矩阵、邻接表与边集数组 ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • 邻接矩阵（Adjacency Matrix）：n×n 二维数组，a[i][j]=1（或权重）表示顶点 i 到 j 有边，无权无向图主对角线对称。查边 O(1)、遍历邻居 O(n)、空间 O(n²)——适合稠密图与需 O(1) 判边（Floyd 多源最短路）。
  • 邻接表（Adjacency List）：每个顶点挂一条链表/动态数组存它的邻居。空间 O(V+E)、查边 O(度)、遍历邻居 O(度)——适合稀疏图与 BFS/DFS/Dijkstra/Prim。
  • 边集数组（Edge List）：只存一条条边 {u, v, w}，空间 O(E)、查边 O(E)、遍历邻居需扫全部边——适合「按边遍历」的算法（Kruskal 最小生成树、Bellman-Ford）。
  • 稀疏/稠密判据：边数 m 接近 n² 为稠密、远小于 n²（如 O(n)）为稀疏。稠密选矩阵、稀疏选表是第一选型原则。
  • 三者对比一句话：矩阵赢在查边 O(1)、输在空间 O(n²)；表赢在省空间、输在查边 O(度)；边集数组最省空间但查询最慢。
  • 建图复杂度：邻接矩阵建图 O(n² + m)（要先清零）；邻接表建图 O(V + E)；边集数组建图 O(E)。
  • 遍历邻居：BFS/DFS 的核心操作是「枚举某顶点的所有邻居」——邻接表 O(度) 最快，矩阵要 O(n) 扫一整行（稀疏图下大量 0 浪费）。
  • 选型总纲：稠密选矩阵、稀疏选表、按边遍历选边集数组。详见工程实现与选型。

一、邻接矩阵：n×n 数组查边 O(1) ​

邻接矩阵用一个 n×n 的二维数组 a 表示图：a[i][j] = 1（无权）或 a[i][j] = w（带权，权值）表示顶点 i 到 j 有一条边；无边则 a[i][j] = 0（或带权图用 ∞）。

无向图              邻接矩阵 a
  0 ─── 1            0 1 2 3
  │     │         0 [0,1,0,1]
  3 ─── 2         1 [1,0,1,0]
                  2 [0,1,0,1]
                  3 [1,0,1,0]
              （无向图矩阵关于主对角线对称）

无向图的矩阵对称（a[i][j] = a[j][i]），因为边 {i,j} 双向；有向图矩阵不一定对称。

js
// 无权无向图的邻接矩阵建图
function buildMatrix(n, edges) {
  const a = Array.from({ length: n }, () => new Array(n).fill(0));
  for (const [u, v] of edges) {
    a[u][v] = 1;       // 无向图：两个方向都置 1
    a[v][u] = 1;
  }
  return a;
}
// 查边：a[u][v] === 1 ?  O(1)

优点：①查边/判边存在 O(1)（直接读 a[u][v]）；②实现最简单，一个二维数组；③适合稠密图（边多，矩阵利用率高）；④Floyd 多源最短路天然基于矩阵。

缺点：①空间 O(n²)——对稀疏图是灾难（一亿顶点要 10¹⁶ 槽，存不下）；②遍历某顶点邻居要扫一整行 O(n)，稀疏图下大量 0 是浪费；③增删边虽 O(1)，但加顶点要扩矩阵（O(n²) 拷贝）。

二、邻接表：每个顶点挂邻居链表 ​

邻接表为每个顶点维护一条链表（或动态数组），链表里存「与该顶点直接相连的邻居」。

无向图              邻接表
  0 ─── 1            0 → [1, 3]
  │     │            1 → [0, 2]
  3 ─── 2            2 → [1, 3]
                     3 → [0, 2]

实现上，最常见的是「数组 + 动态数组」：外层一个长度 n 的数组，每个元素是一个动态数组（JS 用 Array、Python 用 list、C++ 用 vector<vector<int>>），存该顶点的邻居。

js
// 无权无向图的邻接表建图（数组套数组）
function buildAdjList(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);     // 无向图：两个方向都 push
    adj[v].push(u);
  }
  return adj;
}
// 查边：(u,v) 是否有边？→ 遍历 adj[u] 找 v，O(度)
// 遍历邻居：for (const w of adj[u]) ...  O(度)

优点：①空间 O(V+E)——只存实际存在的边，稀疏图省内存（社交网一亿用户几亿边 vs 矩阵 10¹⁶）；②遍历邻居 O(度)，是 BFS/DFS 的核心操作，最高效；③加边 O(1)（push）、加顶点 O(1)（外层数组 push 空链表）。

缺点：①查边（判 (u,v) 是否有边）要扫 u 的整条邻居链表，O(度)，不如矩阵 O(1)（重边时还需计数去重）；②实现略复杂（两层结构）；③删除某条边 O(度)（要先找到位置）。

三、边集数组：只存边，按边遍历 ​

边集数组最朴素——只存一个边列表，每个元素是一条边 {u, v, w}（起点、终点、权重）。它不维护「每个顶点的邻居」，而维护「每一条边」。

无向图              边集数组 edges
  0 ─── 1            [{u:0, v:1}, {u:1, v:2},
  │     │             {u:2, v:3}, {u:0, v:3}]
  3 ─── 2
js
// 无权无向图的边集数组建图
function buildEdgeList(n, edges) {
  return edges.map(([u, v]) => ({ u, v })); // 带权则加 w
}
// 查边：遍历整个 edges 找 (u,v)，O(E)
// 遍历顶点 u 的邻居：扫全部 edges 筛 u∈{e.u,e.v}，O(E)

优点：①空间最小 O(E)，只存边本身；②按边遍历天然高效——Kruskal 最小生成树（要按权重排序所有边）、Bellman-Ford（每轮松弛所有边）都直接基于边集数组；③实现极简。

缺点：①查边、遍历某顶点邻居都要 O(E) 扫全部边，查询效率最差；②不适合 BFS/DFS/Dijkstra（它们要频繁按顶点枚举邻居）。

四、三者对比表 ​

维度邻接矩阵邻接表边集数组
空间O(n²)O(V+E)O(E)
查边 (u,v)?O(1) ✅O(度)O(E) ❌
遍历某顶点邻居O(n)O(度) ✅O(E) ❌
遍历所有边O(n²)O(V+E)O(E) ✅
建图O(n² + m)O(V+E)O(E)
加边/删边O(1) / O(1)O(1) / O(度)O(1) / O(E)
适合图类型稠密图稀疏图按边处理
典型算法FloydBFS/DFS/Dijkstra/PrimKruskal/Bellman-Ford

五、稠密选矩阵、稀疏选表 ​

这是图表示选型的第一判据。设顶点数 n、边数 m：

  • 稠密图（m ≈ n²）：邻接矩阵 O(n²) 空间没有浪费（矩阵里大部分是 1），且查边 O(1) 优势明显——选矩阵。典型如小规模完全图、运算优先关系图。
  • 稀疏图（m ≪ n²，如 m = O(n)）：邻接矩阵 O(n²) 空间里大部分是 0（浪费），而邻接表 O(V+E) ≈ O(n) 极省——选邻接表。现实中的图（社交/网页/地图）几乎都是稀疏图。

绝大多数面试与工程场景是稀疏图，所以邻接表是默认选择；只有在「稠密」或「需要 O(1) 判边」（如 Floyd）时才用矩阵。边集数组是补充——当算法本身按边处理（Kruskal、Bellman-Ford）时，直接用边集数组最方便（有时会与邻接表并用：邻接表用于遍历、边集数组用于排序边）。

交互演示 ​

下一步 ​

选定了表示法，下一步是工程落地：邻接表的 JS/Python 实现长什么样？有向图、无向图、带权图分别怎么存？输入数据怎么解析成图？见工程实现与选型。