A-Level Edexcel Computer Science: Graph Algorithms In-Depth Revision

📚 A-Level Edexcel Computer Science: Graph Algorithms In-Depth Revision | 图算法考点精讲

Graph algorithms are a core component of the Edexcel A-Level Computer Science specification. Whether you’re dealing with network routing, dependency resolution, or social graph analysis, a solid grasp of graph representations, traversal techniques, and shortest-path methods is essential. This revision guide walks you through adjacency structures, BFS, DFS, Dijkstra’s algorithm, and crucial exam tips, with worked examples and clear step-by-step traces to help you ace Paper 1.

图算法是 Edexcel A-Level 计算机科学大纲的核心内容。无论是网络路由、依赖关系解析还是社交图谱分析，牢固掌握图的表示、遍历技术和最短路径方法都至关重要。本篇复习指南带你系统梳理邻接结构、BFS、DFS、Dijkstra 算法及重要应试技巧，配有详细示例和清晰的逐步跟踪过程，助你在 Paper 1 中斩获高分。

1. Graph Fundamentals | 图的基本概念

A graph consists of vertices (or nodes) and edges that connect pairs of vertices. Edges can be directed (one-way) or undirected (two-way), and may carry weights representing cost, distance, or capacity. Understanding these properties is the first step toward applying the correct algorithm.

图由顶点（节点）以及连接顶点的边组成。边可以是有向（单向）或无向（双向）的，并且可以带有权重，表示代价、距离或容量。理解这些属性是正确应用算法的第一步。

Common exam examples include road networks (weighted, undirected), web links (directed, unweighted), and task dependency graphs (directed, acyclic). You should be able to identify the type of graph from a problem description.

考试中常见的例子包括路网（加权、无向）、网页链接（有向、无权重）以及任务依赖图（有向、无环）。你需要能够根据问题描述识别图的类型。

2. Adjacency Matrix Representation | 邻接矩阵表示法

An adjacency matrix uses a 2D array where the cell at row i, column j stores the weight of the edge from vertex i to vertex j (or 0 / ∞ if no edge exists). For an unweighted graph, it stores 1 for an edge and 0 for no edge.

邻接矩阵使用二维数组，其中第 i 行第 j 列的单元格存储顶点 i 到顶点 j 的边权重（若无边则存 0 或 ∞）。对于无权图，有边存 1，无边存 0。

This representation allows O(1) edge lookups but consumes O(n²) space, making it suitable for dense graphs. Symmetry occurs for undirected graphs.

这种表示法支持 O(1) 的边查询，但占用 O(n²) 空间，适合稠密图。无向图的矩阵是对称的。

Vertex	A	B	C
A	0	4	2
B	4	0	1
C	2	1	0

Example: A weighted undirected graph with vertices A, B, C and edges A–B (4), A–C (2), B–C (1).

示例：一个加权无向图，顶点为 A、B、C，边为 A–B (4)、A–C (2)、B–C (1)。

3. Adjacency List Representation | 邻接表表示法

An adjacency list stores an array of linked lists (or dynamic arrays), where each vertex has a list of its adjacent vertices and corresponding edge weights.

邻接表存储一个链表（或动态数组）的数组，每个顶点对应一个链表，记录其相邻顶点及相应的边权重。

This uses O(V + E) space, making it memory-efficient for sparse graphs. Traversing all neighbours of a vertex is fast, although edge existence checks take O(degree) time.

这种表示法使用 O(V + E) 空间，对于稀疏图非常高效。遍历一个顶点的所有邻居很快，但检查边是否存在需要 O(degree) 时间。

A -> (B, 4) -> (C, 2)
B -> (A, 4) -> (C, 1)
C -> (A, 2) -> (B, 1)

In exams, you may be asked to draw either representation from a given graph or to compare their suitability for different tasks.

考试中可能要求你根据给定图画出其中一种表示，或比较它们在不同任务中的适用性。

4. Breadth-First Search (BFS) Concept | 广度优先搜索 (BFS) 概念

BFS explores a graph level by level, starting from a source vertex. It uses a queue to keep track of vertices to visit next, ensuring vertices are processed in order of increasing distance from the source.

BFS 从源顶点开始，逐层探索图。它使用一个队列记录接下来要访问的顶点，确保按照与源顶点的距离递增的顺序处理顶点。

It is typically used to find the shortest path in unweighted graphs or to discover all reachable vertices. BFS also forms the basis for many graph-based puzzles and web crawlers.

BFS 通常用于在无权图中寻找最短路径，或发现所有可达顶点。它还是许多基于图的谜题和网络爬虫的基础。

5. BFS Step-by-Step Trace | BFS 逐步跟踪

Consider an unweighted graph: A connected to B and C; B connected to D; C connected to D and E. Starting BFS at A:

考虑一个无权图：A 连接 B 和 C；B 连接 D；C 连接 D 和 E。从 A 开始 BFS：

Step 1: Enqueue A, mark A visited. Queue: [A].

步骤 1: A 入队，标记 A 已访问。队列: [A]。

Step 2: Dequeue A, enqueue its unvisited neighbours B and C. Queue: [B, C]. Order: A.

