IB AQA Computer Science: Graph Algorithms – Key Exam Points | IB AQA 计算机：图算法考点精讲

📚 IB AQA Computer Science: Graph Algorithms – Key Exam Points | IB AQA 计算机：图算法考点精讲

Graph algorithms form a core part of both IB Computer Science and AQA A-level Computer Science specifications. Understanding how to represent graphs, traverse them, and solve classic problems such as shortest path and minimum spanning tree is essential for scoring well in exams. This revision guide covers the most frequently assessed topics, blending conceptual clarity with exam-style techniques.

图算法是IB计算机科学与AQA A-level计算机课程的核心内容。掌握图的表示方法、遍历技术以及最短路径、最小生成树等经典问题的求解，是考试得高分的关键。本考点精讲涵盖最常见的考查主题，兼顾概念理解与应试技巧，助你系统梳理重点。

1. Graph Fundamentals and Terminology | 图的基本概念与术语

A graph G = (V, E) consists of a set of vertices V and a set of edges E. In directed graphs, each edge has an orientation, whereas edges in undirected graphs have no direction. Important terms include degree (number of incident edges), path (sequence of vertices connected by edges), cycle (a path that starts and ends at the same vertex), and connectivity. Weighted graphs assign a numerical cost to each edge, often representing distance or time.

图 G = (V, E) 由顶点集合 V 和边集合 E 组成。有向图中每条边都有方向，而无向图中的边则没有方向差异。重点术语包括度（与顶点相连的边数）、路径（由边连接的顶点序列）、环（起点和终点相同的路径）以及连通性。带权图为每条边赋予一个数值，通常表示距离或时间成本。

In exam questions, you might be asked to count vertices and edges, identify cycles, or distinguish between simple graphs and multigraphs. A simple graph has no loops and at most one edge between any pair of vertices. Be able to classify graphs as connected, complete, bipartite, or trees.

考试中可能要求你计算顶点和边的数量、识别环，或者区分简单图与多重图。简单图没有自环，且任意两点间至多只有一条边。同时要能够将图分类为连通图、完全图、二分图或树。

2. Graph Representations: Adjacency Matrix and List | 图的表示：邻接矩阵与邻接表

There are two primary ways to represent a graph in a computer program: the adjacency matrix and the adjacency list. An adjacency matrix is a 2D array of size V×V, where entry [i][j] is 1 (or the edge weight) if there is an edge from vertex i to vertex j, and 0 otherwise. For an undirected graph, the matrix is symmetric.

计算机中表示图主要有两种方式：邻接矩阵和邻接表。邻接矩阵是一个 V×V 的二维数组，若顶点 i 到顶点 j 有边，则元素 [i][j] 为 1（或边权重），否则为 0。对于无向图，该矩阵是对称的。

An adjacency list stores, for each vertex, a list of its adjacent vertices or outgoing edges. This structure is more memory-efficient for sparse graphs, whereas the adjacency matrix allows O(1) edge existence checks but consumes O(V²) space. Know how to construct both representations from a diagram and analyse their space/time trade-offs.

邻接表为每个顶点存储其相邻顶点或出边的列表。对于稀疏图，这种结构更节省内存，而邻接矩阵能以 O(1) 时间检查边是否存在，但消耗 O(V²) 的空间。要能从图中构建这两种表示，并分析它们的时空权衡。

Representation	Space	Edge Check	Best for
Adjacency Matrix	O(V²)	O(1)	Dense graphs
Adjacency List	O(V + E)	O(degree)	Sparse graphs

表：邻接矩阵与邻接表的比较

3. Breadth-First Search (BFS) Algorithm | 广度优先搜索算法

BFS explores a graph level by level, starting from a provided source vertex. It uses a queue to keep track of vertices to visit next. When a vertex is dequeued, all its unvisited neighbours are marked as visited and enqueued. This ensures that vertices are processed in non-decreasing order of their distance from the source.

广度优先搜索从一个源顶点开始，逐层探索图。它使用队列记录下一步要访问的顶点。当一个顶点出队时，其所有未访问的邻居都会被标记并加入队列。这保证了顶点按照与源点距离不减的顺序被处理。

BFS is commonly used to find the shortest path (in terms of number of edges) in an unweighted graph, to test bipartiteness, or to perform level-order traversal. Its time complexity is O(V + E) when using an adjacency list. In exam scenarios, you may be required to trace the order of visited vertices or write pseudocode for BFS.

BFS常用于求解无权图中的最短路径（按边数计）、检测二分图或进行层序遍历。使用邻接表时其时间复杂度为 O(V + E)。考试中可能要求你追踪顶点访问顺序或写出 BFS 伪代码。

4. Depth-First Search (DFS) Algorithm | 深度优先搜索算法

DFS explores as far as possible along each branch before backtracking. It can be implemented using recursion (call stack) or an explicit stack. Starting from the source, DFS visits an unvisited neighbour and applies the same strategy recursively until no unvisited neighbour remains, then backtracks.

