Graph Algorithms for A-Level CCEA Computer Science | A-Level CCEA 计算机：图算法考点精讲

📚 Graph Algorithms for A-Level CCEA Computer Science | A-Level CCEA 计算机：图算法考点精讲

Graph algorithms are a cornerstone of A-Level CCEA Computer Science, underpinning everything from social networks to satellite navigation. Mastery requires understanding both the abstract representations of graphs and the step‑by‑step procedures that solve real‑world problems – including depth‑first and breadth‑first traversals, shortest‑path calculations, and minimum spanning tree constructions. This article breaks down each essential algorithm, explains typical exam scenarios, and clarifies common misconceptions, all tailored to the CCEA specification.

图算法是 CCEA A-Level 计算机科学的核心内容，支撑着从社交网络到卫星导航的各种应用。掌握这一模块需要同时理解图的抽象表示方式，以及解决实际问题的分步算法流程——包括深度优先与广度优先遍历、最短路径计算和最小生成树构造。本文逐一拆解每个必考算法，解析典型考题情景，并澄清常见误解，内容完全紧扣 CCEA 考纲要求。

1. Fundamentals of Graph Representation | 图的基本表示方法

A graph G = (V, E) consists of a set of vertices V and a set of edges E. In the CCEA exam you must be able to represent a graph using an adjacency matrix, an adjacency list, and (less frequently) an edge list. An adjacency matrix uses a 2D Boolean or integer array where the cell at row i, column j indicates the presence (and possibly weight) of an edge. An adjacency list stores each vertex together with a collection of its neighbours, typically implemented as an array of linked lists or dynamic arrays.

图 G = (V, E) 由顶点集 V 和边集 E 组成。在 CCEA 考试中，你需要掌握用邻接矩阵、邻接表以及（较少见的）边列表来表示图。邻接矩阵使用二维布尔或整数数组，第 i 行第 j 列的单元格表示是否存在一条边（以及可能的权重）。邻接表则将每个顶点与其邻居集合一起存储，通常以链表或动态数组的数组形式实现。

Adjacency matrix: Fast edge lookup O(1), but memory O(V²); best for dense graphs. 邻接矩阵： 边查询速度快 O(1)，但内存占用 O(V²)；适合稠密图。
Adjacency list: Memory efficient O(V+E), slower lookup O(degree); ideal for sparse graphs. 邻接表： 内存效率高 O(V+E)，查询较慢 O(degree)；适合稀疏图。

CCEA questions often ask you to draw these structures from a given graph or to compare their efficiency for particular algorithms. You should also be comfortable with directed, undirected, weighted, and unweighted graphs.

CCEA 试题经常要求根据给定图画出这些结构，或比较它们在特定算法中的效率。此外，你还需熟悉有向图、无向图、带权图和非带权图。

2. Depth‑First Search (DFS) – Recursive and Stack‑Based | 深度优先搜索 (DFS) – 递归与栈实现

Depth‑first search explores as far as possible along each branch before backtracking. It can be implemented recursively (where the call stack handles backtracking) or iteratively using an explicit stack. Starting at the source node, DFS marks the node as visited, then recursively visits each unvisited neighbour. The order of traversal produces a DFS tree, and the finishing times can be used for topological sorting (see later section).

深度优先搜索会沿每一个分支尽可能深入，再回溯。它可以用递归实现（由调用栈负责回溯），也可以使用显式的栈进行迭代。从起始节点出发，DFS 将该节点标记为已访问，然后递归访问每一个未访问的邻居。遍历顺序产生一棵 DFS 树，其完成时间可用于拓扑排序（见后续章节）。

The CCEA syllabus expects you to be able to simulate DFS on a given graph, showing the order in which nodes are visited and recording the stack/recursion depth. You must also understand its time complexity O(V+E) when an adjacency list is used, since every vertex and edge is processed once.

CCEA 考纲要求你能够在给定图上模拟 DFS，展示节点访问顺序，并记录栈状态或递归深度。你还必须理解，采用邻接表时其时间复杂度为 O(V+E)，因为每个顶点和每条边都会处理一次。

Key exam tip: Watch out for disconnected graphs – if the graph has multiple components, you need to restart DFS from any unvisited vertex to ensure all nodes are processed.

