📚 GCSE Edexcel Computer Science: Graph Algorithms | GCSE Edexcel 计算机：图算法 考点精讲
Graphs are a fundamental data structure used to model pairwise relationships between objects. In the Edexcel GCSE Computer Science specification, understanding graph representations, traversal algorithms, and basic shortest path concepts is essential for solving algorithmic problems. Graphs appear in many real-world contexts, from social networks to navigation systems. This article revises key topics: graph terminology, adjacency matrix and adjacency list, depth-first and breadth-first search, and Dijkstra's algorithm. Each section pairs English explanations with Chinese translations to strengthen bilingual understanding.
图是一种基础的数据结构，用于建模对象之间的成对关系。在 Edexcel GCSE 计算机科学大纲中，理解图的表示方法、遍历算法和基本的最短路径概念是解决算法问题的关键。图出现在许多实际场景中，从社交网络到导航系统。本文梳理核心考点：图术语、邻接矩阵与邻接表、深度优先与广度优先搜索，以及 Dijkstra 算法。每个小节均提供中英文对照，以巩固双语理解。
1. What is a Graph? | 什么是图？
A graph consists of a set of vertices (also called nodes) connected by edges. Vertices represent entities, and edges represent relationships between them. In computer science, graphs can model networks, maps, dependency links, and more. Each edge may be directed (one-way) or undirected (two-way). A graph can also be weighted, where each edge carries a numerical value representing cost, distance, or capacity. For example, in a transport network, vertices could be stations and weighted edges could represent travel times.
图由一组顶点（也称节点）以及连接它们的边组成。顶点表示实体，边表示实体之间的关系。在计算机科学中，图可以建模网络、地图、依赖关系等。每条边可以是有向（单向）或无向（双向）。图也可以带权，其中每条边带有一个数值，表示代价、距离或容量。例如，在交通网络中，顶点可以是车站，加权边可以表示通行时间。
2. Types of Graphs | 图的类型
Graphs are classified into several types: undirected graphs (edges have no direction), directed graphs (digraphs, where edges have a direction), weighted graphs (edges carry weights), and unweighted graphs. A graph can also be cyclic (contains at least one cycle) or acyclic (no cycles). Trees are a special type of acyclic connected graph. Understanding graph type is important because it affects which algorithms can be applied. GCSE questions often ask you to identify the type of graph from a diagram or to suggest an appropriate data structure.
图可分为多种类型：无向图（边没有方向）、有向图（边有方向）、加权图（边带权重）和非加权图。图也可以是循环的（至少包含一个环）或无环的（没有环）。树是一种特殊的无环连通图。理解图的类型很重要，因为它影响可使用的算法。GCSE 考题常要求你从示意图中识别图类型，或提出合适的数据结构。
3. Representing Graphs: Adjacency Matrix | 图的表示：邻接矩阵
es. The cell at row i, column j stores 1 (or the edge weight) if an edge exists from vertex i to vertex j, otherwise 0. For an undirected graph, the matrix is symmetric. Adjacency matrices allow constant-time O(1) edge existence checks, but they consume O(V²) memory, even for sparse graphs. They are suitable when the graph is dense (many edges) or when quick edge lookups are needed.
邻接矩阵是一个 V×V 的二维数组，其中 V 为顶点数。若顶点 i 到顶点 j 存在边，则第 i 行第 j 列的单元格存储 1（或边的权重），否则为 0。对于无向图，矩阵是对称的。邻接矩阵可以在常数时间 O(1) 内检查边的存在，但内存消耗为 O(V²)，即使图为稀疏图。当图稠密（边较多）或需要快速边查找时，适合使用邻接矩阵。
4. Representing Graphs: Adjacency List | 图的表示：邻接表
An adjacency list uses an array or list of lists. Each vertex has a list of its adjacent vertices (and optionally the edge weights). For a graph with V vertices and E edges, adjacency list uses O(V + E) memory, much more efficient for sparse graphs. Adding or removing edges is also fast. However, checking if an edge exists between two specific vertices may require scanning a list, taking O(V) in the worst case. In GCSE, you might be asked to construct an adjacency list from a diagram or to compare it with an adjacency matrix.
邻接表使用一个数组或列表的列表。每个顶点都有一个相邻顶点的列表（可附带边权重）。对于有 V 个顶点和 E 条边的图，邻接表的内存消耗为 O(V + E)，对于稀疏图更高效。添加或删除边也很快。然而，检查两个特定顶点之间是否存在边可能需要扫描列表，最坏情况为 O(V)。在 GCSE 中，你可能会被要求根据示意图构造邻接表，或比较邻接表与邻接矩阵。
5. Graph Traversal: Depth-First Search (DFS) | 图遍历：深度优先搜索（DFS）
Depth-First Search explores a graph by going as far as possible along each branch before backtracking. It can be implemented using a stack (explicitly or via recursion). DFS visits a starting node, marks it as visited, then recursively visits an unvisited neighbour. This process continues until a dead end is reached, then backtracks. DFS is useful for solving puzzles, topological sorting, detecting cycles, and pathfinding in mazes. The order of visited nodes depends on the starting node and the order neighbours are processed.
深度优先搜索（DFS）沿着每个分支尽可能深入，然后再回溯。它可以用栈来实现（显式或通过递归）。DFS 访问起始节点，标记为已访问，然后递归访问一个未访问的邻居。该过程持续进行，直到走到死胡同，然后回溯。DFS 常用于解谜、拓扑排序、环路检测和迷宫寻路。访问节点的顺序取决于起始节点和处理邻居的顺序。
6. Graph Traversal: Breadth-First Search (BFS) | 图遍历：广度优先搜索（BFS）
Breadth-First Search explores a graph level by level. It starts at a chosen vertex, visits all its immediate neighbours first, then moves to the neighbours of those neighbours, and so on. BFS uses a queue to keep track of the next vertex to visit. BFS guarantees the shortest path in an unweighted graph because it discovers all vertices at distance k before any at distance k+1. It is widely used in web crawling, social network 'friend' suggestions, and shortest path on grids.
广度优先搜索（BFS）按层次遍历图。它从选定的顶点开始，先访问所有直接邻居，然后访问邻居的邻居，依此类推。BFS 使用队列记录下一个要访问的顶点。BFS 能够保证在无权图中找到最短路径，因为它会在访问距离 k+1 的任何顶点之前，发现所有距离为 k 的顶点。它广泛用于网络爬虫、社交网络“好友”推荐和网格最短路径。
7. Algorithm: DFS Step-by-Step | DFS 算法逐步解析
Standard DFS algorithm (using an explicit stack or recursion):
- Choose a starting vertex and mark it as visited.
- Push the vertex onto the stack (or call recursively).
- While the stack is not empty: pop a vertex, then for each unvisited neighbour, mark it as visited and push it onto the stack.
- Repeat until the stack is empty. The order of popping defines the traversal sequence.
标准 DFS 算法（使用显式栈或递归）：
- 选择一个起始顶点，标记为已访问。
- 将该顶点压入栈中（或递归调用）。
- 当栈不为空时：弹出一个顶点，然后对于每个未访问的邻居，标记为已访问并压入栈中。
- 重复直到栈空。弹出顺序定义了遍历序列。
be A → B → D → E → C → F (if neighbours are processed left to right). Notice how D and E are explored deeply before moving to C.
示例：遍历顶点 A（连接 B、C）、B（连接 D、E）、C（连接 F）的图。从 A 开始，一种可能的 DFS 顺序为 A → B → D → E → C → F（假设按从左到右处理邻居）。注意 D 和 E 被深入探索后，才回到 C。
8. Algorithm: BFS Step-by-Step | BFS 算法逐步解析
BFS algorithm using a queue:
- Start at the chosen vertex, mark it as visited and enqueue it.
- While the queue is not empty: dequeue a vertex, then for each unvisited neighbour, mark it as visited and enqueue it.
- Continue until the queue is empty. The order of dequeuing gives the BFS order.
使用队列的 BFS 算法：
- 从选定顶点开始，标记为已访问并入队。
- 当队列不为空时：出队一个顶点，然后对于每个未访问的邻居，标记为已访问并入队。
- 继续直到队列为空。出队顺序即为 BFS 顺序。
ours at distance 1 (B, C) are visited before any at distance 2 (D, E, F). This level-order property makes BFS ideal for finding the shortest path in unweighted graphs.
使用同一个图，从 A 开始的 BFS 得到：A → B → C → D → E → F。距离 1 的所有邻居（B、C）在距离 2 的邻居（D、E、F）之前被访问。这种层次顺序特性使 BFS 非常适于查找无权图中的最短路径。
9. Shortest Path: Dijkstra's Algorithm | 最短路径：Dijkstra 算法
For weighted graphs with non-negative edge weights, Dijkstra' tially set to infinity (∞) except the start (0). It repeatedly selects the unvisited vertex with the smallest tentative distance, updates its neighbours, and marks it as visited. This process uses a priority queue for efficiency. At GCSE, you are expected to trace the algorithm on a small graph and update distance tables step by step.
对于带非负权重的图，Dijkstra 算法可以查找从起始顶点到所有其他顶点的最短路径。它维护一个到每个顶点的已知最短距离表，初始设为无穷大（∞），除起点为 0。算法反复选择尚未访问的具有最小临时距离的顶点，更新其邻居的距离，然后将其标记为已访问。为提高效率，通常使用优先队列。在 GCSE 中，要求你能在小图上追踪算法的执行，并逐步更新距离表。
| Vertex | Shortest distance from A | Previous vertex |
|---|---|---|
| A | 0 | — |
| B | 4 | A |
| C | 3 | A |
| D | 7 | B |
The table shows a possible state after running Dijkstra on a small weighted graph. You must be able to fill in such a table following the greedy choice of the unvisited vertex with minimal distance.
| 顶点 | 从 A 的最短距离 | 前驱顶点 |
|---|---|---|
| A | 0 | — |
| B | 4 | A |
| C | 3 | A |
| D | 7 | B |
该表展示了对一个小型加权图执行 Dijkstra 算法后的可能状态。你必须能够按照贪心选择未访问且距离最小的顶点的方法，填写此类表格。
10. Applications of Graph Algorithms | 图算法的应用
Graph algorithms solve many real-life problems. DFS helps in topological sorting of tasks, identifying strongly connected components, and solving mazes. BFS is the foundation of shortest path in unweighted networks and is used in peer-to-peer networks. Dijkstra's algorithm powers GPS navigation and network routing protocols like OSPF. Other graph algorithms include Prim's and Kruskal's for minimum spanning trees (useful in laying cables). In exams, you may be asked to suggest an appropriate algorithm for a given scenario and justify your choice.
图算法解决许多现实问题。DFS 可用于任务拓扑排序、识别强连通分支和迷宫求解。BFS 是无权网络最短路径的基础，也用于点对点网络。Dijkstra 算法支撑着 GPS 导航和 OSPF 等网络路由协议。其他图算法包括用于最小生成树的 Prim 和 Kruskal 算法（适用于布线）。在考试中，你可能需要根据给定场景建议合适的算法，并证明选择的合理性。
11. Exam Tips & Common Pitfalls | 考试技巧与常见错误
Common mistakes in graph algorithm questions include: confusing adjacency matrix and adjacency list memory complexities; forgetting to mark the starting vertex as visited in traversal algorithms; not maintaining a correct queue/stack order; and incorrectly updating distances in Dijkstra's algorithm. Always show your working clearly, especially distance tables and visited vertex lists. Use systematic step-by-step tracing. Double-check that you have processed all neighbours before moving on. In Dijkstra, never update a distance after a vertex is marked as visited.
图算法题目中的常见错误有：混淆邻接矩阵和邻接表的内存复杂度；在遍历算法中忘记标记起点为已访问；没有正确维护队列/栈的顺序；以及在 Dijkstra 算法中错误地更新距离。请务必清晰地展示你的解题过程，特别是距离表和已访问顶点列表。使用系统化的逐步追踪。在进入下一步前，再次检查是否已处理所有邻居。在 Dijkstra 算法中，一旦顶点标记为已访问，切勿再更新其距离。
12. Practice Questions & Summary | 练习题与总结
Try these revision questions: (1) Draw the adjacency matrix and adjacency list for a given directed graph. (2) Perform DFS and BFS starting from vertex X, writing the order of visited nodes. (3) Run Dijkstra's algorithm on a weighted graph with 5 vertices, completing a distance table. (4) Explain why BFS finds the shortest path in an unweighted graph but DFS does not. (5) Describe a real-world scenario where an adjacency list is preferred over an adjacency matrix. Answers can be checked against the concepts covered in this article.
试试这些复习题：(1) 为给定的有向图画出邻接矩阵和邻接表。(2) 从顶点 X 开始执行 DFS 和 BFS，写出访问节点顺序。(3) 对一个有 5 个顶点的加权图运行 Dijkstra 算法，完成距离表。(4) 解释为什么 BFS 能在无权图中找到最短路径而 DFS 不能。(5) 描述一个现实场景，说明为何邻接表比邻接矩阵更适合。答案可对照本文讲解的概念进行核对。
To summarise, graph algorithms are a vital part of the Edexcel GCSE Computer Science syllabus. You need to confidently represent graphs using matrices and lists, trace DFS/BFS operations, and apply Dijkstra's algorithm to small weighted graphs. Mastery of these fundamentals will not only boost your exam performance but also build a solid foundation for further study in computer science.
总而言之，图算法是 Edexcel GCSE 计算机科学大纲的重要组成部分。你需要自信地使用矩阵和列表表示图，追踪 DFS/BFS 操作，并能在小型加权图上应用 Dijkstra 算法。掌握这些基础知识不仅能提高你的考试成绩，还为计算机科学的进一步学习打下坚实基础。
Published by TutorHao | GCSE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图