步骤 2: A 出队，将其未访问邻居 B、C 入队。队列: [B, C]。访问顺序: A。

Step 3: Dequeue B, enqueue its unvisited neighbour D. Queue: [C, D]. Order: A, B.

步骤 3: B 出队，将其未访问邻居 D 入队。队列: [C, D]。访问顺序: A, B。

Step 4: Dequeue C, enqueue E (D already visited). Queue: [D, E]. Order: A, B, C.

步骤 4: C 出队，将 E 入队（D 已访问）。队列: [D, E]。访问顺序: A, B, C。

Step 5: Dequeue D, no unvisited neighbours. Queue: [E]. Order: A, B, C, D.

步骤 5: D 出队，无未访问邻居。队列: [E]。访问顺序: A, B, C, D。

Step 6: Dequeue E, no unvisited neighbours. Queue: []. Order: A, B, C, D, E. Complete.

步骤 6: E 出队，无未访问邻居。队列: []。访问顺序: A, B, C, D, E。完成。

The visited order also gives the shortest path lengths (in edges) from A: A–0, B–1, C–1, D–2, E–2.

访问顺序也给出了从 A 出发的最短路径长度（以边数计）：A–0, B–1, C–1, D–2, E–2。

6. Depth-First Search (DFS) Concept | 深度优先搜索 (DFS) 概念

DFS plunges deep into a graph by following one branch as far as possible before backtracking. It uses a stack (explicitly or via recursion) to remember the path and discovers vertices along a single path before popping back.

DFS 沿着一条分支尽可能深入，直到无法继续再回溯。它使用栈（显式或通过递归）来记忆路径，在弹回之前沿着单一路径发现顶点。

DFS is commonly applied in maze solving, cycle detection, topological ordering (in directed acyclic graphs), and strongly connected component identification.

DFS 常用于迷宫求解、环路检测、拓扑排序（有向无环图）和强连通分量识别。

7. DFS Step-by-Step Trace | DFS 逐步跟踪

Using the same graph, start DFS at A (using a stack):

使用同一个图，从 A 开始 DFS（使用栈）：

Push A. Stack: [A]. Pop A, mark visited, push its neighbours C then B (order affects result). Stack: [C, B]. Order: A.

A 入栈。栈: [A]。弹出 A，标记已访问，将其邻居 C 和 B 入栈（顺序会影响结果）。栈: [C, B]。访问顺序: A。

Pop B, mark visited, push D. Stack: [C, D]. Order: A, B.

弹出 B，标记已访问，将 D 入栈。栈: [C, D]。访问顺序: A, B。

Pop D, mark visited, no unvisited neighbours. Stack: [C]. Order: A, B, D.

弹出 D，标记已访问，无未访问邻居。栈: [C]。访问顺序: A, B, D。

Pop C, mark visited, push E (D already visited). Stack: [E]. Order: A, B, D, C.

弹出 C，标记已访问，将 E 入栈（D 已访问）。栈: [E]。访问顺序: A, B, D, C。

Pop E, mark visited. Stack: []. Order: A, B, D, C, E.

弹出 E，标记已访问。栈: []。访问顺序: A, B, D, C, E。

DFS order depends on the order neighbours are pushed. Both BFS and DFS must mark visited vertices to avoid infinite loops.

DFS 的访问顺序取决于邻居入栈的顺序。BFS 和 DFS 都必须标记已访问顶点，以避免无限循环。

8. Dijkstra’s Algorithm: Shortest Path in Weighted Graphs | Dijkstra 算法：加权图最短路径

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. It greedily selects the unvisited vertex with the smallest tentative distance, updates its neighbours, and repeats until all vertices are visited.

Dijkstra 算法在边权重非负的图中，寻找从源顶点到所有其他顶点的最短路径。它贪心地选择未访问顶点中暂定距离最小的一个，更新其邻居，重复直到所有顶点都被访问。

Key data structures: a distance array (initialised to ∞ for all except source, which is 0) and a visited set or priority queue to track the next current vertex.

关键数据结构：距离数组（除源顶点为 0 外，其余初始化为 ∞）以及一个已访问集合或优先队列，用于跟踪下一个当前顶点。

A common exam task is to manually trace Dijkstra on a small graph and produce the final shortest-path tree or distances.

常见的考试任务是手动在一个小图上跟踪 Dijkstra 算法，并得出最终的最短路径树或距离。

9. Dijkstra Tracing Example | Dijkstra 实例跟踪

Consider a weighted graph: vertices A, B, C, D, E. Edges: A–B (6), A–C (2), B–D (1), C–B (3), C–D (5), D–E (2), B–E (7). Source: A.

考虑一个加权图：顶点 A、B、C、D、E。边：A–B (6), A–C (2), B–D (1), C–B (3), C–D (5), D–E (2), B–E (7)。源顶点：A。

Initial distances: d(A)=0, d(B)=∞, d(C)=∞, d(D)=∞, d(E)=∞. Unvisited: all.

初始距离：d(A)=0, d(B)=∞, d(C)=∞, d(D)=∞, d(E)=∞。未访问集合：全部。