考试要点：留意非连通图——如果图存在多个连通分量，你需要从任意未访问的顶点重新启动 DFS，以确保所有节点都被处理。

3. Breadth‑First Search (BFS) and the Queue | 广度优先搜索 (BFS) 与队列

BFS explores all neighbours of the current vertex before moving to the next level. It uses a queue to store vertices awaiting processing. Starting from the source, BFS enqueues the starting node, marks it visited, then repeatedly dequeues a vertex, examines each unvisited neighbour, and enqueues them. This process layers the graph into levels based on distance from the source.

广度优先搜索在移到下一层之前，先探索当前顶点的所有邻居。它使用一个队列来存储等待处理的顶点。从源点出发，BFS 将起始节点入队并标记为已访问，然后反复从队列取出一个顶点，检查其每个未访问的邻居，并将它们入队。这一过程根据距离源点的远近将图分层。

BFS is the algorithm of choice for finding the shortest path in an unweighted graph because it visits vertices in order of increasing distance. In the CCEA exam you may be asked to list the BFS traversal order, reconstruct the shortest path by maintaining predecessor pointers, or discuss applications such as web crawling and social network “friends of friends” queries.

BFS 是在非带权图中寻找最短路径的首选算法，因为它按距离递增的顺序访问顶点。在 CCEA 考试中，你可能需要列出 BFS 遍历顺序，通过维护前驱指针重建最短路径，或者讨论如网络爬虫和社交网络“朋友的朋友”查询等应用。

Time complexity is again O(V+E) with an adjacency list. BFS requires O(V) memory in the worst case for the queue, which is worth noting in constrained‑memory scenarios.

时间复杂度同样是 O(V+E)（邻接表）。BFS 在最坏情况下队列的内存开销为 O(V)，这在内存受限情景中值得注意。

4. Dijkstra’s Algorithm – Single‑Source Shortest Paths in Weighted Graphs | Dijkstra 算法 – 加权图的单源最短路径

When edges carry non‑negative weights, Dijkstra’s algorithm finds the shortest path from a start vertex to all other vertices. It maintains a priority queue of unvisited vertices based on their current shortest distance estimate. Initially, the source distance is 0 and all others are ∞. At each step, the vertex with the smallest tentative distance is extracted, and for each of its neighbours, the algorithm relaxes the edge – that is, it updates the neighbour’s distance if going through the current vertex offers a shorter path.

当边具有非负权重时，Dijkstra 算法可以找到从起始顶点到所有其他顶点的最短路径。它根据当前的最短距离估计维护一个未访问顶点的优先级队列。初始时，源点距离为 0，其余为 ∞。每一步提取拥有最小试探距离的顶点，并对其每个邻居进行边松弛——即如果经过当前顶点得到更短路径，就更新邻居的距离。

CCEA candidates must be able to trace Dijkstra’s algorithm manually on a small graph (typically in a table showing iteration number, selected vertex, updated distances, and predecessors). You must state clearly that the algorithm requires all edge weights to be non‑negative; a negative weight can cause an incorrect permanent label to be assigned.

CCEA 考生必须能够在小型图上手动追踪 Dijkstra 算法（通常以表格形式展示迭代次数、选中的顶点、更新后的距离和前驱节点）。你必须明确指出该算法要求所有边权重非负；负权重可能导致永久标签被错误指定。

The naive implementation without a priority queue runs in O(V²). With a binary heap, the complexity improves to O((V+E) log V). Which implementation you analyse may depend on the graph density, a nuance examiners occasionally probe.

未采用优先级队列的简单实现复杂度为 O(V²)。使用二叉堆可将复杂度提升至 O((V+E) log V)。分析哪种实现方式取决于图的稀疏程度，这是考官偶尔会考查的细微之处。

5. A* Search – Heuristic Enhancement of Dijkstra | A* 搜索 – Dijkstra 的启发式增强

The A* algorithm extends Dijkstra by incorporating a heuristic function h(n) that estimates the cost from a node n to the goal. It visits nodes in order of f(n) = g(n) + h(n), where g(n) is the exact cost from the start to n. If the heuristic is admissible (never overestimates) and consistent, A* guarantees an optimal path while typically expanding far fewer nodes than Dijkstra, making it indispensable in game AI and route planners.

