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

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

Graph algorithms form a cornerstone of the Cambridge International A-Level Computer Science syllabus. They underpin important concepts in data structures, problem-solving, and artificial intelligence. This article offers a detailed breakdown of the essential graph algorithms you must master for the CIE exam, including representations, traversal techniques, shortest path methods, and heuristic search.

图算法是剑桥国际A-Level计算机科学大纲的基石。它们支撑着数据结构、问题解决和人工智能中的重要概念。本文详细分解了CIE考试中必须掌握的核心图算法，涵盖图的表示、遍历技术、最短路径方法以及启发式搜索。

1. Understanding Graphs and Their Representations | 理解图及其表示方法

A graph is an abstract data type consisting of vertices (nodes) and edges connecting them. Graphs can be directed or undirected, weighted or unweighted. Choosing the right representation impacts memory usage and algorithm efficiency.

图是一种抽象数据类型，由顶点（节点）和连接它们的边组成。图可以是有向或无向的，带权或不带权的。选择合适的表示方法会影响内存使用和算法效率。

• The adjacency matrix is a 2D array of size V × V where entry [i][j] stores 1 (or the edge weight) if an edge exists, otherwise 0. It allows O(1) lookup for edge existence but uses O(V²) space.

  邻接矩阵是一个 V×V 的二维数组，如果存在边则项 [i][j] 存储 1（或边的权重），否则为 0。它允许 O(1) 时间查询边是否存在，但占用 O(V²) 空间。

• The adjacency list uses an array of linked lists or dynamic arrays. Each vertex has a list of its adjacent vertices. Space complexity is O(V+E), making it efficient for sparse graphs.

  邻接表使用链表或动态数组构成的数组。每个顶点都有一个保存其相邻顶点的列表。空间复杂度为 O(V+E)，对稀疏图非常高效。

• Weighted graphs store the weight alongside the neighbour in adjacency lists or in the matrix cell.

  带权图在邻接表中将权重与邻居一同存储，或在矩阵单元中存储权重。

Aspect | 方面	Adjacency Matrix | 邻接矩阵	Adjacency List | 邻接表
Space | 空间	O(V²)	O(V+E)
Edge query | 边查询	O(1)	O(degree(v))
Best for | 最适合	Dense graphs | 稠密图	Sparse graphs | 稀疏图

---

2. Graph Traversal Algorithms | 图遍历算法

Traversal algorithms systematically visit every vertex and edge in a graph. They are fundamental to many real-world applications like web crawling, network analysis, and puzzle solving. The CIE exam focuses on two principal methods: Depth-First Search (DFS) and Breadth-First Search (BFS).

遍历算法系统地访问图中的每个顶点和边。它们是许多实际应用的基础，例如网页爬取、网络分析和谜题求解。CIE 考试重点考察两种主要方法：深度优先搜索（DFS）和广度优先搜索（BFS）。

Both algorithms use a Boolean array to track visited nodes, ensuring each node is processed exactly once. The core difference lies in the data structure used to manage the fringe (the set of discovered but unprocessed nodes).

两种算法都使用一个布尔数组来跟踪已访问的节点，确保每个节点恰好被处理一次。核心区别在于用于管理边界（已发现但未处理的节点集合）的数据结构。

---

3. Depth-First Search (DFS) in Detail | 深度优先搜索（DFS）详解

DFS explores as far as possible along each branch before backtracking. It uses a stack, either explicitly or implicitly via recursion. The algorithm starts at a chosen vertex, marks it as visited, and recursively visits an unvisited neighbour until no more unvisited neighbours exist, then backtracks.

DFS 在回溯之前尽可能深地探索每个分支。它使用栈，可以是显式的栈或通过递归隐式调用。算法从选定的顶点开始，将其标记为已访问，递归地访问未访问的邻居，直到不再有未访问的邻居，然后回溯。

