📚 Graph Algorithms for IB & CIE Computer Science | IB CIE 计算机：图算法考点精讲
Graph algorithms are a cornerstone of the IB and CIE Computer Science syllabus, appearing in both theory papers and practical problem-solving tasks. From modelling networks and social connections to optimising routes and dependency resolution, understanding graphs and their associated algorithms is essential. This revision guide walks you through the key concepts, representations, traversal methods, shortest path and minimum spanning tree algorithms, topological sorting, and complexity analysis, with paired English-Chinese explanations to reinforce understanding for exams.
图算法是 IB 和 CIE 计算机科学课程的重要基石，无论是理论试卷还是实际的问题解决任务中都会出现。从网络和社会关系建模到路径优化和依赖解析，理解图及其相关算法至关重要。本复习指南将带你梳理关键概念、表示方法、遍历方式、最短路径与最小生成树算法、拓扑排序以及复杂度分析，并通过中英对照的讲解巩固考点理解，助力考试准备。
1. Graph Basics | 图的基本概念
A graph G = (V, E) consists of a set of vertices (nodes) V and a set of edges E connecting pairs of vertices. Edges can be directed (arcs) or undirected, and may carry weights. Graphs can be cyclic or acyclic, connected or disconnected. Important terms include degree (number of edges incident to a vertex), path (sequence of vertices connected by edges), and adjacency (neighbour relationship).
图 G = (V, E) 由顶点（节点）集合 V 和连接顶点对的边集合 E 组成。边可以是有向的（弧）或无向的，也可以带有权重。图可以是循环的或无环的、连通的或不连通的。重要术语包括度（与顶点关联的边数）、路径（由边连接的顶点序列）和邻接（相邻关系）。
In IB/CIE exams, you must distinguish between simple graphs (no loops, no multiple edges) and multigraphs. A tree is a connected, acyclic graph; a forest is a set of disjoint trees. Bipartite graphs can split vertices into two sets with edges only between sets.
在 IB/CIE 考试中，需要区分简单图（无自环、无重边）和多重图。树是连通且无环的图；森林是一组不相交的树。二分图可以将顶点分成两个集合，且边只连接不同集合的顶点。
2. Graph Representation | 图的表示方法
Two primary representations are used in computing: adjacency matrix and adjacency list. An adjacency matrix is a 2D array of size |V|×|V| where entry (i, j) stores 1 (or the edge weight) if an edge exists from vertex i to j, and 0 otherwise. Memory complexity is O(|V|²), efficient for dense graphs but wasteful for sparse graphs.
在计算中主要使用两种表示方法：邻接矩阵和邻接表。邻接矩阵是一个大小为 |V|×|V| 的二维数组，如果顶点 i 到 j 存在边，则条目 (i, j) 存储 1（或边权重），否则为 0。内存复杂度为 O(|V|²)，适合稠密图，但对稀疏图较为浪费。
An adjacency list stores for each vertex a list of its adjacent vertices (or edges with weights). It uses O(|V|+|E|) memory, ideal for sparse graphs. Traversal and edge insertion/deletion operations differ in efficiency depending on the chosen representation. Exam questions often ask you to draw both representations from a given diagram.
邻接表为每个顶点存储其相邻顶点的列表（或带权重的边）。它使用 O(|V|+|E|) 的内存，非常适合稀疏图。遍历和边的插入/删除操作在不同表示下效率不同。考题常要求根据给定示意图画出两种表示。
3. Breadth-First Search (BFS) | 广度优先搜索
BFS explores a graph level by level, starting from a source vertex. It uses a queue to manage vertices to be explored. BFS visits all vertices at distance k before moving to k+1. This algorithm is used to find the shortest path in unweighted graphs and to test connectivity.
BFS 从源顶点开始，按层级探索图。它使用队列来管理待探索的顶点。BFS 在移动到距离 k+1 之前先访问所有距离为 k 的顶点。该算法可用于在无权图中寻找最短路径以及测试连通性。
The time complexity of BFS is O(|V|+|E|) when using an adjacency list, as each vertex is enqueued and dequeued once, and each edge is examined once. Space complexity is O(|V|) due to the queue and visited array.
使用邻接表时，BFS 的时间复杂度为 O(|V|+|E|)，因为每个顶点入队出队一次，每条边检查一次。空间复杂度为 O(|V|)，由于需要队列和已访问数组。
- Enqueue source and mark visited.
- 将源顶点入队并标记已访问。
- While queue not empty: dequeue vertex u, for each unvisited neighbour v of u, mark visited and enqueue v.
- 当队列非空时：顶点 u 出队，对于 u 的每个未访问邻居 v，标记已访问并入队 v。
4. Depth-First Search (DFS) | 深度优先搜索
DFS explores as far as possible along each branch before backtracking. It can be implemented using recursion (implicit stack) or an explicit stack data structure. DFS is useful for topological sorting, detecting cycles, and connected component identification.
DFS 在回溯之前沿着每个分支尽可能深地探索。它可以使用递归（隐式栈）或显式栈数据结构来实现。DFS 对于拓扑排序、检测环以及识别连通分量非常有用。
Like BFS, DFS has time complexity O(|V|+|E|) with an adjacency list. Recursive DFS may cause stack overflow on deep graphs. IB/CIE often ask to trace DFS order given a graph and starting node, noting that order can vary based on neighbour visitation sequence.
与 BFS 类似，DFS 在邻接表下时间复杂度为 O(|V|+|E|)。递归 DFS 在深度很大的图上可能导致栈溢出。IB/CIE 常要求根据给定图和起始节点追踪 DFS 的访问顺序，注意顺序可能因邻居访问次序而不同。
5. Shortest Path: Dijkstra’s Algorithm | 最短路径：Dijkstra 算法
Dijkstra’s algorithm finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edge weights. It maintains a priority queue of vertices keyed by their current shortest distance estimate. At each step, it extracts the vertex with the minimum distance, relaxes its outgoing edges, and updates distances.
Dijkstra 算法用于在边权非负的加权图中寻找单源到所有其他顶点的最短路径。它维护一个以当前最短距离估计值为键的顶点优先队列。每一步提取最小距离的顶点，松弛其出边并更新距离。
Time complexity depends on implementation: O(|V|²) using simple array, O((|V|+|E|) log |V|) with binary heap. With Fibonacci heap it can be O(|E| + |V| log |V|). Dijkstra does not work with negative weights; Bellman-Ford should be used in that case.
时间复杂度取决于实现：使用简单数组时为 O(|V|²)，使用二叉堆时为 O((|V|+|E|) log |V|)。采用斐波那契堆可达 O(|E| + |V| log |V|)。Dijkstra 算法不能处理负权边；遇到负权应使用 Bellman-Ford 算法。
Exam tips: you may be asked to perform a dry run on a small graph, updating a distance table. Always initialise source distance = 0, others = ∞. Use a visited set to avoid reprocessing.
考试提示：可能要求在小型图上进行手算演练，更新距离表。始终初始化源距离为 0，其余为 ∞。使用已访问集合避免重复处理。
6. Minimum Spanning Tree: Prim’s Algorithm | 最小生成树：Prim 算法
A minimum spanning tree (MST) of a connected, undirected, weighted graph is a subset of edges that connects all vertices with minimum total weight and no cycles. Prim’s algorithm builds the MST by starting from an arbitrary vertex and greedily adding the cheapest edge that connects a tree vertex to a non-tree vertex.
连通无向加权图的最小生成树（MST）是连接所有顶点、总权重最小且无环的边子集。Prim 算法构建 MST 时，从任意顶点开始，贪心地添加连接树内顶点与树外顶点的最便宜边。
Using a priority queue, Prim’s algorithm runs in O(|E| log |V|) or O(|V|²) for dense implementations. It resembles Dijkstra but without accumulating path distance; instead, key values represent minimum edge weight to connect to the growing tree.
使用优先队列，Prim 算法在稠密图实现的运行时间为 O(|E| log |V|) 或 O(|V|²)。它类似 Dijkstra，但不累积路径距离；键值代表连接到正在生长的树的最小边权重。
- Initialise all keys to ∞, parent array to nil. Set key of start vertex to 0.
- 将所有顶点的键值初始化为 ∞，父数组为 nil。将起始顶点键值设为 0。
- Repeat: extract min-key vertex u not in MST, mark u as in MST, for each neighbour v not in MST: if edge weight(u,v) < key[v], update key[v] and set parent[v] = u.
- 重复：提取不在 MST 中的最小键值顶点 u，将 u 标记为在 MST 中，对于每个不在 MST 中的邻居 v：如果边权(u,v) < key[v]，则更新 key[v] 并设置 parent[v] = u。
7. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树：Kruskal 算法
Kruskal’s algorithm builds the MST by sorting all edges by weight and adding them one by one, discarding any edge that would create a cycle. A disjoint-set (union-find) data structure efficiently checks for cycles.
Kruskal 算法通过按权重排序所有边并逐一添加来构建 MST，丢弃任何形成环的边。应用并查集（disjoint-set）数据结构高效检测环。
Time complexity is O(|E| log |E|) due to sorting, which dominates. Union-Find operations are nearly O(1) with path compression and union by rank. Kruskal is often preferred for sparse graphs, while Prim is simpler for dense graphs or adjacency matrix representation.
由于排序占主导，时间复杂度为 O(|E| log |E|)。采用路径压缩和按秩合并后，并查集操作几乎为 O(1)。Kruskal 算法通常适用于稀疏图，而 Prim 在稠密图或邻接矩阵表示下更简单。
Exam questions may provide a list of edges; you must sort, apply union-find, and list edges in the order they are added to the MST. Watch out for multiple edges with the same weight.
考题可能提供边列表；你需要排序、应用并查集，并按添加到 MST 的顺序列出边。注意相同权重的多条边。
8. Topological Sorting | 拓扑排序
Topological sorting orders vertices of a directed acyclic graph (DAG) such that for every directed edge u→v, u comes before v in the ordering. It is used in task scheduling, prerequisite resolution, and build systems.
拓扑排序将有向无环图（DAG）的顶点排序，使得对于每条有向边 u→v，u 在排序中位于 v 之前。它用于任务调度、先决条件解析和构建系统。
Two main methods exist: Kahn’s algorithm (BFS-based using in-degree) and DFS-based (post-order finish times). Kahn’s algorithm repeatedly removes vertices with in-degree 0. The DFS method records vertices in reverse finish time order.
主要有两种方法：Kahn 算法（基于 BFS 利用入度）和基于 DFS 的方法（后序完成时间）。Kahn 算法反复移除入度为 0 的顶点。DFS 方法按完成时间倒序记录顶点。
| Algorithm | Method | Complexity |
| Kahn’s | In-degree queue | O(|V|+|E|) |
| DFS-based | Recursive stack | O(|V|+|E|) |
9. Algorithm Complexity & Comparison | 算法复杂度与对比
Understanding the time and space complexities of graph algorithms is vital for choosing the right one and for analysis questions. Below is a summary of complexities assuming adjacency list representation, where V = |V|, E = |E|.
理解图算法的时间和空间复杂度对于选择正确算法以及应对分析题目至关重要。下表总结了在邻接表表示下的复杂度，其中 V = |V|，E = |E|。
| Algorithm | Time Complexity | Space Complexity |
| BFS / DFS | O(V+E) | O(V) |
| Dijkstra (binary heap) | O((V+E) log V) | O(V) |
| Prim (binary heap) | O(E log V) | O(V) |
| Kruskal | O(E log E) | O(V) (union-find) |
| Topological Sort | O(V+E) | O(V) |
Choosing between Prim and Kruskal: Prim is faster for dense graphs (E ≈ V²), Kruskal is faster for sparse graphs. For unweighted shortest path, BFS suffices and is simpler than Dijkstra.
在 Prim 和 Kruskal 之间选择：Prim 对稠密图（E ≈ V²）更快，Kruskal 对稀疏图更快。对于无权最短路径，BFS 足够且比 Dijkstra 更简单。
10. Common Exam Applications & Pitfalls | 常见考试应用与陷阱
IB and CIE exams often present scenario-based questions: road networks (shortest path, MST), computer network routing (link-state uses Dijkstra), dependency graphs (topological sort), and social network analysis (BFS for degrees of separation). Recognising the underlying graph model is half the battle.
IB 和 CIE 考试常出基于场景的问题：道路网络（最短路径、MST），计算机网络路由（链路状态用 Dijkstra），依赖图（拓扑排序），社交网络分析（BFS 用于分离度）。识别底层的图模型是成功的一半。
Pitfalls include forgetting to mark visited vertices (leading to infinite loops), using Dijkstra with negative weights, confusing directed vs undirected edges during traversal, and omitting to update the distance of the source to 0. Also, topological sorting is only valid for DAGs; attempting on a graph with cycles will fail.
常见陷阱包括忘记标记已访问顶点（导致无限循环），在有负权的图上使用 Dijkstra，遍历时混淆有向边和无向边，忘记将源顶点距离更新为 0。此外，拓扑排序仅对 DAG 有效；在包含环的图上尝试会失败。
Always double-check your dry-run tables, and when implementing or tracing recursive DFS, be mindful of the call stack and the order of neighbour processing. Practise past paper questions to internalise the patterns.
始终仔细检查手算表格，在实现或追踪递归 DFS 时，注意调用栈和邻居处理的顺序。多练习历年真题来内化这些模式。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导