Select A (distance 0). Update neighbours: B via A=6 → d(B)=6; C via A=2 → d(C)=2.

选择 A（距离 0）。更新邻居：B 经 A=6 → d(B)=6；C 经 A=2 → d(C)=2。

Mark A visited. Smallest unvisited distance is C (2). Select C. Update neighbours: B via C=2+3=5 (<6) → d(B)=5; D via C=2+5=7 → d(D)=7.

标记 A 已访问。未访问中最小的距离是 C (2)。选择 C。更新邻居：B 经 C=2+3=5 (<6) → d(B)=5；D 经 C=2+5=7 → d(D)=7。

Mark C visited. Smallest unvisited distance is B (5). Select B. Update neighbours: D via B=5+1=6 (<7) → d(D)=6; E via B=5+7=12 → d(E)=12.

标记 C 已访问。未访问中最小的距离是 B (5)。选择 B。更新邻居：D 经 B=5+1=6 (<7) → d(D)=6；E 经 B=5+7=12 → d(E)=12。

Mark B visited. Smallest unvisited distance is D (6). Select D. Update neighbour E: via D=6+2=8 (<12) → d(E)=8.

标记 B 已访问。未访问中最小的距离是 D (6)。选择 D。更新邻居 E：经 D=6+2=8 (<12) → d(E)=8。

Mark D visited. Next smallest is E (8). Select E, no updates. Mark E visited. Final distances: A=0, B=5, C=2, D=6, E=8. Shortest path to E: A→C→B→D→E (2+3+1+2=8).

标记 D 已访问。下一个最小的是 E (8)。选择 E，无更新。标记 E 已访问。最终距离：A=0, B=5, C=2, D=6, E=8。到 E 的最短路径：A→C→B→D→E (2+3+1+2=8)。

10. Why Negative Weights Break Dijkstra | 负权重为何破坏 Dijkstra 算法

Dijkstra assumes that once a vertex is marked visited, its shortest distance is final. With negative edge weights, a later path could reduce the distance to an already visited vertex, breaking the greedy property. The algorithm may produce incorrect results in such graphs.

Dijkstra 假设一旦顶点标记为已访问，其最短距离就是最终值。如果存在负权重的边，后续路径可能会减少已访问顶点的距离，从而破坏贪心性质。在这种图上，算法可能得出错误结果。

For graphs with negative edges, the Bellman-Ford algorithm should be used, but that is beyond the scope of the Edexcel A-Level specification. You only need to know that Dijkstra requires non-negative weights.

对于带负边的图，应使用 Bellman-Ford 算法，但这超出了 Edexcel A-Level 大纲的范围。你只需知道 Dijkstra 要求权重非负即可。

11. Comparing BFS, DFS and Dijkstra | BFS、DFS 与 Dijkstra 对比

BFS uses a queue and finds the shortest path in terms of edge count (unweighted graphs). DFS uses a stack and is not suitable for shortest path; it is used for exploration and ordering. Dijkstra uses a priority concept (min-distance) and finds the shortest path for weighted graphs with non-negative edges.

BFS 使用队列，按边数寻找最短路径（无权图）。DFS 使用栈，不适合最短路径；它用于探索和排序。Dijkstra 使用优先级概念（最小距离），在带非负权重的图中寻找最短路径。

Algorithm	Data Structure	Weighted?	Shortest Path?
BFS	Queue	No (ignores weights)	Yes (unweighted)
DFS	Stack / recursion	No	No
Dijkstra	Min-priority queue	Yes (non-negative)	Yes (weighted)

In exams, you may be asked to justify which algorithm to use for a given problem context or to trace each on a provided graph.

考试中，你可能需要根据给定问题情境说明选用哪种算法，或在提供的图上对每种算法进行跟踪。

12. Exam Tips and Common Pitfalls | 应试技巧与常见误区

Always distinguish between directed and undirected edges when drawing or analysing a graph. A common mistake is applying Dijkstra to a graph with negative weights, or forgetting to update distances when a shorter path is found during tracing.

在绘制或分析图时，务必区分有向边和无向边。常见错误包括：对含负权重的图使用 Dijkstra，或在跟踪时发现更短路径却忘记更新距离。

When tracing BFS/DFS, maintain a clear visit order and a record of the queue or stack content at each step. For Dijkstra, create a neat table with columns: Vertex, Shortest distance from source, Previous vertex, and Visited status.

跟踪 BFS/DFS 时，要清晰地记录访问顺序，以及每一步队列或栈的内容。对于 Dijkstra，最好制作一个整洁的表格，包括列：顶点、从源顶点的最短距离、前驱顶点、已访问状态。

Practice with past paper questions is essential. Edexcel often asks for algorithm traces showing every stage, so your working must be methodical and easily readable by an examiner.

练习往年真题至关重要。Edexcel 考试经常要求展示算法跟踪的每一个阶段，因此你的解答必须条理清晰，易于阅卷人阅读。

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

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

A-Level Edexcel Computer Science: Graph Algorithms In-Depth Revision | 图算法考点精讲