A* 算法通过引入启发式函数 h(n) 来扩展 Dijkstra 算法，h(n) 估算从节点 n 到目标的代价。它按 f(n) = g(n) + h(n) 的顺序访问节点，其中 g(n) 是从起点到 n 的实际代价。如果启发式函数是可接受的（不高估）且一致的，A* 能保证最优路径，并且通常比 Dijkstra 展开的节点少得多，因此在游戏 AI 和路径规划器中不可或缺。

CCEA may not require you to code A*, but you need to compare it with Dijkstra, explain the role of the heuristic, and trace a simple example (e.g., a grid with Manhattan distance as heuristic). Understanding why a bad heuristic (e.g., constant zero) degrades A* to Dijkstra is a classic discussion point.

CCEA 可能不要求你编写 A* 代码，但你需要将其与 Dijkstra 进行比较，解释启发式函数的作用，并追踪一个简单示例（例如在网格中使用曼哈顿距离作为启发函数）。理解为什么一个糟糕的启发函数（如恒为零）会使 A* 退化成 Dijkstra，是一个经典的讨论点。

6. Minimum Spanning Trees – Prim’s Algorithm | 最小生成树 – Prim 算法

A minimum spanning tree (MST) of a weighted, connected, undirected graph spans all vertices with the minimum possible total edge weight. Prim’s algorithm builds the MST incrementally, starting from an arbitrary vertex. It maintains a set of visited vertices and repeatedly picks the cheapest edge that connects a visited vertex to an unvisited one, adding that edge and the new vertex to the tree.

加权连通无向图的最小生成树 (MST) 以最小总边权连接所有顶点。Prim 算法从任意顶点开始逐步构建 MST。它维护一个已访问顶点集合，并反复选取连接已访问顶点与未访问顶点的最小代价边，将该边和新顶点加入树中。

You must be able to demonstrate Prim’s algorithm step by step, often by maintaining a distance table that tracks the minimal‑weight edge connecting each unvisited vertex to the current tree. The algorithm is greedy: it always chooses the local optimum, but this globally yields an MST. Prim’s runs in O(V²) when implemented with a simple array, or O(E log V) with a priority queue – similar to Dijkstra’s performance profile.

你必须能逐步演示 Prim 算法，通常采用一个距离表，记录每个未访问顶点与当前树连接的最小权重边。该算法是贪心的：它总是选择局部最优解，但最终能全局生成 MST。用简单数组实现时，Prim 算法复杂度为 O(V²)；用优先队列则为 O(E log V)——与 Dijkstra 的性能特征相似。

7. Minimum Spanning Trees – Kruskal’s Algorithm | 最小生成树 – Kruskal 算法

Kruskal’s algorithm takes a different approach: it sorts all edges by weight, then considers them in ascending order, adding an edge to the MST if it does not form a cycle. Cycle detection is handled by a disjoint‑set (union‑find) data structure. The algorithm stops when V‑1 edges have been added.

Kruskal 算法采取不同思路：它按权重排序所有边，然后按升序考虑每条边，如果该边不形成环路，就加入 MST。环路检测由不相交集合（并查集）数据结构处理。算法在选择了 V‑1 条边后停止。

CCEA examinations frequently ask you to trace Kruskal’s on a given graph, showing edge selection and the evolving union‑find states. You should contrast it with Prim’s: Kruskal’s works well for sparse graphs where sorting edges is fast, but it requires an efficient union‑find. The time complexity is O(E log E) or O(E log V), dominated by sorting.

CCEA 考试经常要求追踪给定图上的 Kruskal 算法，展示边的选择以及并查集状态的演变。你应该将它与 Prim 进行对比：Kruskal 在边排序开销较小的稀疏图上表现良好，但需要高效的并查集。时间复杂度为 O(E log E) 或 O(E log V)，排序占据主导。

A common pitfall is forgetting to stop after V‑1 edges, or misapplying Kruskal to a directed graph – it only applies to undirected MST problems.

