📚 IB Computer Science: Graph Algorithms Key Concepts | IB 计算机：图算法考点精讲
Graph algorithms form a fundamental part of the IB Computer Science syllabus, testing both theoretical understanding and practical application. From representing graphs efficiently to traversing them and finding optimal paths, these concepts are essential for solving real-world problems like network routing, social network analysis and project scheduling. This article breaks down the key graph algorithms you need to master for the IB exam, complete with clear explanations and common pitfalls.
图算法是 IB 计算机科学教学大纲中的基础部分，既考察理论理解也考察实际应用。从高效地表示图，到遍历图以及寻找最优路径，这些概念对于解决网络路由、社交网络分析和项目调度等现实问题至关重要。本文详细解析了 IB 考试中必须掌握的关键图算法，并配有清晰的解释和常见误区。
1. Graph Terminology and Basic Concepts | 图的基本术语与概念
A graph G = (V, E) consists of a set of vertices V (also called nodes) and a set of edges E connecting them. Graphs can be directed (edges have a direction) or undirected. A weighted graph assigns a numerical value to each edge, representing cost, distance or capacity. A path is a sequence of vertices where each consecutive pair is joined by an edge. A cycle is a path that starts and ends at the same vertex without repeating edges. Understanding these terms is the foundation for all graph algorithms.
图 G = (V, E) 由一组顶点 V（也称为节点）和连接它们的一组边 E 组成。图可以是有向的（边有方向）或无向的。加权图给每条边分配一个数值，表示成本、距离或容量。路径是一系列顶点，其中每对连续顶点都由一条边连接。环是一条起点和终点相同且不重复边的路径。理解这些术语是所有图算法的基础。
2. Graph Representations: Adjacency Matrix vs Adjacency List | 图的表示：邻接矩阵与邻接表
The adjacency matrix is a 2D array of size V×V where the cell [i][j] is 1 (or the weight) if an edge exists from vertex i to j, and 0 otherwise. Space complexity is O(V²), making it memory-intensive for sparse graphs but very fast for checking direct connections. In the IB exam, you may be asked to draw or interpret an adjacency matrix.
邻接矩阵是一个 V×V 大小的二维数组，如果顶点 i 到 j 之间有边，则单元格 [i][j] 为 1（或权重），否则为 0。空间复杂度为 O(V²)，对于稀疏图来说内存占用很大，但检查直接连接的速度非常快。在 IB 考试中，你可能会被要求绘制或解读邻接矩阵。
The adjacency list stores for each vertex a list of its neighbouring vertices (or edges with weights). Space complexity is O(V + E), which is efficient for sparse graphs. It is the preferred representation for most traversal algorithms, such as BFS and DFS, because it allows quick iteration over neighbours.
邻接表为每个顶点存储其相邻顶点的列表（或带权重的边）。空间复杂度为 O(V + E)，对于稀疏图来说很高效。它是大多数遍历算法（如 BFS 和 DFS）的首选表示方式，因为可以快速迭代相邻节点。
3. Depth-First Search (DFS) | 深度优先搜索
DFS explores a graph by going as deep as possible along a branch before backtracking. It can be implemented using recursion (implicit stack) or an explicit stack. The algorithm marks a starting vertex as visited, then recursively visits an unvisited neighbour until all reachable vertices are visited. DFS is useful for detecting cycles, topological ordering, and solving maze-like problems.
DFS 沿着一条分支尽可能深入地探索图，然后再回溯。它可以使用递归（隐式栈）或显式栈来实现。算法将起始顶点标记为已访问，然后递归访问未访问过的邻居，直到所有可达顶点都被访问。DFS 可用于检测环、拓扑排序以及解决类似迷宫的问题。
Time complexity is O(V + E) when using an adjacency list, because each vertex and edge is processed once. The space complexity is O(V) in the worst case due to the recursion stack. In an exam, you might be asked to trace DFS execution order on a given graph.
使用邻接表时，时间复杂度为 O(V + E)，因为每个顶点和边都被处理一次。最坏情况下的空间复杂度为 O(V)，这是由递归栈造成的。在考试中，你可能会被要求在一个给定图上追踪 DFS 的执行顺序。
4. Breadth-First Search (BFS) | 广度优先搜索
BFS explores a graph layer by layer, visiting all vertices at the current distance before moving to the next distance level. It uses a queue data structure to keep track of vertices to visit. Starting from a source vertex, BFS marks it as visited, enqueues it, and then repeatedly dequeues a vertex and enqueues all its unvisited neighbours. BFS is the foundation for finding shortest paths in unweighted graphs.
BFS 逐层探索图，在移动到下一个距离层级之前先访问当前距离上的所有顶点。它使用队列数据结构来追踪待访问的顶点。从源顶点开始，BFS 将其标记为已访问并入队，然后反复将顶点出队，并将其所有未访问的邻居入队。BFS 是在无权图中寻找最短路径的基础。
Time complexity is also O(V + E) with an adjacency list. BFS guarantees the shortest path in terms of number of edges if the graph is unweighted. IB exam questions may ask you to simulate BFS and record the order of vertex visits or to compare BFS with DFS.
使用邻接表时，时间复杂度也是 O(V + E)。如果图是无权的，BFS 能保证找到边数最少的最短路径。IB 考试题可能会要求你模拟 BFS 并记录顶点访问顺序，或者比较 BFS 与 DFS。
5. Shortest Path Problem: Dijkstra’s Algorithm | 最短路径问题：Dijkstra 算法
Dijkstra’s algorithm finds the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights. It maintains a set of vertices whose shortest distance from the source is known and repeatedly selects the unvisited vertex with the smallest tentative distance, updating its neighbours’ distances if a shorter path is found. This greedy approach guarantees optimality only when all edge weights are ≥ 0.
Dijkstra 算法在具有非负边权值的图中，找出从单一源顶点到所有其他顶点的最短路径。它维护一个已知从源点出发最短距离的顶点集，并反复选择未访问顶点中暂定距离最小的那个，如果找到更短路径则更新其邻居的距离。这种贪心方法仅在所有权重 ≥ 0 时才保证最优解。
Implementation often uses a priority queue (min-heap) to efficiently extract the minimum distance vertex. With a binary heap, time complexity is O((V+E) log V). The algorithm does not work with negative edge weights; for those, the Bellman-Ford algorithm is required. IB HL typically requires understanding the steps and limitations.
实现通常使用优先队列（最小堆）来高效地提取距离最小的顶点。使用二叉堆时，时间复杂度为 O((V+E) log V)。该算法不能处理负权边；对此需要使用贝尔曼-福特算法。IB 高水平（HL）通常要求理解其步骤和局限性。
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 the minimum possible total edge weight, without cycles. Prim’s algorithm builds the MST incrementally, starting from an arbitrary vertex. At each step, it adds the cheapest edge that connects a vertex in the tree to a vertex outside the tree. This is another greedy algorithm that yields an optimal MST.
一个连通无向加权图的最小生成树（MST）是所有边的一个子集，它连接所有顶点并使总边权和最小，且无环。Prim 算法逐步构建 MST，从任意一个顶点开始。每一步，它添加将树内顶点与树外顶点连接起来的最便宜的边。这也是另一种能够得出最优 MST 的贪心算法。
Using a priority queue similar to Dijkstra’s, the time complexity is O((V+E) log V). Prim’s algorithm works well on dense graphs. The main difference from Dijkstra is that Prim considers the edge weight to reach any unvisited vertex, while Dijkstra considers the accumulated path length from the source.
使用类似于 Dijkstra 的优先队列，时间复杂度为 O((V+E) log V)。Prim 算法在稠密图上效果很好。它与 Dijkstra 的主要区别在于：Prim 考虑的是到达任意未访问顶点的边权，而 Dijkstra 考虑的是从源点出发的累积路径长度。
7. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树：Kruskal 算法
Kruskal’s algorithm is an alternative method for finding an MST. It sorts all edges in non-decreasing order of weight and adds each edge to the MST if it does not form a cycle. To efficiently detect cycles, a disjoint-set data structure (Union-Find) is used. This approach processes edges globally, making it attractive for sparse graphs.
Kruskal 算法是寻找 MST 的另一种方法。它按权重非递减顺序对所有边进行排序，并将每条边添加到 MST 中，前提是该边不会形成环。为了高效地检测环，使用了不相交集数据结构（并查集）。这种方法从全局处理边，因此对稀疏图很有吸引力。
Time complexity is O(E log E) due to the sorting step, which dominates. In connected graphs, E ≥ V-1, so it is comparable to Prim’s for sparse graphs. IB exams may ask you to list the edges in the order they are added by Kruskal’s algorithm, or to compare the two MST algorithms.
时间复杂度为 O(E log E)，主要来自排序步骤。在连通图中，E ≥ V-1，因此对于稀疏图而言，它与 Prim 算法有可比性。IB 考试可能会要求你列出 Kruskal 算法添加边的顺序，或者比较这两种 MST 算法。
8. Topological Sorting | 拓扑排序
Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before v. It is used in scheduling tasks with dependencies, e.g., compiling modules. One algorithm based on DFS recursively visits nodes and pushes them onto a stack after processing all outgoing edges; the final stack order is the topological order.
拓扑排序是有向无环图（DAG）中顶点的线性排序，使得对于每条有向边 u → v，顶点 u 都排在 v 前面。它用于对具有依赖关系的任务进行调度，例如编译模块。一种基于 DFS 的算法递归地访问节点，并在处理完所有出边后将其压入栈中；最终的栈顺序就是拓扑顺序。
An alternative method (Kahn’s algorithm) repeatedly removes vertices with no incoming edges (in-degree zero) and appends them to the result. Both run in O(V+E) time. The graph must be a DAG; if a cycle exists, topological sorting is impossible, which provides a way to detect cycles.
另一种方法（Kahn 算法）反复移除没有入边的顶点（入度为零）并将其附加到结果中。两者的运行时间均为 O(V+E)。图必须是一个 DAG；如果存在环，则拓扑排序不可能，这也提供了一种检测环的方法。
9. A* Search Algorithm (HL Extension) | A* 搜索算法（HL 拓展）
A* is an informed search algorithm that extends Dijkstra by using a heuristic function h(n) estimating the cost from node n to the goal. It evaluates nodes by f(n) = g(n) + h(n), where g(n) is the known cost from the start to n. If h(n) is admissible (never overestimates) and consistent, A* finds the optimal path. In IB HL, you may encounter A* in pathfinding contexts such as grid maps.
A* 是一种启发式搜索算法，它通过使用启发式函数 h(n) 估算从节点 n 到目标节点的代价，对 Dijkstra 进行了扩展。它通过 f(n) = g(n) + h(n) 来评估节点，其中 g(n) 是从起点到 n 的已知代价。如果 h(n) 是可采纳的（从不高估）且一致的，A* 就能找到最优路径。在 IB HL 中，你可能会在网格地图等寻路情境中遇到 A*。
The choice of heuristic dramatically affects performance; for grid maps, Manhattan distance is common if movements are limited to four directions. A* degenerates to Dijkstra when h(n) = 0. Understanding how the heuristic influences the search is important for exam explanations.
启发式函数的选择会极大影响性能；对于网格地图，如果移动仅限于四个方向，曼哈顿距离是常见的。当 h(n) = 0 时，A* 退化为 Dijkstra。理解启发式函数如何影响搜索对于考试中的解释非常重要。
10. Algorithmic Complexity and Choosing the Right Algorithm | 算法复杂性与选择合适的算法
Knowing the time and space complexities is crucial for IB exam success. The table below summarises the complexities for common graph algorithms, assuming an adjacency list representation unless noted otherwise. These help in justifying which algorithm is most suitable under given constraints (e.g., dense vs sparse graph, weighted vs unweighted).
了解时间与空间复杂度对于 IB 考试成功至关重要。下表总结了常见图算法的复杂度，除非特别说明，均基于邻接表表示。这些有助于在给定约束条件下（如稠密图与稀疏图、加权与无权）论证哪种算法最合适。
| Algorithm | Time Complexity | Space Complexity |
|---|---|---|
| BFS / DFS | O(V + E) | O(V) |
| Dijkstra (with heap) | O((V+E) log V) | O(V) |
| Prim (with heap) | O((V+E) log V) | O(V) |
| Kruskal | O(E log E) | O(V + E) |
| Topological Sort | O(V + E) | O(V) |
When choosing an algorithm, consider edge weights (negative? zero?), graph density, and whether you need shortest paths or minimum spanning tree. For IB questions, always explain your reasoning using complexity analysis.
在选择算法时，要考虑边权（负权？零权？）、图的密度，以及你需要的是最短路径还是最小生成树。对于 IB 题目，一定要用复杂度分析解释你的推理。
11. Common Mistakes and Exam Tips | 常见错误与考试技巧
Many students confuse Dijkstra’s algorithm with BFS. Remember: BFS works for unweighted graphs; Dijkstra is needed for weighted graphs with non-negative weights. Another common error is forgetting that DFS and BFS require a visited set to prevent infinite loops in cyclic graphs.
许多学生将 Dijkstra 算法与 BFS 混淆。请记住：BFS 用于无权图；Dijkstra 则用于非负权重的加权图。另一个常见错误是忘记 DFS 和 BFS 需要已访问集合来防止在带环图中出现无限循环。
When tracing Kruskal’s algorithm, always process edges in sorted order and only add if no cycle is formed – drawing the disjoint-set trees can help. For Prim’s, keep track of the cut. In exam answers, clearly label your working, and state the data structure used (e.g., adjacency list).
在追踪 Kruskal 算法时，始终按排序顺序处理边，并且只有在不形成环时才添加——画出不相交集树会有所帮助。对于 Prim 算法，要跟踪割。在考试答案中，清楚标注你的解题过程，并说明使用的数据结构（如邻接表）。
Finally, always check whether the question asks for steps, final output, or an explanation of why a particular algorithm is correct. Use precise terminology such as ‘relaxation’ for updating distances in Dijkstra and ‘cut’ for edges considered in Prim’s.
最后，务必检查题目是要求写出步骤、最终输出，还是解释为什么某个算法是正确的。使用精确的术语，如 Dijkstra 中更新距离的“松弛”和 Prim 算法中考虑的边的“割”。
12. Practising with Real IB-style Questions | 用 IB 风格真题练习
The best way to internalise graph algorithms is to solve past paper questions. Draw the graphs, simulate the algorithms step by step, and write pseudocode. Pay attention to questions that ask you to modify an algorithm for a specific context, as IB often tests applied understanding. Review the IB data structures option syllabus to ensure all required algorithms (including A* at HL) are covered.
内化图算法的最好方法是做历年真题。绘制图表，一步步模拟算法，并写下伪代码。注意那些要求你针对特定情境修改算法的题目，因为 IB 经常考察应用理解。复习 IB 数据结构选修大纲，确保涵盖所有必需算法（包括 HL 的 A*）。
Mastering graph algorithms not only secures high marks in the exam but also builds a strong foundation for further studies in computer science, where graphs model countless real-world systems.
掌握图算法不仅能在考试中稳得高分，也为计算机科学的进一步学习打下坚实基础，因为图可以为无数现实系统建模。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导