深度优先搜索尽可能沿着每个分支深入探索，直到无法继续才回溯。它可以通过递归（调用栈）或显式栈实现。从源点开始，DFS 访问一个未访问的邻居并递归应用同样策略，直到没有未访问邻居时回溯。

DFS is the foundation for many graph algorithms: detecting cycles, topological ordering, finding connected components, and solving mazes. Its time complexity is also O(V + E). Be prepared to simulate DFS on a diagram, noting the order of discovery and finish times, and to explain how recursion stack frames evolve.

DFS 是许多图算法的基础：环检测、拓扑排序、寻找连通分量以及迷宫求解。时间复杂度同为 O(V + E)。备考时要能对图示模拟 DFS，记录发现顺序和完成时间，并解释递归栈帧的变化。

5. BFS vs DFS: Choosing the Right Traversal | BFS与DFS：选择合适的遍历

Although both BFS and DFS visit every reachable vertex, their behaviours differ significantly. BFS finds the shortest unweighted path and tends to stay closer to the source, making it ideal for peer-to-peer network searches or web crawling limited by depth. DFS, on the other hand, uses less memory on deep graphs and can be more suitable for constraint-satisfaction problems like puzzle solving.

尽管 BFS 和 DFS 都能访问所有可达顶点，但行为差异显著。BFS 能找到无权最短路径，且倾向于在靠近源点处搜索，适合点对点网络搜索或限定深度的网页爬取。而 DFS 在深度的图中内存占用更小，更适合谜题求解等约束满足问题。

Memory-wise, BFS queue can grow to O(V) in the worst case while DFS stack depth can also be O(V). However, in practice BFS often requires storing more nodes at once. Examiners like to ask scenario-based questions: “Which traversal would you use to find the fastest route in a subway map with equal transfer times?” The answer is BFS because it gives the minimal number of edges.

在内存方面，BFS 的队列在最坏情况下可增到 O(V)，而 DFS 的栈深度也可以达到 O(V)。不过实践中 BFS 往往需要同时存储更多节点。考官喜欢设置情境题：“换乘时间相等的地铁图中，哪种遍历能最快找到路径？”答案是 BFS，因为它能给出最少边数。

6. Shortest Path Problem and Dijkstra’s Algorithm | 最短路径问题与Dijkstra算法

When edges carry non-negative weights, Dijkstra’s algorithm finds the shortest path from a single source to all other vertices. It maintains a priority queue (min‑heap) of vertices keyed by their current shortest distance estimate. Starting with distance 0 at the source and ∞ elsewhere, it repeatedly extracts the vertex with the smallest distance, relaxes its outgoing edges, and updates neighbours if a cheaper path is found.

当边权非负时，Dijkstra 算法可以找到从单一源点到所有其他顶点的最短路径。它维护一个以当前最短距离估计为键值的最小优先队列。源点距离初始为 0，其余为∞，算法反复提取距离最小的顶点，对其出边进行松弛操作，若找到更短路径则更新邻居的距离。

The relaxation condition is: if d[u] + w(u, v) < d[v], then d[v] = d[u] + w(u, v). Dijkstra is correct only when all edge weights are non-negative; negative edges can cause incorrect results. Its time complexity is O((V+E) log V) with a binary heap. In exams, you must be able to fill a distance table step by step and reconstruct the shortest path using a predecessor array.

松弛条件为：若 d[u] + w(u, v) < d[v]，则 d[v] = d[u] + w(u, v)。仅当所有边权非负时 Dijkstra 算法才是正确的，负权边会导致结果出错。使用二叉堆时时间复杂度为 O((V+E) log V)。考试中必须能够逐步填写距离表，并利用前驱数组重建最短路径。

7. Step-by-step Dijkstra with a Worked Example | Dijkstra算法分步详解及示例

Consider the following weighted directed graph: vertices A, B, C, D, E. Edges and weights: A→B (6), A→D (1), B→C (5), B→D (2), B→E (2), D→B (2), D→E (1), E→C (5). Source = A.

考虑如下带权有向图：顶点 A, B, C, D, E。边及权重：A→B (6), A→D (1), B→C (5), B→D (2), B→E (2), D→B (2), D→E (1), E→C (5)。源点 = A。

Step	Visited	B	C	D	E
Init	–	∞	∞	∞	∞
1	A	6	∞	1	∞
2	A, D	3	∞	1	2
3	A, D, E	3	7	1	2
4	A, D, E, B	3	5	1	2
5	All	3	5	1	2

Starting from A, D is closest (1), then E (2), then B (3 via D), and finally C (5 via B). The shortest path A→C is A→D→B→C with total weight 5. This systematic filling of the distance table is exactly what exam mark schemes expect.

