Graph Algorithms in GCSE WJEC Computer Science | GCSE WJEC 计算机：图算法考点精讲

📚 Graph Algorithms in GCSE WJEC Computer Science | GCSE WJEC 计算机：图算法考点精讲

Graph algorithms are a fundamental part of the WJEC GCSE Computer Science specification, enabling us to model and solve real-world problems such as route planning, social networks, and dependency analysis. This article covers the key concepts you need to master: graph terminology, representations, depth-first search, breadth-first search, Dijkstra’s shortest path algorithm, and key exam tips. Each section explains the core idea in English, followed by a matching Chinese explanation to support bilingual learners and ensure thorough understanding.

图算法是 WJEC GCSE 计算机科学考试大纲的核心组成部分，能够用来建模和解决路径规划、社交网络、依赖关系分析等实际问题。本文涵盖你需要掌握的关键概念：图术语、图的表示方法、深度优先搜索、广度优先搜索、Dijkstra最短路径算法以及重要的考试技巧。每个部分先用英文解释核心思想，再用对应的中文说明，以支持双语学习者并确保全面理解。

1. Graph Terminology | 图的基本术语

A graph is a collection of nodes (or vertices) connected by edges. In WJEC GCSE Computer Science, you need to know the difference between directed and undirected graphs, as well as weighted and unweighted graphs. A vertex represents an entity, while an edge represents a relationship. In a directed graph, edges have a direction (one-way), whereas in an undirected graph, edges are two-way.

图是由节点（或顶点）通过边连接而成的集合。在 WJEC GCSE 计算机科学中，你需要区分有向图和无向图，以及加权图和非加权图。顶点代表实体，边代表关系。在有向图中，边有方向（单向），而在无向图中，边是双向的。

Additionally, a weighted graph assigns a numerical value to each edge, often representing cost, distance, or time. A path is a sequence of vertices where each adjacent pair is connected by an edge. A cycle occurs when a path starts and ends at the same vertex without repeating edges. Understanding these terms is essential before tackling algorithms.

此外，加权图为每条边赋予一个数值，通常表示成本、距离或时间。路径是一系列顶点的序列，其中每对相邻顶点由一条边连接。环是指一条路径从某个顶点出发，不重复使用边，最终回到该顶点。在开始学习算法之前，理解这些术语至关重要。

Term (术语)	Definition (定义)
Vertex / Node	A point in the graph (图中的点)
Edge / Arc	A connection between two vertices (两个顶点之间的连接)
Directed graph	Edges have a direction (边有方向)
Undirected graph	Edges have no direction (边无方向)
Weighted graph	Edges carry a numerical value (边带有数值)

2. Graph Representations | 图的表示方法

Graphs can be represented in computer memory using two main structures: the adjacency matrix and the adjacency list. An adjacency matrix is a 2D array where the cell at row i, column j indicates whether there is an edge from vertex i to vertex j. For an unweighted graph, 1 or 0 is typically used; for a weighted graph, the weight value or infinity (∞) is stored.

图在计算机内存中可以使用两种主要结构表示：邻接矩阵和邻接表。邻接矩阵是一个二维数组，其中第 i 行、第 j 列的单元格表示从顶点 i 到顶点 j 是否存在一条边。对于非加权图，通常使用 1 或 0；对于加权图，则存储权重值或无穷大 (∞)。

An adjacency list, on the other hand, uses a list (or dictionary) where each vertex is associated with a linked list or array of its neighbouring vertices. For example, vertex A might store B, C as neighbours. Adjacency lists are more memory-efficient for sparse graphs, while adjacency matrices allow O(1) edge lookups but use more space. WJEC exams may ask you to draw or interpret both.

另一方面，邻接表使用一个列表（或字典），其中每个顶点关联一个链表或数组，存储其相邻顶点。例如，顶点 A 可能将 B、C 存储为邻居。对于稀疏图，邻接表在内存使用上更高效，而邻接矩阵可以实现 O(1) 边查找，但占用更多空间。WJEC 考试可能要求你绘制或解读这两种表示方法。

