GCSE CCEA Computer Science: Graph Algorithms Explained | GCSE CCEA 计算机：图算法考点精讲

📚 GCSE CCEA Computer Science: Graph Algorithms Explained | GCSE CCEA 计算机：图算法考点精讲

Graph algorithms are a core part of the CCEA GCSE Computer Science specification. You are expected to understand how data can be modelled as a graph, how to represent graphs in computer memory, and how standard traversal algorithms (Depth-First Search and Breadth-First Search) explore a graph step by step. This article will take you through every key concept, using clear explanations, worked examples, and pseudocode that follows the style commonly seen in CCEA exam questions.

图算法是 CCEA GCSE 计算机科学考纲的核心内容之一。你需要掌握如何将数据建模为图结构，如何在计算机内存中表示图，以及标准的遍历算法（深度优先搜索和广度优先搜索）如何一步步探索图。本文将通过清晰的解释、详细的示例和贴近 CCEA 考试风格的伪代码，带你逐一攻克每个关键考点。

1. What is a Graph? | 什么是图？

A graph is a collection of vertices (also called nodes) connected by edges. Graphs can model real-world systems such as social networks, transport links, or the structure of a website. In GCSE Computer Science, a graph can be directed (edges have a direction) or undirected (edges are two-way), and sometimes weighted (edges carry a value, such as distance or cost). Unless specified, we assume an unweighted, undirected graph for traversal algorithms.

图是由顶点（也称节点）通过边连接而成的集合。图可以模拟现实世界中的系统，例如社交网络、交通连接或网站结构。在 GCSE 计算机科学中，图可以是有向的（边具有方向）或无向的（边是双向的），有时还是加权的（边带有诸如距离或成本之类的值）。除非另有说明，遍历算法通常基于无权的无向图。

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

To store a graph in a program, we use either an adjacency matrix or an adjacency list. The choice affects memory usage and the speed of certain operations. You must be able to draw both representations from a given diagram and explain the trade-offs.

在程序中存储图，我们可以使用邻接矩阵或邻接表。选择哪种表示方法会影响内存使用和某些操作的速度。你必须能根据给定的图绘制出两种表示方法，并解释它们各自的优缺点。

An adjacency matrix is a two-dimensional array (n x n for n vertices) where cell [i][j] is 1 if there is an edge from vertex i to vertex j, and 0 otherwise. For an undirected graph, the matrix is symmetric. It uses O(n²) memory, which is wasteful for sparse graphs but allows fast edge lookup.

邻接矩阵是一个二维数组（n 个顶点对应 n×n 矩阵），若顶点 i 到顶点 j 存在边，则单元格[i][j]为 1，否则为 0。对于无向图，矩阵是对称的。邻接矩阵占用 O(n²) 内存，对于稀疏图而言很浪费，但能快速查询边的存在。

An adjacency list stores, for each vertex, a list of adjacent vertices. For an unweighted graph, this can be an array of linked lists or dynamic arrays. It uses O(v+e) memory, which is efficient for sparse graphs, but checking for a specific edge takes O(degree) time.

邻接表为每个顶点存储一个邻接顶点的列表。对于无权图，可以用链表或动态数组构成的数组来实现。它占用 O(v+e) 内存，对稀疏图非常高效，但检查特定边是否存在需要 O(degree) 的时间。

3. Why Traverse a Graph? | 为什么要遍历图？

Graph traversal is the process of visiting every vertex in a graph, typically starting from a given node. Traversal algorithms are fundamental for solving problems like pathfinding, web crawling, network broadcasting, and detection of connected components. CCEA focuses on two standard methods: Depth-First Search (DFS) and Breadth-First Search (BFS).

图的遍历是指访问图中所有顶点的过程，通常从某个给定节点开始。遍历算法是解决寻路、网页爬取、网络广播和连通分量检测等问题的基础。CCEA 考试聚焦于两种标准方法：深度优先搜索（DFS）和广度优先搜索（BFS）。

4. Depth-First Search (DFS) Overview | 深度优先搜索 (DFS) 概述

Depth-First Search explores a graph by going as far as possible along a branch before backtracking. It can be implemented using a stack (either an explicit stack or recursion, which uses the call stack). DFS is useful for tasks like maze solving, topological sorting, and detecting cycles.

深度优先搜索通过沿着一条分支尽可能走远，然后再回溯的方式来探索图。它可以使用栈来实现（显式栈或利用递归调用栈）。DFS 常用于迷宫求解、拓扑排序和环检测等任务。

5. DFS Algorithm Step-by-Step | DFS 算法步骤

The DFS algorithm from a starting vertex S proceeds as follows:

从起始顶点 S 出发的 DFS 算法步骤如下：

Mark S as visited.
For each unvisited neighbour N of S, recursively perform DFS from N (or push N onto the stack if using an iterative stack).
If no unvisited neighbours remain, backtrack to the previous vertex.

标记 S 为已访问。
对 S 的每个未访问邻居 N，递归地从 N 执行 DFS（若使用迭代栈，则将 N 压入栈）。
若没有未访问邻居，则回溯至前一个顶点。

Exam questions often ask you to simulate DFS on a small graph, showing the order in which nodes are visited. Make sure you follow the alphabetical or numerical order of neighbours to guarantee a unique answer.

考试中常要求你在一个小型图上模拟 DFS，展示节点的访问顺序。务必按字母序或数字序处理邻居，以确保得到唯一答案。

6. DFS Worked Example | DFS 示例详解

Consider an undirected graph with vertices A, B, C, D, E. A is connected to B and C; B is connected to D and E; C is connected to E. Starting at A, and visiting neighbours alphabetically, a possible DFS order is: A → B → D → E → C. The process:

考虑一个无向图，顶点为 A、B、C、D、E。A 连接 B 和 C；B 连接 D 和 E；C 连接 E。从 A 开始，按字母序访问邻居，可能的 DFS 访问顺序为：A → B → D → E → C。过程如下：

Visit A. Unvisited neighbours: B, C. Choose B (alphabetical order).
Visit B. Unvisited neighbours: D, E. Choose D.
Visit D. No unvisited neighbours. Backtrack to B.
From B, next unvisited neighbour: E. Visit E.
From E, unvisited neighbour: C. Visit C. All nodes visited.

访问 A。未访问邻居：B, C。选择 B（字母序）。
访问 B。未访问邻居：D, E。选择 D。
访问 D。无未访问邻居，回溯到 B。
从 B，下一个未访问邻居：E。访问 E。
从 E，未访问邻居：C。访问 C。全部节点访问完毕。

In pseudocode, a recursive DFS looks like this:

递归实现的 DFS 伪代码如下：

PROCEDURE DFS(vertex)
    MARK vertex AS visited
    FOR each neighbour IN adjacency_list[vertex]
        IF neighbour NOT visited THEN
            DFS(neighbour)
        ENDIF
    ENDFOR
ENDPROCEDURE

7. Breadth-First Search (BFS) Overview | 广度优先搜索 (BFS) 概述

Breadth-First Search explores a graph level by level. Starting from a source vertex, it visits all its immediate neighbours, then neighbours of those neighbours, and so on. BFS uses a queue to keep track of the order in which to visit vertices. It is particularly good for finding the shortest path in an unweighted graph.

广度优先搜索按层级探索图。从源顶点开始，先访问它的所有直接邻居，然后再访问这些邻居的邻居，以此类推。BFS 使用一个队列来记录顶点访问的顺序。它在无权图中寻找最短路径时尤为出色。

8. BFS Algorithm Step-by-Step | BFS 算法步骤

The BFS algorithm starts with a queue containing the starting vertex. Then it repeats:

BFS 算法从一个包含起始顶点的队列开始。然后重复以下步骤：

Dequeue a vertex V from the front of the queue.
If V is unvisited, mark it as visited and output V.
Enqueue all unvisited neighbours of V.

从队列前端取出一个顶点 V。
若 V 未被访问，则标记为已访问并输出 V。
将 V 的所有未访问邻居入队。

This continues until the queue is empty. Note: In some exam boards’ pseudocode, you may see neighbours enqueued only if they are not already in the queue or visited; be careful to follow the given mark scheme.

重复这一过程，直到队列为空。注意：在某些考试局提供的伪代码中，邻居只有在尚未入队或未访问时才入队；答题时需要严格遵循评分方案的要求。

9. BFS Worked Example | BFS 示例详解

Using the same graph (A–B, A–C, B–D, B–E, C–E), start at A with alphabetical ordering:

使用同一个图（A–B, A–C, B–D, B–E, C–E），从 A 开始，按字母序：

Queue: [A]. Dequeue A, mark visited. Neighbours B, C enqueued. Queue: [B, C].
Dequeue B, mark visited. Neighbours D, E enqueued (A is already visited). Queue: [C, D, E].
Dequeue C, mark visited. Neighbour E already in queue (or visited), ignore. Queue: [D, E].
Dequeue D, mark visited. No new neighbours. Queue: [E].
Dequeue E, mark visited. Queue empty. Visit order: A, B, C, D, E.