一个常见陷阱是选择了 V‑1 条边后忘记停止，或将 Kruskal 误用于有向图——它只适用于无向图的 MST 问题。

8. Topological Sort – Ordering Dependencies | 拓扑排序 – 依赖关系排序

A topological ordering of a directed acyclic graph (DAG) is a linear sequence of vertices such that for every directed edge (u → v), u appears before v. This is vital in build systems, course prerequisite chains, and task scheduling. Two classic algorithms exist: Kahn’s algorithm (based on in‑degree) and DFS‑based topological sort.

有向无环图 (DAG) 的拓扑排序是一种顶点的线性序列，使得对于每条有向边 (u → v)，u 出现在 v 之前。这在构建系统、课程前置关系链和任务调度中至关重要。存在两种经典算法：基于入度的 Kahn 算法和基于 DFS 的拓扑排序。

Kahn’s algorithm: Compute the in‑degree of each vertex; repeatedly remove a vertex with in‑degree 0, append it to the ordering, and decrement the in‑degree of its neighbours. If the ordering contains all vertices, a topological sort exists; otherwise the graph contains a cycle.

Kahn 算法：计算每个顶点的入度；反复移除一个入度为 0 的顶点，将其追加到排序结果中，并使其邻居入度减 1。若排序包含所有顶点，则存在拓扑排序；否则图中含有环。

DFS‑based approach: Perform a DFS, and as each vertex finishes (after exploring all descendants), push it onto a stack. Reversing the stack order gives a topological sort. This method naturally detects back edges, which indicate cycles.

基于 DFS 的方法：执行 DFS，每当一个顶点完成（即所有后代探索完毕）时，将其压入栈中。反转栈中顺序即得拓扑排序。该方法天然能够检测表示存在环路的回边。

CCEA questions often present a dependency table and ask you to produce a valid topological order, identify multiple possible orders, or explain why a cycle prevents ordering. Time complexity: O(V+E).

CCEA 试题经常给出一个依赖关系表，要求你生成一个有效的拓扑顺序，识别可能的多重顺序，或解释为什么环路会阻止排序。时间复杂度：O(V+E)。

9. Shortest Path on DAGs and Dynamic Programming Connection | DAG 上的最短路径与动态规划联系

When a graph is a DAG, shortest (and longest) paths can be found in O(V+E) time by processing vertices in topological order. Because there are no cycles, relaxing edges in this order guarantees that by the time you process a vertex, all paths leading to it have been considered. This is far more efficient than Dijkstra’s and requires no priority queue.

当图是一个 DAG 时，可按拓扑顺序在 O(V+E) 时间内找到最短（及最长）路径。由于不存在环路，按此顺序进行边松弛可以保证，处理某个顶点时，所有到达它的路径都已被考虑。这比 Dijkstra 更高效，且无需优先队列。

This technique also highlights the strong link between graph algorithms and dynamic programming: the topologically sorted DAG ensures optimal substructure, allowing memoisation of distances. CCEA papers sometimes feature crossover questions where you need to interpret a scheduling problem as a DAG shortest‑path problem.

这一技术也突显了图算法与动态规划的紧密联系：拓扑排序后的 DAG 确保了最优子结构，从而可以对距离进行记忆化存储。CCEA 试卷有时会出现交叉题型，要求你将一个调度问题解释为 DAG 上的最短路径问题。

10. Graph Traversal Applications and Exam Scenarios | 图遍历的应用与考试情景

CCEA assessments commonly embed graph algorithms in practical contexts: a maze as a graph (cells = vertices, passages = edges), a computer network with routers and links, or a revision timetable where topics have prerequisites. For each scenario, identify the most appropriate algorithm – BFS for shortest hop count, DFS for connectivity or cycle detection, Dijkstra/A* for weighted shortest paths, topological sort for valid ordering, and MST for least‑cost connectivity (e.g., laying cables).

CCEA 的评估常将图算法融入实际情境中：迷宫表示为一个图（格子为顶点，通道为边），带有路由器和链路的计算机网络，或带有前置要求的学习计划表。对于每种情境，要识别最合适的算法——BFS 用于最短跳数，DFS 用于连通性或环路检测，Dijkstra/A* 用于加权最短路径，拓扑排序用于有效顺序安排，MST 用于最低成本连通（例如铺设线缆）。