Consider a simple graph with vertices A, B, C and edges A→B, A→C, B→C. Its adjacency matrix (unweighted) would show 1 at (A,B), (A,C), (B,C) and 0 elsewhere. The adjacency list would list A: B,C; B: C; C: (empty).

考虑一个简单的图，顶点为 A、B、C，边为 A→B、A→C、B→C。其邻接矩阵（非加权）将在 (A,B)、(A,C)、(B,C) 处显示 1，其余为 0。邻接表则会显示 A: B、C；B: C；C:（空）。

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

Depth-first search explores a graph by going as deep as possible along one branch before backtracking. It uses a stack data structure, either explicitly or via recursion. Starting from a given node, DFS visits an unvisited neighbour, marks it as visited, and pushes it onto the stack. It then recursively visits the next unvisited neighbour of that node until no unvisited neighbours remain, at which point it pops the stack and backtracks.

深度优先搜索通过沿着一条分支尽可能深入，然后再回溯的方式来遍历图。它使用栈数据结构，可以显式使用或通过递归隐式使用。从给定节点开始，DFS 访问一个未访问过的邻居，将其标记为已访问，并压入栈。然后递归访问该节点的下一个未访问邻居，直到没有未访问邻居为止，此时弹出栈并回溯。

DFS is useful for detecting cycles, solving mazes, or performing topological sorting. Its time complexity is O(V + E) where V is the number of vertices and E is the number of edges, because each vertex and edge is explored once. In WJEC GCSE, you should be able to trace a DFS manually on a small graph and list the order of visited nodes.

DFS 可用于检测环、解决迷宫问题或执行拓扑排序。其时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数，因为每个顶点和每条边都被访问一次。在 WJEC GCSE 中，你应该能够在小图上手动模拟 DFS，并列出访问节点的顺序。

4. Depth-First Search – Worked Example | 深度优先搜索 – 示例演练

Let’s trace DFS on an undirected graph: A connected to B and C; B connected to A, D, E; C connected to A, F; D connected to B; E connected to B, F; F connected to C, E. Start at A. We’ll push A, mark visited. Neighbours of A: B, C. Choose B (smaller order). Push B, mark visited. From B, neighbours are A, D, E. A visited, pick D. Push D, mark visited. D’s neighbour is only B (visited), so pop D. Back to B, next unvisited neighbour E. Push E, mark visited. From E, neighbours B (visited), F (unvisited). Push F, mark visited. F’s neighbours: C (unvisited), E (visited). Push C, mark visited. Now all visited. Order of visitation: A, B, D, E, F, C.

我们来在一个无向图上模拟 DFS：A 与 B、C 相连；B 与 A、D、E 相连；C 与 A、F 相连；D 与 B 相连；E 与 B、F 相连；F 与 C、E 相连。从 A 开始。我们将 A 压栈并标记为已访问。A 的邻居：B、C。选择 B（按较小顺序）。压入 B，标记已访问。从 B 出发，邻居为 A、D、E。A 已访问，选择 D。压入 D，标记已访问。D 的邻居只有 B（已访问），因此弹出 D。回到 B，下一个未访问邻居 E。压入 E，标记已访问。从 E 出发，邻居 B（已访问）、F（未访问）。压入 F，标记已访问。F 的邻居：C（未访问）、E（已访问）。压入 C，标记已访问。现在所有顶点均已访问。访问顺序：A、B、D、E、F、C。

Notice that DFS does not guarantee the shortest path; it simply explores one branch fully. In exams, you may be asked to trace using a stack or to write a simple algorithm outline.

请注意，DFS 不保证找到最短路径；它只是完整地探索一个分支。在考试中，你可能需要利用栈模拟 DFS 或写出简单的算法概要。

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