从 A 开始，D 最近 (1)，然后是 E (2)，接着 B（经 D 为 3），最后 C（经 B 为 5）。A→C 的最短路径为 A→D→B→C，总权重 5。这种逐步填写距离表的方式正是阅卷标准答案所期望的。

8. A* Search Algorithm: Heuristic Optimization | A*搜索算法：启发式优化

A* extends Dijkstra’s idea by adding a heuristic function h(n) that estimates the cost from node n to the goal. The priority queue is keyed by f(n) = g(n) + h(n), where g(n) is the actual cost from source to n. If h(n) is admissible (never overestimates the true cost) and consistent, A* guarantees the optimal shortest path while often exploring far fewer nodes than Dijkstra.

A* 算法在 Dijkstra 基础上引入启发式函数 h(n)，用于估计从节点 n 到目标的代价。优先队列以 f(n) = g(n) + h(n) 为键值，其中 g(n) 为从源点到 n 的实际成本。若 h(n) 是可接受的（从不高于真实成本）且满足一致性，A* 既能保证找到最优路径，又通常比 Dijkstra 探索更少的节点。

Common heuristics include Euclidean distance and Manhattan distance for grid maps. In IB and some AQA scenarios, you might be asked to explain the role of the heuristic or compare A* with Dijkstra. Remember that if h(n) = 0 for all nodes, A* degenerates into Dijkstra. A well-chosen heuristic makes A* more efficient for real-world pathfinding such as GPS navigation.

常见的启发式包括欧几里得距离和网格地图中的曼哈顿距离。在 IB 和部分 AQA 试题中，可能要求解释启发式的作用或比较 A* 与 Dijkstra。注意如果所有节点的 h(n)=0，A* 退化为 Dijkstra。精心选择的启发式使 A* 在 GPS 导航等实际寻路场景中效率更高。

9. Minimum Spanning Trees: Prim’s and Kruskal’s Algorithms | 最小生成树：Prim与Kruskal算法

A minimum spanning tree (MST) connects all vertices of an undirected weighted graph with the minimum total edge weight and without cycles. Prim’s algorithm grows the tree one vertex at a time: starting from an arbitrary vertex, it repeatedly adds the cheapest edge that connects a tree vertex to a non‑tree vertex. Kruskal’s algorithm, conversely, sorts all edges by weight and adds them one by one, skipping those that would create a cycle (using union‑find).

最小生成树（MST）以最小的总边权连接无向带权图的所有顶点，且不含环。Prim 算法从一个任意顶点开始，逐点增长，反复添加连接树内顶点和树外顶点的最便宜边。Kruskal 算法则将所有边按权重排序，依次添加，跳过会形成环的边（借助并查集）。

You must be able to trace both algorithms on a given graph and state the final MST weight. Prim’s works well with dense graphs and adjacency matrices, while Kruskal’s is often simpler to implement using edge lists. Exam questions frequently ask for the order in which edges are added, or to identify which algorithm would be more efficient for a specific representation.

要求能够对给定图追踪这两种算法并给出最终 MST 的权重。Prim 适合稠密图和邻接矩阵，而 Kruskal 基于边列表实现通常更简洁。考题常要求写出边的添加顺序，或针对特定表示方法判断哪种算法更高效。

10. Topological Sorting for Directed Acyclic Graphs | 有向无环图的拓扑排序

Topological sorting orders the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge u → v, u comes before v in the ordering. This is essential in build systems, task scheduling, and prerequisite chains. Two common approaches are Kahn’s algorithm (using indegree counts and a queue) and DFS‑based post‑order reversal.

拓扑排序将为有向无环图（DAG）的顶点安排一个顺序，使得对于每条有向边 u → v，u 在 v 之前。这在构建系统、任务调度和前置课程链中至关重要。常见的两种方法是 Kahn 算法（利用入度计数和队列）以及基于 DFS 的后序反转法。

Kahn’s algorithm repeatedly removes vertices with indegree 0, appends them to the result, and decrements the indegrees of their neighbours. If the graph contains a cycle, some vertices will never reach indegree 0; thus, topological sort can also detect cycles. Be ready to simulate either method and to identify valid topological orders when multiple choices exist.

Kahn 算法反复移除入度为 0 的顶点，将其加入结果，并递减邻居的入度。若图中有环，某些顶点入度永远不会为 0，因此拓扑排序也可用于环检测。要能模拟任何一种方法，并在存在多个合法顺序时识别出有效的拓扑排序。

In IB and AQA assessments, candidates often face tasks like: “Give a topological ordering of the following DAG” or “Explain why a graph cannot have a topological order.” Make sure you can justify the absence of a topological order by identifying a cycle.

在 IB 和 AQA 考核中，考生常会面对诸如“给出下列 DAG 的一个拓扑顺序”或“解释为何某图不能有拓扑排序”等题目。务必能通过找出环来论证为何无法实现拓扑排序。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

IB AQA Computer Science: Graph Algorithms – Key Exam Points | IB AQA 计算机：图算法考点精讲