图解算法通识讲义树与图
图论遍历、拓扑排序与并查集
核心心智模型：点线交织，防环染色；入度为零入队撕开依赖网，并查集瞬间连通岛屿。
核心交互式算法图解演练沙盒
图论遍历模型
图论广度优先搜索 (BFS) 队列层序扩散演练
步骤 1 / 4
当前 BFS 队列 Queue:[1]
时间: O(V + E) 线性图遍历1
2
3
4
起始点入队：将源点 1 加入队列，标记 visited[1]=true，准备层序扩散遍历。
关键操作与时空复杂度速查对照表
| 操作 / 算法阶段 | 平均时间 | 最坏时间 | 空间复杂度 | 核心底层机制 |
|---|---|---|---|---|
| 邻接表图 DFS / BFS | O(V + E) | O(V + E) | O(V) | 每个顶点访问一次，每条边检查一次。 |
| 拓扑排序判定 | O(V + E) | O(V + E) | O(V + E) | 入度为 0 节点流水线出队。 |
template.java
int[] inDegree = new int[numCourses];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) {
inDegree[p[0]]++;
adj.get(p[1]).add(p[0]);
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) q.offer(i);
int count = 0;
while (!q.isEmpty()) {
int cur = q.poll(); count++;
for (int next : adj.get(cur)) {
if (--inDegree[next] == 0) q.offer(next);
}
}
return count == numCourses;解题核心心法提炼
- 图的遍历核心在「防环」：必须通过 visited 数组或原地标记阻断回环死循环。
- 拓扑排序是解决任务前置依赖与编译顺序的核心范式。
- 并查集（Union-Find）具备近乎常数 O(α(N)) 的连通性判断与合并能力。
常见踩坑警示与避坑指南
- 图的邻接表构建时有向边与无向边方向搞反。
- 入度统计时漏算了自环或重复边。
对应 Hot 100 实战题目突围
原理已掌握！立即进入沉浸式工作台开始实战演练，强化代码肌肉记忆