Breadth-first search explores a graph level by level, visiting all neighbours of a node before moving to the next level. It uses a queue data structure (FIFO). Starting from a source vertex, BFS enqueues it, marks it visited. Then it repeatedly dequeues a vertex, examines each of its unvisited neighbours, marks them visited, and enqueues them. This process continues until the queue is empty.

广度优先搜索逐层遍历图，在进入下一层之前先访问当前节点的所有邻居。它使用队列数据结构（先进先出）。从源顶点开始，BFS 将其入队并标记为已访问。然后它反复将顶点出队，检查其每个未访问的邻居，将它们标记为已访问并入队。此过程持续到队列为空。

BFS finds the shortest path in an unweighted graph, because it examines nodes in increasing order of distance from the source. It is often used in social network friend suggestions or web crawling. Complexity is also O(V + E).

BFS 可以在非加权图中找到最短路径，因为它按距离源点递增的顺序检查节点。它常用于社交网络好友推荐或网络爬虫。复杂度同样为 O(V + E)。

6. Breadth-First Search – Worked Example | 广度优先搜索 – 示例演练

Using the same graph, start BFS at A. Enqueue A, mark visited. Dequeue A, neighbours B and C. Both unvisited, so mark B, C visited and enqueue B, C. Queue now [B, C]. Dequeue B, neighbours A (visited), D, E. Mark D, E visited, enqueue D, E. Queue [C, D, E]. Dequeue C, neighbours A (visited), F. Mark F visited, enqueue F. Queue [D, E, F]. Dequeue D, no unvisited neighbours. Dequeue E, neighbour F already visited. Dequeue F, neighbour C visited. All done. Visitation order: A, B, C, D, E, F.

使用相同的图，从 A 开始 BFS。将 A 入队，标记为已访问。将 A 出队，邻居 B 和 C 均未访问，因此标记 B、C 已访问并入队 B、C。队列现在为 [B, C]。将 B 出队，邻居 A（已访问）、D、E。标记 D、E 已访问并入队 D、E。队列 [C, D, E]。将 C 出队，邻居 A（已访问）、F。标记 F 已访问并入队 F。队列 [D, E, F]。将 D 出队，无未访问邻居。将 E 出队，邻居 F 已访问。将 F 出队，邻居 C 已访问。全部完成。访问顺序：A、B、C、D、E、F。

Note the order differs from DFS. BFS visits all nodes at distance 1 first (B, C), then distance 2 (D, E, F), which guarantees the shortest path from A to any node in terms of number of edges.

注意顺序与 DFS 不同。BFS 首先访问距离为 1 的所有节点（B、C），然后是距离为 2 的节点（D、E、F），这保证了从 A 到任何节点在边数方面的最短路径。

7. Dijkstra’s Shortest Path Algorithm – Concept | Dijkstra 最短路径算法 – 概念

Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It maintains a set of unvisited nodes and tentative distances (initially set to infinity, except the source which is 0). At each step, it selects the unvisited node with the smallest tentative distance, marks it visited, and updates the distances of its neighbours by considering if going through the current node offers a shorter path.

Dijkstra 算法用于在具有非负边权重的加权图中找到从源节点到所有其他节点的最短路径。它维护一个未访问节点集合和临时距离（初始设为无穷大，源点除外设为 0）。每一步，它选择未访问节点中临时距离最小的节点，将其标记为已访问，并通过考虑是否经过当前节点能得到更短路径来更新其邻居的距离。

This is a classic greedy algorithm and is widely implemented in GPS navigation. The algorithm terminates when all nodes have been visited. A simplified version for small graphs is expected in WJEC GCSE, where you manually update distance tables.

这是一种经典的贪心算法，广泛应用于 GPS 导航。当所有节点都被访问后算法终止。在 WJEC GCSE 中，要求掌握小规模图的简化版本，即手动更新距离表。

8. Dijkstra’s Algorithm – Step-by-Step Example | Dijkstra 算法 – 逐步示例