When justifying your choice, discuss complexity, constraints (weights, direction, acyclicity), and memory requirements. A well‑reasoned comparison can turn an average answer into a top‑mark response.

在论证你的选择时，要讨论复杂度、约束条件（权重、方向、无环性）和内存需求。有充分理由的比较能将普通答案转变为高分回答。

Be prepared to produce pseudo‑code or to evaluate given pseudo‑code for correctness. Bugs often involve incorrect visited handling, missing cycle checks, or inappropriate data structures.

要做好准备写出伪代码，或评估给定伪代码的正确性。Bug 通常涉及错误的访问标记处理、缺失的环路检查，或不合适的数据结构。

11. Comparing Algorithms – When and Why | 算法比较 – 何时使用与为何使用

Algorithm 算法	Best for 最适合	Limitations 限制	Complexity 复杂度
BFS	Unweighted shortest path / level order 非带权最短路径 / 层次遍历	Queue memory O(V); cannot handle weights 队列内存 O(V)；不能处理权重	O(V+E)
DFS	Connectivity, cycle detection, topological sorting 连通性、环路检测、拓扑排序	No shortest‑path guarantee; recursion depth 不保证最短路径；递归深度限制	O(V+E)
Dijkstra	Weighted non‑negative graphs 非负权图	Fails with negative edges; slower than BFS 存在负边时失败；比 BFS 慢	O((V+E) log V)
A*	Goal‑directed search with heuristic 带启发式函数的目标导向搜索	Needs an admissible heuristic; memory heavy 需要可接受的启发函数；内存开销大	Depends on heuristic 取决于启发函数
Prim / Kruskal	Minimum spanning tree 最小生成树	Only for undirected graphs; not for pathfinding 仅适用于无向图；不能用于寻路	O(E log V) / O(E log E)

This comparative table is a powerful revision tool. Internalise the conditions and trade‑offs, and you will be able to answer those high‑mark “evaluate” questions with confidence.

这张对比表是强大的复习工具。将条件和权衡内化于心，你就能自信地回答那些高分“评估”类问题。

12. Exam Traps and How to Avoid Them | 考试陷阱与避坑指南

Confusing BFS queue with DFS stack: BFS uses FIFO queue, DFS uses LIFO stack (or recursion). Mixing them up produces incorrect traversal orders. 混淆 BFS 队列与 DFS 栈： BFS 用先进先出队列，DFS 用后进先出栈（或递归）。搞混会导致错误的遍历顺序。
Applying Dijkstra with a negative edge: Marking a vertex permanently after extraction can cause a wrong shortest path. Know the example of the triangle with one negative edge. 在含负边的图上使用 Dijkstra： 在提取顶点后将其永久标记可能导致错误的最短路径。要熟记含一条负边的三角形反例。
Forgetting to reset visited flags in multi‑component algorithms: DFS/BFS loops must iterate over all vertices, restarting when an unvisited vertex is found. 在多分量算法中忘记重置访问标记： DFS/BFS 循环必须遍历所有顶点，发现未访问顶点时重新启动。
Stopping Kruskal’s too late or too early: Stop exactly when the MST has V‑1 edges. Continuing may add unnecessary edges and signals misunderstanding. Kruskal 算法停止过早或过迟： 恰在 MST 拥有 V‑1 条边时停止。继续添加边表示理解有误。
Ignoring data structure efficiency: A theoretical O(E log V) may be slower than O(V²) for tiny graphs; exam comments on constant factors can demonstrate deeper insight. 忽略数据结构的效率： 对于微小图，理论上的 O(E log V) 可能比 O(V²) 更慢；在试卷上点评常数因子的影响能展示更深的理解。

Practice step‑wise tracing with text‑book examples until the mechanics become second nature. The CCEA exam rewards precision, not just high‑level description.

用教科书示例反复练习分步追踪，直到操作步骤成为本能。CCEA 考试奖励的是精确性，而不仅仅是高层次描述。

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

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

Graph Algorithms for A-Level CCEA Computer Science | A-Level CCEA 计算机：图算法 考点精讲