• Recursive pseudocode: visit(v) → mark v visited → for each neighbour w of v: if not visited, visit(w).

  递归伪代码：visit(v) → 标记 v 已访问 → 对 v 的每个邻居 w：如果未访问，则 visit(w)。

• Iterative version: push start node onto stack → while stack not empty: pop node, if not visited, mark visited and push all unvisited neighbours onto stack.

  迭代版本：将起始节点压入栈 → 当栈不为空：弹出节点，如果未访问，则标记已访问并将所有未访问的邻居压入栈。

• Time complexity is O(V+E) for adjacency lists, O(V²) for adjacency matrix because finding neighbours takes O(V).

  时间复杂度：使用邻接表为 O(V+E)，使用邻接矩阵为 O(V²)，因为查找邻居需要 O(V)。

• DFS produces a depth-first tree and is useful for topological sorting, detecting cycles, and solving mazes.

  DFS 生成一棵深度优先树，适用于拓扑排序、检测环和求解迷宫。

---

4. Breadth-First Search (BFS) in Detail | 广度优先搜索（BFS）详解

BFS explores all neighbours at the present depth level before moving on to nodes at the next depth level. It uses a queue as the fringe structure. BFS finds the shortest path in terms of the number of edges in an unweighted graph.

BFS 在进入下一深度层之前，先探索当前深度层的所有邻居。它使用队列作为边界结构。BFS 可以在无权图中找到以边数衡量的最短路径。

• Algorithm: enqueue start node, mark visited → while queue not empty: dequeue node, for each unvisited neighbour, mark visited and enqueue.

  算法：将起始节点入队，标记已访问 → 当队列不为空：将节点出队，对每个未访问的邻居，标记已访问并入队。

• BFS builds a breadth-first tree where each node’s distance from the source is the minimum number of edges needed to reach it.

  BFS 构建一棵广度优先树，其中每个节点到源节点的距离是到达该节点所需的最少边数。

• Applications include friend recommendation in social networks, peer-to-peer networks, and GPS navigation on unweighted maps.

  应用包括社交网络中的好友推荐、对等网络以及无权地图上的 GPS 导航。

• Complexity is identical to DFS: O(V+E) with adjacency lists, O(V²) with matrix.

  复杂度与 DFS 相同：邻接表为 O(V+E)，邻接矩阵为 O(V²)。

---

5. Comparative Analysis of DFS and BFS | DFS 与 BFS 对比分析

Understanding when to use DFS versus BFS is a common examination requirement. The choice depends on the problem’s nature and the desired tree shape.

理解何时使用 DFS 与 BFS 是考试中的常见要求。选择取决于问题的性质和所需的树形结构。

Property | 属性	DFS	BFS
Fringe structure | 边界结构	Stack (LIFO) | 栈（后进先出）	Queue (FIFO) | 队列（先进先出）
Space complexity | 空间复杂度	O(V) stack depth | O(V) 栈深度	O(V) queue size, potentially large | O(V) 队列大小，可能很大
Path found | 找到的路径	Does not guarantee shortest path | 不保证最短路径	Shortest path (unweighted) | 最短路径（无权）
Use case | 用例	Maze solving, cycle detection | 迷宫求解、环检测	GPS, social networking | GPS、社交网络

In an exam question, carefully read whether you need to explore all vertices, find a specific node, or determine the shortest path (in an unweighted graph). For weighted shortest paths, neither DFS nor BFS suffices — Dijkstra or A* must be used.

在考试题目中，仔细阅读要求是需要探索所有顶点、找到特定节点还是确定最短路径（在无权图中）。对于加权最短路径，DFS 和 BFS 都不够，必须使用 Dijkstra 或 A* 算法。

---

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

Dijkstra’s algorithm computes the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights. It uses a priority queue to always expand the node with the smallest tentative distance.

Dijkstra 算法计算从单个源顶点到图中所有其他顶点的最短路径，适用于具有非负边权的图。它使用优先队列始终扩展具有最小临时距离的节点。