队列：[A]。A 出队并标记已访问。邻居 B、C 入队。队列：[B, C]。
B 出队并标记已访问。邻居 D、E 入队（A 已访问）。队列：[C, D, E]。
C 出队并标记已访问。邻居 E 已在队列中（或已访问），忽略。队列：[D, E]。
D 出队并标记已访问。无新邻居。队列：[E]。
E 出队并标记已访问。队列空。访问顺序：A, B, C, D, E。

Pseudocode for iterative BFS:

迭代实现的 BFS 伪代码：

PROCEDURE BFS(startVertex)
    CREATE queue
    ENQUEUE startVertex
    MARK startVertex AS visited
    WHILE queue NOT empty
        current = DEQUEUE queue
        OUTPUT current
        FOR each neighbour IN adjacency_list[current]
            IF neighbour NOT visited THEN
                MARK neighbour AS visited
                ENQUEUE neighbour
            ENDIF
        ENDFOR
    ENDWHILE
ENDPROCEDURE

10. Applications of Graph Traversal | 图遍历的应用

DFS and BFS are not just abstract exercises — they power many real-world algorithms. In CCEA exams, you may be asked to suggest a suitable algorithm for a given scenario.

DFS 和 BFS 不仅仅是抽象练习，它们支撑着许多现实世界的算法。在 CCEA 考试中，你可能会被要求为特定场景推荐合适的算法。

DFS: used in maze generation and solving, detecting cycles in a graph, and finding strongly connected components.
BFS: used in finding the shortest number of links between two web pages (search engine crawling), peer-to-peer networking, and GPS navigation in unweighted maps.

DFS：用于迷宫生成与求解、图内环检测以及查找强连通分量。
BFS：用于在网页之间查找最短链接数（搜索引擎爬虫）、点对点网络以及无权地图的 GPS 导航。

11. Comparing DFS and BFS | 比较 DFS 与 BFS

Both algorithms have the same time complexity O(v + e) when using an adjacency list, but differ in the data structure used and the order of visitation. This table summarises the key differences you must remember for the exam:

两种算法在邻接表表示下时间复杂度同为 O(v + e)，但使用了不同的数据结构，访问顺序也不同。下表总结了考试中必须牢记的关键区别：

Feature / 特性	DFS	BFS
Data Structure / 数据结构	Stack (explicit or recursion) / 栈（显式或递归）	Queue / 队列
Order / 顺序	Deepest node first / 先深后广	Level-by-level / 逐层扩展
Shortest path (unweighted) / 最短路径（无权）	Not guaranteed / 不保证	Guaranteed / 保证最短
Memory (worst case) / 内存（最坏情况）	O(h) depth of tree / 树深度	O(w) max width / 最大宽度

12. Exam Tips and Common Mistakes | 考试技巧与常见错误

CCEA exam questions on graph algorithms often ask you to trace the state of a stack or queue, write down the order of visited nodes, or explain the purpose of a visited list. Here are tips to boost your marks:

CCEA 关于图算法的试题常要求你跟踪栈或队列的状态、写出节点访问顺序或解释已访问列表的作用。以下技巧能帮你提高得分：

Always use a visited array/flag to prevent infinite loops, especially in graphs with cycles.
When tracing manually, keep a clear record of the data structure (stack/queue) at each step.
Check the question’s rule for neighbour ordering — it is usually alphabetic or numeric. Stick to it strictly.
In pseudocode, ensure you mark a node as visited before enqueuing or pushing it to avoid duplicates.
If asked to compare DFS and BFS, mention both the data structure and the order of exploration. Simply stating ‘DFS uses stack, BFS uses queue’ is often not enough — you must explain the consequence of that choice.

始终使用 visited 数组或标记来防止无限循环，特别是在有环的图中。
手动跟踪时，清晰地记录每一步的数据结构（栈或队列）的状态。
检查题目对邻居顺序的规定——通常是字母序或数字序，务必严格遵守。
在伪代码中，确保将节点标记为已访问后再入队或压栈，以避免重复。
如果要求比较 DFS 和 BFS，不仅要提到数据结构的不同，还要说明这种选择带来的访问顺序差异——只写“DFS 用栈，BFS 用队列”往往不够，你必须解释这种选择的后果。

Mastering graph traversal is about practice: draw small graphs, run the algorithms by hand, and compare your results with the mark schemes from past papers. Understanding the logic behind each step will help you tackle any graph problem with confidence.

掌握图遍历的关键在于练习：绘制小图，手工运行算法，并与往年真题的评分方案比对结果。理解每一步背后的逻辑，将帮助你自信地应对任何图问题。

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

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

GCSE CCEA Computer Science: Graph Algorithms Explained | GCSE CCEA 计算机：图算法 考点精讲