📚 Graph Algorithms for GCSE AQA Computer Science | GCSE AQA 计算机图算法考点精讲
Graphs are one of the most versatile data structures in computing, used to model networks like social connections, road maps, and the Web. In the AQA GCSE Computer Science course, you are expected to understand how graphs are represented and traversed, as well as how to find the shortest path using Dijkstra’s algorithm. Mastering these concepts is essential for both the written exam and your computational thinking skills.
图是计算机科学中最通用的数据结构之一，用于建模社交网络、道路地图和万维网等。在 AQA GCSE 计算机科学课程中，你将理解图的表示与遍历方式，并掌握使用 Dijkstra 算法寻找最短路径。掌握这些概念对笔试和计算思维技能都至关重要。
1. Introduction to Graphs | 图的基本概念
A graph is a collection of nodes (also called vertices) connected by edges. Each edge may represent a one-way or two-way relationship, and can optionally carry a weight to indicate cost, distance, or time.
图是由节点（也称顶点）通过边连接而成的集合。每条边可表示单向或双向关系，并可带有权重（权值），用以表示成本、距离或时间。
In an undirected graph, edges have no direction; in a directed graph (digraph), each edge points from one node to another. Weighted graphs assign a numeric value to each edge, which is crucial for shortest-path algorithms.
在无向图中，边没有方向；在有向图中，每条边从一个节点指向另一个节点。加权图则为每条边赋予一个数值，这对最短路径算法至关重要。
2. Graph Terminology | 图的相关术语
Understanding key terms helps you interpret exam questions accurately. A vertex (or node) is a fundamental unit; an edge is a connection between two vertices. The degree of a vertex is the number of edges connected to it. A path is a sequence of vertices where each adjacent pair is connected by an edge. A cycle is a path that starts and ends at the same vertex without repeating edges.
理解关键术语有助于准确解读考题。顶点（节点）是基本单元；边是两顶点间的连接。顶点的度是指连接到它的边数。路径是一系列顶点且相邻顶点间有边相连。环是一条起点与终点重合且不重复边的路径。
Graphs can be connected (there is a path between every pair of vertices) or disconnected. A tree is a special connected graph with no cycles. In directed graphs, ‘in-degree’ and ‘out-degree’ describe edges entering and leaving a vertex.
图可以是连通的（每对顶点间都有路径）或不连通的。树是一种无环的连通图。在有向图中，“入度”和“出度”分别描述进入和离开顶点的边数。
3. Representing Graphs: Adjacency Matrix | 图的表示：邻接矩阵
An adjacency matrix is a 2D array of size V × V (where V is the number of vertices). The cell at row i, column j is 1 (or the edge weight) if there is an edge from vertex i to vertex j; otherwise it is 0 or ∞.
邻接矩阵是一个 V×V 的二维数组（V 为顶点数）。若顶点 i 到顶点 j 有边，则第 i 行第 j 列的单元格为 1（或边的权值）；否则为 0 或 ∞。
This representation makes it fast to check for an edge (O(1) time), but it consumes O(V²) memory, which can be wasteful for sparse graphs. In an undirected graph, the matrix is symmetric across the main diagonal.
这种表示法可以快速检查是否存在边（时间复杂度 O(1)），但占用 O(V²) 内存，对于稀疏图可能浪费空间。在无向图中，矩阵沿主对角线对称。
Below is an example adjacency matrix for a weighted directed graph with vertices A, B, C, D:
以下是一个带权有向图的邻接矩阵示例，顶点为 A、B、C、D：
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 4 | ∞ | 2 |
| B | ∞ | 0 | 3 | ∞ |
| C | ∞ | ∞ | 0 | 1 |
| D | ∞ | 5 | ∞ | 0 |
4. Representing Graphs: Adjacency List | 图的表示：邻接表
An adjacency list stores each vertex alongside a list of its neighbouring vertices (and edge weights if applicable). It is more memory-efficient for sparse graphs, using O(V + E) space, where E is the number of edges.
邻接表为每个顶点存储一个邻接顶点列表（以及相关边权，如果适用）。对于稀疏图它更节省内存，空间复杂度为 O(V+E)，其中 E 为边数。
However, checking whether an edge exists can take longer than with an adjacency matrix, as you may need to scan a list. In the exam you may be asked to draw or interpret an adjacency list for a given graph.
然而，检查边是否存在可能比邻接矩阵更费时，因为可能需要扫描列表。考试可能会要求你绘制或解读给定图的邻接表。
5. Graph Traversal: Depth-First Search (DFS) | 图的遍历：深度优先搜索
Depth-First Search explores as far down a branch as possible before backtracking. It uses a stack – either explicitly or via recursion – to remember the path. DFS is useful for detecting cycles, topological sorting, and solving maze-like problems.
深度优先搜索会沿分支尽可能深入，然后回溯。它使用栈（显式或通过递归）来记住路径。DFS 可用于检测环、拓扑排序以及解决迷宫类问题。
Steps for DFS starting at a given node: (1) push the start node onto the stack and mark it as visited. (2) While the stack is not empty, pop a node. (3) For each unvisited neighbour, push it onto the stack and mark it as visited. (4) Record the order of popped nodes as the traversal result.
从给定节点开始 DFS 的步骤：(1) 将起始节点压入栈并标记为已访问。(2) 当栈非空时，弹出一个节点。(3) 对于每个未访问的邻居，将其压入栈并标记为已访问。(4) 记录弹出节点的顺序作为遍历结果。
In the exam, you may be asked to show the order in which nodes are visited using DFS on a simple graph. Always keep a table of visited nodes and the stack contents to avoid mistakes.
考试中可能会要求你用 DFS 遍历简单图并写出节点访问顺序。务必维护已访问节点表和栈内容，以避免错误。
6. Graph Traversal: Breadth-First Search (BFS) | 图的遍历：广度优先搜索
Breadth-First Search explores all neighbours at the current depth before moving deeper. It uses a queue to store nodes in first-in-first-out order. BFS finds the shortest path in terms of the number of edges in an unweighted graph.
广度优先搜索先访问当前深度的所有邻居，再进入下一层。它使用队列按先进先出顺序存储节点。在无权图中，BFS 可以找到边数最少的最短路径。
The BFS procedure: (1) enqueue the start node and mark it visited. (2) Dequeue a node and examine it. (3) For each unvisited neighbour, enqueue it and mark it visited. (4) Repeat until the queue is empty. The order of dequeuing gives the BFS traversal.
BFS 流程：(1) 起始节点入队并标记已访问。(2) 节点出队并访问。(3) 对于每个未访问的邻居，将其入队并标记已访问。(4) 重复直到队列为空。出队顺序即为 BFS 遍历结果。
Knowing when to use DFS or BFS is important. Choose BFS when you need the shortest path by edge count or level-order exploration; choose DFS for exhaustive searches and backtracking puzzles.
知道何时使用 DFS 或 BFS 很重要。需要按边数的最短路径或按层探索时选 BFS；需要穷举搜索和回溯谜题时选 DFS。
7. Shortest Path: Dijkstra’s Algorithm | 最短路径：Dijkstra 算法
Dijkstra’s algorithm finds the shortest distance from a source node to every other node in a weighted graph with non-negative edge weights. It gradually builds the set of nodes for which the shortest path is confirmed.
Dijkstra 算法用于在边权非负的加权图中，找出从源节点到其他所有节点的最短距离。它逐步构建已确定最短路径的节点集合。
It works by maintaining two sets: visited (shortest distance known) and unvisited. Initially all distances are set to ∞ except the source (distance 0). At each step, the unvisited node with the smallest tentative distance is chosen, made visited, and its neighbours’ distances are updated if a shorter route is found.
算法维持两个集合：已访问 (最短距离已知) 和未访问。初始所有距离设为 ∞，源节点除外 (距离 0)。每一步选取未访问节点中试探距离最小的节点，将其标记为已访问，并更新其邻居的距离（若发现更短路径）。
The update rule is: if d[u] + w(u, v) < d[v], then set d[v] = d[u] + w(u, v), where d[x] is the current shortest distance from the source and w(u,v) is the weight of the edge from u to v.
更新规则为：若 d[u] + w(u, v) < d[v]，则 d[v] = d[u] + w(u, v)，其中 d[x] 是从源点至 x 的当前最短距离，w(u,v) 是边 u→v 的权。
8. Worked Example of Dijkstra’s Algorithm | Dijkstra 算法实例
Consider a weighted graph with vertices A, B, C, D, E. The source is A. The edges: A→B (6), A→D (1), B→C (5), B→D (2), D→B (2), D→E (1), E→B (2), E→C (5). Follow the steps to compute shortest distances.
考虑一个带权图，顶点为 A、B、C、D、E，源点为 A。边：A→B (6)，A→D (1)，B→C (5)，B→D (2)，D→B (2)，D→E (1)，E→B (2)，E→C (5)。遵照步骤计算最短距离。
Initial distances: A=0, others=∞. Unvisited: {A,B,C,D,E}. Choose A. Neighbours B (6) and D (1) get updated: B=6, D=1. Mark A visited.
初始距离：A=0，其他=∞。未访问集：{A,B,C,D,E}。选取 A。邻居 B (6) 和 D (1) 更新：B=6，D=1。标记 A 已访问。
Next smallest unvisited is D (1). Neighbours: B (current 6, via D 1+2=3 → update to 3) and E (1+1=2). Now B=3, E=2. Mark D visited.
未访问中最小的是 D (1)。邻居：B（当前 6，经 D 为 1+2=3 → 更新为 3）和 E (1+1=2)。现在 B=3，E=2。标记 D 已访问。
Next smallest is E (2). Neighbours: B (3, via E 2+2=4 → no change) and C (2+5=7). Set C=7. Mark E visited.
未访问中最小的是 E (2)。邻居：B（3，经 E 为 2+2=4 → 不变）和 C (2+5=7)。设 C=7。标记 E 已访问。
Next smallest is B (3). Neighbour C (current 7, via B 3+5=8 → no change). Mark B visited. Finally, choose C (7) – no unvisited neighbours. Final distances: A=0, B=3, C=7, D=1, E=2.
未访问中最小的是 B (3)。邻居 C（当前 7，经 B 为 3+5=8 → 不变）。标记 B 已访问。最后选取 C (7)——无未访问邻居。最终距离：A=0，B=3，C=7，D=1，E=2。
Shortest path from A to C: A → D → E → C with total weight 7
从 A 到 C 的最短路径：A → D → E → C，总权值为 7
9. Applications of Graph Algorithms | 图算法的应用
Graph traversal and shortest-path algorithms underpin many real-world technologies. BFS is used in social network friend suggestion (‘people you may know’), web crawling, and GPS navigation for unweighted routes. DFS is applied in puzzle solving, compiler design, and detecting cycles in dependencies.
图的遍历与最短路径算法支撑了许多现实技术。BFS 用于社交网络的好友推荐（“可能认识的人”）、网页爬虫和无权路径的 GPS 导航。DFS 用于解谜、编译器设计以及依赖关系中的环检测。
Dijkstra’s algorithm is the foundation of modern route-planning software, internet packet routing (link-state protocols like OSPF), and even in artificial intelligence for pathfinding in games. Understanding these applications can help you answer context-based exam questions more effectively.
Dijkstra 算法是现代路径规划软件、互联网分组路由（如 OSPF 等链路状态协议）的基础，甚至用于游戏中的人工智能寻路。理解这些应用有助于你更有效地回答基于情境的考题。
10. Exam Tips and Common Mistakes | 考试技巧与常见错误
In the AQA exam, you are often given a graph diagram and asked to trace Dijkstra’s algorithm by completing a distance table. Show all steps clearly, and always update the table when a shorter path is found. Do not forget to mark a node as visited once it is selected.
在 AQA 考试中，常会给出一个图并要求通过填写距离表来跟踪 Dijkstra 算法。清晰展示所有步骤，每当发现更短路径时一定要更新表格。节点被选出后不要忘记标记为已访问。
When performing DFS or BFS, be systematic: record the current data structure (stack/queue) and visited list at each step. A common mistake is missing a neighbour or revisiting an already visited node. Practise with both directed and undirected graphs.
执行 DFS 或 BFS 时要有条理：每一步记录当前数据结构（栈/队列）和已访问列表。常见错误是遗漏邻居或重复访问已访问节点。要用有向图和无向图分别练习。
For adjacency matrices, remember that the diagonal is often 0 (distance from a node to itself). In weighted graphs, use ∞ for absent edges. Check that you correctly interpret matrix dimensions – row to column corresponds to edge direction.
对于邻接矩阵，记住对角线通常为 0（节点到自身的距离）。在加权图中，无边处用 ∞。确保正确解读矩阵维度——行到列对应边的方向。
- Keep your working neat and labelled – examiners award marks for method.
- 保持书写整洁并标注清晰——考官按步骤给分。
- Memorise the Dijkstra update condition and apply it exactly.
- 记住 Dijkstra 更新条件并准确运用。
- Understand when to use infinity symbols and zero in initial distance tables.
- 明白初始距离表何时用无穷大符号和零。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导