• Initialize all distances to infinity except the source (0). Maintain a min-priority queue of unvisited nodes ordered by current distance.

  将所有距离初始化为无穷大，源节点除外（设为 0）。维护一个按当前距离排序的未访问节点的最小优先队列。

• While the priority queue is not empty: extract the node u with minimum distance. For each neighbour v of u, if distance[u] + weight(u,v) < distance[v], update distance[v] and record u as v's predecessor.

  当优先队列不为空：提取具有最小距离的节点 u。对于 u 的每个邻居 v，如果 distance[u] + weight(u,v) < distance[v]，则更新 distance[v] 并将 u 记为 v 的前驱。

• The algorithm works because once a node is extracted from the priority queue, its distance is final. This holds only when all edge weights are non-negative.

  该算法有效的原因是，一旦一个节点从优先队列中提取出来，它的距离就是最终的。这仅在所有边权为非负时才成立。

---

7. Step-by-Step Execution of Dijkstra’s Algorithm | Dijkstra 算法逐步执行

Consider a graph with vertices A, B, C, D and edges: A-B (4), A-C (2), B-C (1), B-D (5), C-D (8), C-E (10), D-E (2). Source is A.

考虑一个包含顶点 A、B、C、D 的图，边为：A-B (4), A-C (2), B-C (1), B-D (5), C-D (8), C-E (10), D-E (2)。源点为 A。

Step | 步骤	Visited/Current | 已访问/当前	Distances (A,B,C,D,E) | 距离 (A,B,C,D,E)
0	–	(0, ∞, ∞, ∞, ∞)
1	A	(0*, 4, 2, ∞, ∞)
2	C (distance 2)	(0*, 3 via C, 2*, 10, 12)
3	B (distance 3)	(0*, 3*, 2*, 8 via B, 12)
4	D (distance 8)	(0*, 3*, 2*, 8*, 10 via D)
5	E (distance 10)	(0*, 3*, 2*, 8*, 10*)

In exam settings, you may be asked to trace the algorithm step by step, updating a table of distances and predecessor nodes. Practice this with various graphs to ensure speed and accuracy.

在考试环境中，你可能需要逐步跟踪算法，更新距离和前驱节点的表格。通过练习各种图来确保速度和准确性。

---

8. A* Search Algorithm: Heuristics and Efficiency | A* 搜索算法：启发式与效率

A* (A-star) is an informed search algorithm that extends Dijkstra by using a heuristic to guide the search towards the goal. It is widely used in pathfinding for AI, such as in navigation and games.

A*（A星）是一种有信息搜索算法，它通过使用启发式扩展 Dijkstra，以引导搜索朝着目标前进。它广泛用于 AI 中的寻路，例如导航和游戏。

• Each node n is assigned a cost f(n) = g(n) + h(n), where g(n) is the actual cost from start to n, and h(n) is a heuristic estimate of the cost from n to goal.

  每个节点 n 被赋予一个成本 f(n) = g(n) + h(n)，其中 g(n) 是从起点到 n 的实际成本，h(n) 是从 n 到目标的启发式估计成本。

• A* maintains a priority queue ordered by f(n). It expands nodes with the lowest f-value first, similar to Dijkstra but directed.

  A* 维护一个按 f(n) 排序的优先队列。它首先扩展 f 值最小的节点，类似于 Dijkstra 但有方向性。

• The heuristic must be admissible: it must never overestimate the true remaining cost to the goal. This guarantees an optimal shortest path.

  启发式必须是可接受的：它绝不能高估到达目标的真实剩余成本。这保证了最优最短路径。

• A common heuristic for grid-based maps is Manhattan distance (|x₁−x₂| + |y₁−y₂|) or Euclidean distance as appropriate.

  基于网格的地图的常见启发式是曼哈顿距离（|x₁−x₂| + |y₁−y₂|）或适用的欧几里得距离。