Consider a weighted directed graph: A→B weight 4, A→C weight 2, B→C weight 1, B→D weight 5, C→D weight 8, C→E weight 10, D→E weight 2, D→F weight 6, E→F weight 2. Start at A. Initialise distances: d(A)=0, others ∞. Unvisited set {A,B,C,D,E,F}. Pick A (smallest 0). Update neighbours: B: 0+4=4 < ∞, set d(B)=4; C: 0+2=2, set d(C)=2. Mark A visited. Next smallest unvisited: C (2). Update C's neighbours: D: 2+8=10, set d(D)=10; E: 2+10=12, set d(E)=12. Mark C visited. Next smallest unvisited: B (4). Update B's neighbours: C visited skip; D: 4+5=9 < 10, update d(D)=9. Mark B visited. Next smallest: D (9). Update D's neighbours: E: 9+2=11 < 12, update d(E)=11; F: 9+6=15, set d(F)=15. Mark D visited. Next: E (11). Update neighbours: F: 11+2=13 < 15, update d(F)=13. Mark E visited. Finally F visited. Shortest distances: A→0, B→4, C→2, D→9, E→11, F→13.

考虑一个加权有向图：A→B 权值 4，A→C 权值 2，B→C 权值 1，B→D 权值 5，C→D 权值 8，C→E 权值 10，D→E 权值 2，D→F 权值 6，E→F 权值 2。从 A 开始。初始化距离：d(A)=0，其他为 ∞。未访问集合 {A,B,C,D,E,F}。选择 A（最小 0）。更新邻居：B：0+4=4 < ∞，设置 d(B)=4；C：0+2=2，设置 d(C)=2。标记 A 已访问。下一个最小未访问节点：C (2)。更新 C 的邻居：D：2+8=10，设置 d(D)=10；E：2+10=12，设置 d(E)=12。标记 C 已访问。下一个最小：B (4)。更新 B 的邻居：C 已访问跳过；D：4+5=9 < 10，更新 d(D)=9。标记 B 已访问。下一个：D (9)。更新 D 的邻居：E：9+2=11 < 12，更新 d(E)=11；F：9+6=15，设置 d(F)=15。标记 D 已访问。下一个：E (11)。更新邻居：F：11+2=13 < 15，更新 d(F)=13。标记 E 已访问。最后 F 已访问。最短距离：A→0，B→4，C→2，D→9，E→11，F→13。

You can trace the path by storing the previous node. For F, previous could be E (since 11+2=13), so path A→C→B→D→E→F. Exams often ask you to complete a table of visited nodes and current shortest distances.

你可以通过存储前驱节点来追踪路径。对于 F，前驱可以是 E（因为 11+2=13），因此路径为 A→C→B→D→E→F。考试中经常要求你填写已访问节点和当前最短距离的表格。

9. When to Use Which Algorithm | 何时使用哪种算法

Choose DFS when you need to explore all paths exhaustively, detect cycles, or solve maze-like problems. BFS is preferred when you need the shortest path in an unweighted graph or level-order traversal. Dijkstra is the go-to algorithm for shortest paths in weighted graphs with non-negative weights. If weights can be negative, Dijkstra fails; then Bellman-Ford would be used, but that’s beyond GCSE scope.

当需要穷举所有路径、检测环或解决迷宫类问题时，选择 DFS。当需要在非加权图中寻找最短路径或进行层序遍历时，BFS 是首选。对于边权非负的加权图的最短路径，Dijkstra 是首选算法。如果权重可能为负，Dijkstra 会失败；此时应使用 Bellman-Ford，但这超出了 GCSE 范围。

In WJEC exams, context matters. For example, routing data between routers in a network where each link has a cost uses Dijkstra. Finding the degrees of separation (friend distance) on a social network can be solved by BFS because friendship graphs are usually unweighted.

在 WJEC 考试中，情境很重要。例如，在网络中路由数据，每条链路都有成本，使用 Dijkstra。在社交网络上计算分离度（好友距离）可以通过 BFS 解决，因为好友关系图通常是非加权的。

10. Common Exam Pitfalls and Tips | 常见考试误区与技巧

Many students confuse DFS order with BFS order. Remember: DFS uses stack (last-in-first-out) and goes deep first; BFS uses queue (first-in-first-out) and goes level by level. Practise drawing the data structures (stack/queue) at each step to avoid mistakes.
Many students also forget to mark nodes as visited immediately when they are pushed/enqueued, leading to duplicate processing. In Dijkstra, ensure you only update neighbours if the new distance is strictly smaller. Also, always select the unvisited node with the smallest tentative distance; do not skip it.

许多学生混淆 DFS 与 BFS 的顺序。记住：DFS 使用栈（后进先出）并优先深入；BFS 使用队列（先进先出）并逐层访问。练习在每一步绘制数据结构（栈/队列）以避免错误。
许多学生还忘记在节点被压栈/入队时立即标记为已访问，导致重复处理。在 Dijkstra 中，确保仅在新的距离严格更小时才更新邻居。同时，始终选择未访问节点中临时距离最小的节点；不要跳过它。

Exam questions may present a graph and ask you to state the order of visiting nodes using DFS or BFS, or to complete a shortest-path table for Dijkstra. Work slowly, double-check your arithmetic, and annotate the graph as you go. When explaining, use precise terminology: ‘vertex’, ‘edge’, ‘traversal’, ‘shortest path’, ‘weighted graph’.

考题可能给出一个图，要求写出使用 DFS 或 BFS 访问节点的顺序，或完成 Dijkstra 的最短路径表格。慢慢来，仔细检查计算，并在图上做标记。解释时，使用精确术语：’顶点’, ‘边’, ‘遍历’, ‘最短路径’, ‘加权图’。

11. Summary Table of Key Algorithms | 关键算法总结表

Algorithm	Data Structure	Graph Type	Purpose
DFS	Stack (explicitly or recursion)	Any	Exhaustive traversal, cycle detection
BFS	Queue	Any (unweighted for shortest path)	Level-order traversal, shortest path (unweighted)
Dijkstra	Priority queue (or manual min-selection)	Weighted, non-negative edges	Shortest path from single source

This table provides a quick reference for recall. Remember that for GCSE, you are not required to implement these algorithms in code, but you must be able to trace them and understand their characteristics.

此表提供了快速参考以便记忆。记住，对于 GCSE，你不需要用代码实现这些算法，但必须能够手动模拟并理解它们的特点。

12. Practice and Revision Advice | 练习与复习建议

To master graph algorithms, create your own small graphs (4-6 nodes) and trace DFS, BFS, and Dijkstra by hand. Compare results with a friend or use online visualisation tools. Pay attention to edge cases: disconnected graphs, graphs with multiple paths, and the handling of equal distances in Dijkstra (choose arbitrarily). Past papers from WJEC often include scenarios involving networks, transport maps, or dependency diagrams.

要掌握图算法，请自行制作小图（4-6 个节点），并手动模拟 DFS、BFS 和 Dijkstra。与同学比较结果或使用在线可视化工具。注意边界情况：非连通图、多路径图以及在 Dijkstra 中处理相等距离（任意选择）。WJEC 的历年真题中经常包含涉及网络、交通地图或依赖关系图的场景。

When revising, explain each algorithm aloud in your own words, and draw the evolving data structures. This dual coding approach strengthens memory. Ensure you can justify why BFS finds the shortest path in unweighted graphs and why Dijkstra works only for non-negative weights. Good luck with your revision!

复习时，用自己的话大声解释每种算法，并画出变化的数据结构。这种双重编码方法可以增强记忆。确保你能够解释为什么 BFS 在非加权图中能找到最短路径，以及为什么 Dijkstra 仅适用于非负权重。祝你复习顺利！

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

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

Graph Algorithms in GCSE WJEC Computer Science | GCSE WJEC 计算机：图算法 考点精讲