📚 Graph Algorithms: Key Exam Topics for IB and Edexcel Computer Science | IB Edexcel 计算机：图算法 考点精讲
Graph algorithms form a cornerstone of the IB and Edexcel Computer Science syllabi, testing your ability to model problems, traverse structures, and optimize routes. This guide breaks down every essential concept, from adjacency representations to shortest‑path and spanning tree algorithms, with paired English and Chinese explanations to support your revision.
图算法是 IB 和 Edexcel 计算机科学考纲的基石，考查你对问题建模、结构遍历和路径优化的能力。本文用配对的中英文解析每个核心考点，从邻接表示法到最短路径和生成树算法，助你高效复习。
1. Graph Terminology and Representations | 图的基本术语与表示法
A graph G = (V, E) consists of vertices (V) and edges (E). In an undirected graph, an edge between A and B is bidirectional; in a directed graph (digraph), it has direction. Weighted graphs attach a numerical cost to each edge. Understanding these foundations is the first step toward mastering traversal and pathfinding.
图 G = (V, E) 由顶点(V)和边(E)组成。在无向图中，A 和 B 之间的边是双向的；在有向图中则具有方向。加权图为每条边附加一个数值代价。掌握这些基础是精通遍历和寻路的第一步。
Two common representations are the adjacency matrix and the adjacency list. An adjacency matrix is a 2D array of size |V|×|V|, where cell (i, j) is 1 (or the weight) if an edge exists, else 0. An adjacency list uses an array of linked lists or dynamic arrays, where each vertex stores its neighbors. Exam questions often ask you to compare their space and time efficiency.
两种常见表示法是邻接矩阵和邻接表。邻接矩阵是一个 |V|×|V| 的二维数组，若边存在，则单元格 (i, j) 为 1（或权重），否则为 0。邻接表使用链表或动态数组，每个顶点存储其邻居。考题常要求比较两者的空间和时间效率。
| Representation | Space | Edge existence check | Iterating neighbors |
|---|---|---|---|
| Adjacency Matrix | O(V²) | O(1) | O(V) |
| Adjacency List | O(V + E) | O(degree) | O(degree) |
2. Depth‑First Search (DFS) | 深度优先搜索
DFS explores a graph by going as deep as possible along a branch before backtracking. It can be implemented recursively or with an explicit stack. DFS is used for topological sorting, cycle detection, and path existence. The standard pseudocode marks a node as visited, then recursively calls DFS on each unvisited neighbor.
深度优先搜索沿着一个分支尽可能深地探索，无法继续时再回溯。它可用递归或显式栈实现。DFS 常用于拓扑排序、环路检测和路径存在性。标准伪代码将节点标记为已访问，然后对每个未访问的邻居递归调用 DFS。
In IB and Edexcel exams, you must be able to trace DFS on a given graph, showing the order of vertex visits and the contents of the stack (or call stack) at each step. Understand how the adjacency list order influences the traversal sequence when multiple choices exist.
在 IB 和 Edexcel 考试中，你必须能够对给定图进行 DFS 模拟，展示每一步的顶点访问顺序和栈（或调用栈）内容。理解当存在多个选择时，邻接表中的顺序如何影响遍历序列。
DFS(v): mark v visited; for each neighbor u of v: if not visited then DFS(u)
Complexity: O(V + E) when adjacency list is used. Exam questions often test the recursive depth and the maximum stack size in terms of the longest path length.
复杂度：使用邻接表时为 O(V + E)。试题常考查递归深度以及用最长路径长度表示的最大栈大小。
3. Breadth‑First Search (BFS) | 广度优先搜索
BFS explores a graph level by level, using a queue. It finds the shortest path (in terms of number of edges) in an unweighted graph. Starting from a source node, BFS marks it as visited, enqueues it, then repeatedly dequeues a vertex and enqueues all its unvisited neighbors.
广度优先搜索使用队列逐层探索图。它能在非加权图中找到最短路径（按边数计）。从源节点开始，BFS 将其标记为已访问并入队，然后反复将队首顶点出队，并将其所有未访问邻居入队。
BFS is essential for shortest‑path puzzles, peer‑to‑peer network flooding, and web crawling. In exams, you may be asked to produce the BFS traversal order, or to compute distances from a source using a distance array.
BFS 对于最短路径谜题、P2P 网络广播和网络爬虫至关重要。考试中可能要求你给出 BFS 遍历顺序，或使用距离数组计算从源出发的距离。
Both DFS and BFS share the same O(V + E) time with adjacency lists. The difference is in the data structure: stack (or recursion) for DFS, queue for BFS. You must be able to compare their applications.
DFS 和 BFS 在邻接表下的时间复杂度均为 O(V + E)，区别在于数据结构：DFS 使用栈（或递归），BFS 使用队列。你必须能比较它们的应用场景。
4. Topological Sorting | 拓扑排序
A topological order of a directed acyclic graph (DAG) is a linear ordering of vertices such that for every directed edge (u, v), u comes before v. This is used in build systems, course prerequisite chains, and task scheduling. Both DFS‑based and Kahn’s algorithm (using in‑degree counts) are examinable.
有向无环图(DAG)的拓扑排序是顶点的线性排序，使得每条有向边 (u, v) 中 u 在 v 之前。它用于构建系统、课程先修链条和任务调度。基于 DFS 的方法和 Kahn 算法（使用入度计数）都是考试内容。
With DFS, you perform a post‑order traversal, pushing vertices onto a stack upon finishing their DFS calls. Popping the stack yields a valid topological order. Kahn’s algorithm repeatedly removes vertices with in‑degree zero, appending them to the result and decrementing neighbors’ in‑degrees.
在 DFS 中，进行后序遍历，在顶点完成 DFS 调用时将其压入栈中。弹出栈即得到有效的拓扑排序。Kahn 算法反复移除入度为零的顶点，将其加入结果，并减少邻居的入度。
Topological Sort (Kahn): while there exists a vertex with in‑degree 0, remove it and update neighbors; if all vertices processed, output order is topological.
Both algorithms detect cycles: if not all vertices are processed, a cycle exists. This is a common exam question: ‘Prove whether a directed graph contains a cycle’.
两种算法均可检测环：如果并非所有顶点都被处理，则存在环。这是常见的考题：‘证明一个有向图是否包含环’。
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 distance table, initialized to infinity except the source (0), and repeatedly selects the unvisited vertex with the smallest tentative distance, relaxing its neighbors.
Dijkstra 算法在具有非负权重的加权图中找出从单一源点到所有其他顶点的最短路径。它维护一个距离表，初始化为无穷大（源点为 0），反复选择未访问顶点中暂定距离最小的顶点，对其邻居进行松弛操作。
Relaxation: if distance[u] + weight(u, v) < distance[v], then distance[v] is updated. The algorithm terminates when all vertices have been visited. Using a priority queue (min‑heap) for the selection step yields O((V + E) log V) complexity, which is typical for exams.
松弛操作：如果 distance[u] + weight(u, v) < distance[v]，则更新 distance[v]。当所有顶点都被访问时算法终止。使用优先队列（最小堆）进行选择可将复杂度优化到 O((V + E) log V)，这是考试中的典型要求。
You must be able to trace Dijkstra step‑by‑step, showing the distance array and the priority queue contents. Remember it fails if negative edges exist; this is a classic exam pitfall.
你必须能逐步追踪 Dijkstra 的执行过程，展示距离数组和优先队列的内容。记住如果存在负权边，该算法会失效；这是典型的考试陷阱。
6. A* Search Algorithm (Extension) | A* 搜索算法（拓展）
A* is a heuristic‑guided shortest‑path algorithm commonly required in IB HL or Edexcel advanced topics. It extends Dijkstra by using an evaluation function f(v) = g(v) + h(v), where g(v) is the actual cost from source to v and h(v) is a heuristic estimate from v to the target. A good heuristic (e.g., Manhattan distance on a grid) keeps A* both admissible and near‑optimal.
A* 是一种启发式引导的最短路径算法，常见于 IB HL 或 Edexcel 高阶主题。它通过评价函数 f(v) = g(v) + h(v) 扩展 Dijkstra，其中 g(v) 是从源到 v 的实际代价，h(v) 是从 v 到目标的启发式估计。良好的启发式（如网格上的曼哈顿距离）使 A* 可接受且接近最优。
In exam discussions, you may be asked to compare Dijkstra with A*, explaining when A* is more efficient. Focus on the admissibility condition: h(v) must never overestimate the true remaining cost. Show how the choice of heuristic affects the number of explored vertices.
在考试讨论中，可能要求你比较 Dijkstra 和 A*，解释 A* 何时更有效。关注可接受条件：h(v) 绝不能高估真实剩余代价。展示启发式的选择如何影响已探索顶点的数量。
7. Minimum Spanning Tree – Prim’s Algorithm | 最小生成树 – Prim 算法
A minimum spanning tree (MST) connects all vertices with the minimum total edge weight. Prim’s algorithm grows the MST from an arbitrary start vertex, maintaining a set of visited vertices and repeatedly choosing the smallest edge connecting the visited set to an unvisited vertex. It is greedy and gives an optimal solution.
最小生成树(MST)以最小的总边权连接所有顶点。Prim 算法从任意起始顶点出发构建 MST，维护一个已访问顶点集，并反复选择连接已访问集与未访问顶点的最小边。它是贪心的且能给出最优解。
Trace Prim’s using a table or a stepwise diagram. The algorithm can be implemented with a priority queue, similar to Dijkstra, but it focuses on edges rather than cumulative distances. Complexity: O(E log V) with a binary heap.
使用表格或逐步图表追踪 Prim 算法。该算法可用优先队列实现，类似于 Dijkstra，但关注边而非累积距离。复杂度：使用二叉堆时为 O(E log V)。
Exam questions often ask for the order in which edges are added to the MST, or to prove why the greedy choice is safe (cut property).
考题常询问加入 MST 的边的顺序，或证明贪心选择的正确性（割性质）。
8. 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, provided they do not form a cycle. A disjoint‑set (union‑find) data structure is used to efficiently detect cycles. This algorithm is especially effective for sparse graphs.
Kruskal 算法通过按权重排序所有边并逐个添加（只要不形成环）来构建 MST。使用并查集（union‑find）数据结构高效检测环。该算法对于稀疏图特别有效。
You must be able to execute Kruskal’s step‑by‑step, showing the sorted edge list and the evolving forest. Compare Prim’s and Kruskal’s: Prim’s works well with dense graphs and adjacency matrices, while Kruskal’s prefers edge list and sparse graphs. Both are O(E log E), but differences emerge based on the data structure.
你必须能按步骤执行 Kruskal，展示排序后的边列表和演化的森林。比较 Prim 与 Kruskal：Prim 适用于稠密图和邻接矩阵，而 Kruskal 更适用于边列表和稀疏图。两者均为 O(E log E)，但因数据结构不同而有差异。
9. Cycle Detection in Directed and Undirected Graphs | 有向图与无向图中的环路检测
In undirected graphs, a back edge encountered during DFS indicates a cycle. You simply record vertices visited and their parents; if you see an already visited neighbor that is not the parent, a cycle exists. In directed graphs, DFS uses a recursion stack to detect back edges: a back edge to a vertex currently in the recursion stack means a cycle.
在无向图中，DFS 过程中遇到回边（back edge）表明存在环。只需记录已访问顶点及其父节点；如果看到已访问的邻居且不是父节点，则存在环。在有向图中，DFS 使用递归栈检测回边：指向当前递归栈中某个顶点的回边表示存在环。
Alternatively, cycle detection in directed graphs can use topological sorting: if Kahn’s algorithm fails to process all vertices, there is a cycle. Exam papers frequently present a graph and ask you to identify whether it is cyclic using a specific method.
或者，有向图中的环检测可使用拓扑排序：如果 Kahn 算法未能处理全部顶点，则存在环。试卷常常给出一个图并要求你使用特定方法判断其是否包含环。
10. Exam‑Style Pitfalls and Data Structure Choices | 考试型陷阱与数据结构选择
Common pitfalls include: forgetting to update the priority queue after a distance decrease in Dijkstra; applying Dijkstra on graphs with negative edges; confusing the order of visited vertices for DFS vs BFS; and using an adjacency matrix for a sparse graph, leading to excessive space. Remember to use the correct complexity analysis based on representation.
常见陷阱包括：在 Dijkstra 中距离减少后忘记更新优先队列；在含有负权边的图上应用 Dijkstra；混淆 DFS 与 BFS 的访问顺序；对稀疏图使用邻接矩阵导致空间过大。务必根据表示法使用正确的复杂度分析。
Always draw the graph when tracing an algorithm. In IB and Edexcel, diagrams are often provided; you must label distances, queue contents, or MST edges directly on the diagram. Practise with graphs that have multiple possible start choices to understand decision points.
追踪算法时务必画出图形。在 IB 和 Edexcel 考试中，通常会提供图示；你必须直接在图上标注距离、队列内容或 MST 边。用具有多种起始选择的图进行练习，以理解决策点。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导