📚 Graph Algorithms for GCSE Computer Science | GCSE 计算机图算法考点精讲
Graphs are one of the most powerful and flexible data structures in computer science. For GCSE Computer Science, you are expected to understand how graphs and trees can be represented, how to traverse them using standard algorithms, and how to solve classic problems such as finding the shortest path or constructing a minimum spanning tree. This article breaks down every key concept, walks through each algorithm step by step, and highlights the most common exam-style traps – so you can approach graph questions with confidence.
图是计算机科学中最强大、最灵活的数据结构之一。在 GCSE 计算机科学考试中，你需要掌握图和树的表示方法、如何使用标准算法进行遍历，以及如何解决最短路径或最小生成树等经典问题。本文会详细拆解每一个核心概念，逐步讲解每一种算法，并点出最常见的考试陷阱，让你面对图相关考题时充满信心。
1. What Is a Graph? | 什么是图？
A graph is a collection of nodes (also called vertices) connected by edges. Graphs can be directed (edges have a one-way direction) or undirected (edges go both ways). They may also be weighted, where each edge has a numerical value representing cost, distance, or capacity. Trees are special graphs with no cycles, where any two vertices are connected by exactly one path.
图是由节点（也称顶点）通过边连接而成的集合。图可以是有向的（边具有单向方向），也可以是无向的（边是双向的）。图还可以带权重，每条边有一个数值，代表代价、距离或容量。树是一种特殊的图，没有环，任意两个顶点之间有且仅有一条路径。
2. Representing Graphs: Adjacency Matrix and List | 图的表示：邻接矩阵与邻接表
There are two standard ways to represent a graph in computer memory: an adjacency matrix and an adjacency list. An adjacency matrix is a 2D array where element [i][j] stores 1 (or the edge weight) if there is an edge from vertex i to vertex j; otherwise it stores 0 or infinity. This representation is intuitive but uses O(n²) memory. An adjacency list stores, for each vertex, a list of its neighbouring vertices (and associated weights if weighted). This is more memory-efficient for sparse graphs, using O(V + E) space where V is the number of vertices and E the number of edges.
在计算机内存中表示图有两种标准方法：邻接矩阵和邻接表。邻接矩阵是一个二维数组，如果从顶点 i 到顶点 j 存在边，则元素 [i][j] 存储 1（或边的权重），否则存储 0 或无穷大。这种表示方法直观，但需要 O(n²) 的内存。邻接表为每个顶点维护一个列表，存储其相邻顶点（以及带权重图中的对应权重）。对于稀疏图，这种方式更节省内存，空间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。
In GCSE exams, you might be given a diagram and asked to write out the adjacency matrix or list. Remember that an undirected edge is symmetric in the matrix and appears in both lists.
在 GCSE 考试中，你可能会遇到给出图并要求写出邻接矩阵或邻接表的题目。请记住，无向边在矩阵中是对称的，并且在邻接表的两边列表中都会出现。
3. Depth-First Search (DFS) | 深度优先搜索
Depth-First Search explores a graph by going as deep as possible down one branch before backtracking. Starting from a chosen vertex, DFS visits an unvisited neighbour, then recursively visits that neighbour’s unvisited neighbour, and so on. When it reaches a vertex with no unvisited neighbours, it backtracks to the previous vertex and tries another branch. This algorithm can be implemented using recursion or an explicit stack.
深度优先搜索通过沿着一条分支尽可能深入探索图，然后再回溯。从选定的顶点出发，DFS 访问一个未访问过的邻居，然后递归地访问该邻居的未访问邻居，依此类推。当到达一个没有未访问邻居的顶点时，它会回溯到上一个顶点，并尝试另一条分支。该算法可以使用递归或显式栈来实现。
DFS is particularly useful for tasks such as detecting cycles, topological sorting (for directed acyclic graphs), and solving maze or puzzle problems. In the traversal order, DFS produces a path that dives deep into the graph quickly.
DFS 特别适用于检测环、拓扑排序（有向无环图）以及解决迷宫或谜题等问题。在遍历顺序上，DFS 产生的路径会迅速深入图的最深处。
4. Breadth-First Search (BFS) | 广度优先搜索
Breadth-First Search explores a graph by visiting all neighbours of the current vertex before moving to the next level. Starting from the source vertex, BFS visits all its immediate neighbours first, then the neighbours of those neighbours, and so on. A queue is used to keep track of vertices to visit next. BFS guarantees that vertices are visited in non-decreasing order of distance from the source (in terms of number of edges).
广度优先搜索在进入下一层之前，先访问当前顶点的所有邻居。从源顶点开始，BFS 先访问其所有直接邻居，然后再访问这些邻居的邻居，如此逐层展开。算法使用一个队列来记录接下来要访问的顶点。BFS 确保按与源顶点的距离（以边数计）非递减顺序访问顶点。
BFS is the foundation for finding the shortest path in an unweighted graph, testing bipartiteness, and web crawling. The traversal order gives a level-by-level structure, which is why BFS is also called a level-order traversal in trees.
BFS 是在无权图中寻找最短路径、测试二分图以及网络爬虫等应用的基础。遍历顺序呈现出逐层结构，因此 BFS 在树中也称为层序遍历。
5. Comparing DFS and BFS | DFS 与 BFS 的对比
Choosing between DFS and BFS depends on the problem. DFS uses a stack (implicit recursion) and often requires less memory for deep, narrow graphs, but it can get stuck exploring a very long path that never leads to the target. BFS uses a queue and finds the shortest path in an unweighted graph, but it can consume more memory because it stores all vertices at the current level. In terms of complexity, both visit every vertex and edge once, giving O(V + E) time.
选择 DFS 还是 BFS 取决于具体问题。DFS 使用栈（隐式递归），对于深而窄的图通常占用较少内存，但可能陷在一条很长的路径中迟迟找不到目标。BFS 使用队列，能够在无权图中找到最短路径，但可能占用更多内存，因为它需要存储当前层的所有顶点。在时间复杂度上，两者都访问每个顶点和每条边一次，均为 O(V + E)。
| Aspect | DFS | BFS | 方面 |
|---|---|---|---|
| Data structure | Stack | Queue | 数据结构 |
| Shortest path | Not guaranteed | Yes (unweighted) | 最短路径 |
| Memory | O(depth) – often lower | O(width) – can be high | 内存 |
When you see an exam question that asks ‘Explain why BFS is used to find the shortest route in a maze’, you can point out that BFS explores level by level, ensuring the first time a node is discovered is via the shortest path.
当你在考试中看到“解释为什么 BFS 用于在迷宫中寻找最短路径”时，你可以指出 BFS 逐层探索，确保首次发现一个节点时经过的路径就是最短路径。
6. Shortest Path: Dijkstra’s Algorithm | 最短路径：Dijkstra 算法
Dijkstra’s algorithm finds the shortest path from a starting vertex to all other vertices in a weighted graph with non-negative edge weights. It maintains a set of unvisited vertices and repeatedly selects the unvisited vertex with the smallest tentative distance, updates its neighbours, and marks it as visited. A priority queue is often used to achieve good performance. The algorithm guarantees the shortest path once a vertex is visited.
Dijkstra 算法用于在带有非负权重的加权图中，寻找从起始顶点到所有其他顶点的最短路径。它维护一个未访问顶点集合，反复选择暂定距离最小的未访问顶点，更新其邻居的距离，然后将其标记为已访问。通常使用优先队列来获得较好的性能。一旦某个顶点被访问，算法就保证已找到到达该顶点的最短路径。
In GCSE exams, you are typically required to trace Dijkstra on a small graph using a table. The table records the vertex, the shortest distance from start, the previous vertex, and a visited flag. At each step, you pick the unvisited vertex with the smallest distance, update neighbours if a shorter path is found, and repeat until all vertices are visited.
在 GCSE 考试中，通常要求你在一个小图上用表格跟踪 Dijkstra 算法。表格记录顶点、从起点到该顶点的最短距离、前驱顶点以及是否已访问的标志。每一步选择距离最小的未访问顶点，如果找到更短路径则更新邻居的距离，重复直到所有顶点都被访问。
Updated distance = min( current distance, distance[v] + weight(v, neighbour) )
更新距离 = min( 当前距离, distance[v] + 边(v, 邻居)的权重 )
7. Minimum Spanning Tree: Prim’s Algorithm | 最小生成树：Prim 算法
A Minimum Spanning Tree (MST) connects all vertices of a weighted, undirected graph with the minimum possible total edge weight, without forming cycles. Prim’s algorithm builds the MST by starting from an arbitrary vertex and repeatedly adding the cheapest edge that connects a vertex already in the tree to a vertex outside the tree, until all vertices are included.
最小生成树 (MST) 用最小的总边权连接加权无向图的所有顶点，且不形成环。Prim 算法通过从一个任意顶点开始，反复添加连接树内顶点与树外顶点的最便宜边，直到所有顶点都被包含，从而构建 MST。
The algorithm maintains a set of visited vertices and a data structure to track the minimum edge weight from the tree to every unvisited vertex. In a typical GCSE paper, you would show the step-by-step growth of the MST by listing the edges in the order they are added and maybe updating a table of best connecting edges.
算法维护一个已访问顶点集合，以及一个数据结构来跟踪从树到每个未访问顶点的最小边权。在典型的 GCSE 试卷中，你需要通过列出边加入的顺序来展示 MST 的逐步生成过程，可能需要更新最佳连接边的表格。
8. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树：Kruskal 算法
Kruskal’s algorithm takes a different approach: sort all edges by weight, then iterate through them in ascending order, adding an edge to the MST if it does not form a cycle. A disjoint-set (union-find) data structure is used to check for cycles efficiently. This algorithm builds the MST edge by edge, focusing on the global cheapest unused edge that doesn’t create a circuit.
Kruskal 算法则采用不同的方法：按权重对所有边进行排序，然后按升序遍历这些边，如果一条边不会形成环，就将其加入 MST。为了高效地检查环，通常使用并查集（disjoint-set）数据结构。该算法一条边一条边地构建 MST，关注的是全局最便宜的、尚未使用的且不会形成回路的边。
While both Prim and Kruskal produce the same total minimum weight (if all edge weights are distinct), the order of edge addition differs. Prim grows a single tree; Kruskal can grow a forest of trees that eventually connect. In exams, you can be asked to list the edges in the order they would be chosen by each algorithm.
虽然 Prim 和 Kruskal 得到的最小总权重相同（如果所有边权都不同），但添加边的顺序不同。Prim 生长一棵树；Kruskal 则可能先生长出一片森林，最终连接成一棵树。在考试中，可能会要求你列出每个算法选择边的顺序。
9. Real-world Applications of Graph Traversals | 图遍历的实际应用
Graph algorithms appear everywhere. DFS is used in puzzle solvers (e.g., Sudoku backtracking), cycle detection in dependency graphs, and finding strongly connected components. BFS powers social network friend suggestions (friends of friends), GPS navigation for unweighted road networks, and peer-to-peer network searches. Dijkstra’s algorithm underpins route planners like Google Maps (when simplified to non-negative weights) and network routing protocols. Minimum spanning trees are key in designing efficient networks such as electricity grids, water pipe layouts, and computer network cabling.
图算法无处不在。DFS 用于谜题求解（如数独回溯）、依赖图中的环检测以及寻找强连通分量。BFS 驱动着社交网络的好友推荐（朋友的朋友）、无权道路网的 GPS 导航以及点对点网络搜索。Dijkstra 算法是 Google 地图等路线规划器（简化为非负权重时）和网络路由协议的基础。最小生成树在设计高效网络（如电网、水管布局和计算机网络布线）中起着关键作用。
Connecting these algorithms to real-world scenarios not only helps you remember them but also answers the ‘evaluate’ and ‘justify’ questions that frequently appear in GCSE exams.
将这些算法与实际场景联系起来，不仅有助于记忆，还能回答 GCSE 考试中经常出现的“评估”和“论证”类问题。
10. Common Mistakes and Exam Tips | 常见错误与考试提示
Many students lose marks by confusing the order of vertex visitation in DFS and BFS. Always double-check the data structure: DFS uses stack (last-in-first-out), BFS uses queue (first-in-first-out). When tracing Dijkstra, remember to update distances for all unvisited neighbours, not just the one with the smallest tentative value. Also, never overwrite a distance if the new path is not shorter. For MST algorithms, ensure you do not create a cycle – this is the most common error with Kruskal’s algorithm, where adding a seemingly cheap edge can still be illegal because it connects two vertices already in the same component.
许多学生因混淆 DFS 和 BFS 中顶点访问的顺序而失分。务必反复检查数据结构：DFS 使用栈（后进先出），BFS 使用队列（先进先出）。在跟踪 Dijkstra 算法时，记得更新所有未访问邻居的距离，而不仅仅是暂定值最小的那个。同时，如果新路径并不更短，决不要覆盖原有距离。对于 MST 算法，确保不形成环——这是 Kruskal 算法最常见的错误，因为添加一条看似便宜的边仍然可能非法，原因在于它连接了两个已经属于同一连通分量的顶点。
- Exam tip: Always write the distance table row by row, showing exactly which vertex is visited at each step.
- 考试提示： 一定要逐行书写距离表，清晰地显示每一步访问了哪个顶点。
- Exam tip: When drawing a tree from BFS or DFS, label edges with the order of traversal.
- 考试提示： 当根据 BFS 或 DFS 绘制树时，用遍历顺序给边标号。
- Exam tip: In compare-and-contrast questions, always mention time complexity, space complexity, and suitability for different types of graphs.
- 考试提示： 在比较与对比类问题中，始终提及时间复杂度、空间复杂度以及适用于何种类型的图。
Lastly, practice tracing algorithms on small graphs until the process becomes automatic. The GCSE examiner expects precise, step-by-step working – showing your method is as important as the final answer.
最后，要在小图上反复练习跟踪算法，直到过程变得自动化。GCSE 考官要求精准的、逐步的解题过程——展示你的方法与得出最终答案同等重要。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply