Graph
图
图进阶时间 遍历 O(V+E)空间 O(V+E)
结点与边的集合。可有向、可带权。邻接表适合稀疏图，邻接矩阵适合稠密图。
动画
广度优先：从 A 出发，一层一层向外扩展。
1 / 13
- 当前
- 默认
讲解
网络、依赖、地图、社交关系。BFS / DFS / 最短路都建立在图上。
- 01邻接表：每个点存一列邻居，空间 O(V+E)。
- 02邻接矩阵：g[u][v] 表示边，查询 O(1)，空间 O(V²)。
- 03遍历用 BFS（层序）或 DFS（一路到底）。
- 04有向图注意入边出边；无向图存两次。
易错点
- 无向图漏存反向边会导致遍历不完整。
- 有环时 DFS 必须标记 visited，否则死循环。
代码
const g = {
A: [class="text-ok">"B", class="text-ok">"D"], B: [class="text-ok">"A", class="text-ok">"C", class="text-ok">"F"],
C: [class="text-ok">"B", class="text-ok">"E"], D: [class="text-ok">"A", class="text-ok">"F"],
E: [class="text-ok">"C", class="text-ok">"F"], F: [class="text-ok">"B", class="text-ok">"D", class="text-ok">"E"],
};