---

9. The Role of Heuristics in A* | 启发式在 A* 中的作用

The performance of A* heavily depends on the quality of the heuristic. A heuristic h(n) that exactly equals the true cost makes A* go straight to the goal with no wasted exploration. If h(n) = 0 for all n, A* degenerates to Dijkstra’s algorithm.

A* 的性能在很大程度上取决于启发式的质量。如果启发式 h(n) 恰好等于真实成本，A* 将直接到达目标而没有多余的探索。如果对所有 n 都有 h(n) = 0，A* 就退化为 Dijkstra 算法。

Heuristic type | 启发式类型	Effect on search | 对搜索的影响
h(n) = 0	Uninformed, behaves like Dijkstra | 无信息，行为类似 Dijkstra
Admissible, but small | 可接受但较小	Explores more nodes, still optimal | 探索更多节点，仍最优
Admissible and consistent | 可接受且一致	Optimal with fewer expanded nodes | 最优且扩展节点更少
Overestimating (inadmissible) | 高估（不可接受）	May not find optimal path | 可能找不到最优路径

In exam questions, you could be asked to explain why a heuristic is admissible or to construct a suitable heuristic for a given problem, such as in a 2D maze or routing scenario.

在考试题目中，可能要求你解释为什么某个启发式是可接受的，或者为一个给定问题（如二维迷宫或路由场景）构建一个合适的启发式。

---

10. Implementing Graph Algorithms in Pseudocode | 图算法的伪代码实现

CIE expects you to write and understand high-level pseudocode for these algorithms. Key points include managing visited flags, using appropriate data structures, and properly updating distances or previous nodes.

CIE 期望你能够编写并理解这些算法的高级伪代码。关键点包括管理访问标志、使用适当的数据结构，以及正确地更新距离或前驱节点。

Example pseudocode for Dijkstra:

Dijkstra 伪代码示例：

DIST[S] ← 0
for all other vertices v: DIST[v] ← ∞
PQ ← priority queue of vertices using DIST
while PQ not empty:
u ← extract_min(PQ)
for each neighbour v of u:
if DIST[u] + weight(u,v) < DIST[v]:
DIST[v] ← DIST[u] + weight(u,v)
PREV[v] ← u
update PQ

When implementing BFS, ensure you use a queue and mark nodes as visited when enqueuing to avoid duplicates.

在实现 BFS 时，确保使用队列并在入队时将节点标记为已访问，以避免重复。

---

11. Common Pitfalls and Exam Tips | 常见陷阱与考试技巧

Avoid the mistake of applying Dijkstra to graphs with negative edges. The algorithm assumes that once a node is settled, no shorter path can be found; negative edges violate this property.

避免将 Dijkstra 算法应用于带有负权边的图。该算法假设一旦一个节点被确定，就没有更短的路径可以被找到；负权边会违反这一性质。

• When tracing DFS, show the stack state and visited set clearly to gain full marks.

  在跟踪 DFS 时，清楚地展示栈的状态和已访问集合以获得满分。

• In A* questions, always identify what g(n) and h(n) represent for the given scenario.

  在 A* 问题中，始终要识别对于给定场景 g(n) 和 h(n) 代表什么。

• For adjacency list vs matrix questions, justify your choice based on graph density and operations required.

  对于邻接表与邻接矩阵的问题，根据图的密度和所需操作来证明你的选择。

• Time management is crucial: practice past paper questions on graph algorithms under timed conditions.

  时间管理至关重要：在限时条件下练习过去试卷中的图算法题目。

• If the question asks for the shortest path, ensure you output the sequence of vertices, not just the distance.

  如果题目要求最短路径，确保输出顶点的序列，而不仅仅是距离。

Graph algorithms are highly visual. Drawing the graph and annotating each step can significantly reduce errors in the exam.

图算法非常直观。在考试中画出图并注释每一步，可以显著减少错误。

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

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