📚 IGCSE WJEC Computer Science: Graph Algorithms – Exam Essentials | IGCSE WJEC 计算机：图算法考点精讲
Graph algorithms are a fundamental topic in the IGCSE WJEC Computer Science specification. They test your ability to model real-world networks such as social media, transport systems, and internet routing. Mastering graph representations (adjacency matrix and list), traversal methods (BFS and DFS), and the shortest path algorithm (Dijkstra) will help you tackle both theory and practical questions with confidence. This guide covers all key concepts, step-by-step examples, and exam strategies you need to excel.
图算法是 IGCSE WJEC 计算机科学大纲中的基础主题。它考察你对现实世界网络（如社交媒体、交通系统和互联网路由）建模的能力。掌握图表示（邻接矩阵和邻接表）、遍历方法（广度优先搜索和深度优先搜索）以及最短路径算法（迪杰斯特拉算法）将帮助你自信地应对理论和实践问题。本指南涵盖所有关键概念、分步示例和考试策略，助你取得优异成绩。
1. Graph Basics: Vertices and Edges | 图基础：顶点与边
A graph G consists of a set of vertices V and a set of edges E. Each edge connects a pair of vertices, representing a relationship. A simple graph has no loops and no multiple edges between the same pair. The order of a graph is the number of vertices, and the size is the number of edges. The degree of a vertex is the count of edges incident to it; for a directed graph, we distinguish between in-degree (incoming edges) and out-degree (outgoing edges).
图 G 由顶点集 V 和边集 E 组成。每条边连接一对顶点，表示一种关系。简单图没有自环，也没有重复边。图的阶是顶点的数量，大小是边的数量。顶点的度是指与该顶点相连的边的数量；对于有向图，区分入度（进入的边）和出度（离开的边）。
A path is a sequence of distinct vertices where each consecutive pair is adjacent. A cycle is a path that starts and ends at the same vertex, with no other repetitions. Understanding these basic terms is vital because all graph algorithms manipulate vertices and edges in structured ways.
路径是一系列不重复的顶点，其中每一对连续顶点都是相邻的。回路是起点和终点相同且没有其他重复顶点的路径。理解这些基本术语至关重要，因为所有图算法都是以结构化的方式操纵顶点和边。
2. Directed vs Undirected and Weighted Graphs | 有向、无向与加权图
In an undirected graph, edges have no orientation: an edge {u, v} implies a two-way relationship, like a friendship. In a directed graph (digraph), each edge has a direction, shown as (u, v) meaning 'from u to v'; this models one-way streets or follower relationships. A graph can be weighted or unweighted. In a weighted graph, each edge carries a numerical label, often called cost, distance, or capacity.
在无向图中，边没有方向：边 {u, v} 表示双向关系，如同友谊。在有向图（有向图）中，每条边都有方向，表示为 (u, v) 意味着“从 u 到 v”；这模拟了单行道或关注关系。图可以加权或无加权。在加权图中，每条边带有一个数值标签，通常称为代价、距离或容量。
For WJEC exams, you may be given a diagram, a set of connections, or a table and asked to identify whether the graph is directed/undirected and weighted/unweighted. Pay attention to arrowheads and edge labels. When an edge has no arrow, assume it is undirected. When all edges carry values, the graph is weighted; this will be needed for Dijkstra's algorithm.
在 WJEC 考试中，你可能会得到一张图、一组连接或一个表格，并被要求判断图是有向/无向还是加权/无加权的。注意箭头和边上的标签。当边没有箭头时，假定为无向。当所有边都带有数值时，图就是加权的；迪杰斯特拉算法需要用到加权图。
3. Representing Graphs: Adjacency Matrix | 图的表示：邻接矩阵
n j is 1 (or the weight) if an edge exists from vertex i to vertex j, and 0 otherwise. For undirected graphs, the matrix is symmetric. This representation allows O(1) edge existence checks but uses O(V²) memory, which is inefficient for sparse graphs.
邻接矩阵使用大小为 V×V 的二维数组。如果存在从顶点 i 到顶点 j 的边，则第 i 行第 j 列的项为 1（或权重），否则为 0。对于无向图，矩阵是对称的。这种表示法可以在 O(1) 时间内检查边是否存在，但使用 O(V²) 内存，对于稀疏图效率低下。
ph with vertices 1, 2, 3, 4 and edges (1→2), (2→3), (3→4), (4→1). The adjacency matrix is:
示例：考虑一个有向图，顶点为 1, 2, 3, 4，边为 (1→2), (2→3), (3→4), (4→1)。其邻接矩阵如下：
| 1 | 2 | 3 | 4 | |
| 1 | 0 | 1 | 0 | 0 |
| 2 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 0 | 1 |
| 4 | 1 | 0 | 0 | 0 |
In exams, you may need to construct a matrix from a diagram or vice versa. Always label the rows and columns clearly and check for symmetry if the graph is undirected.
在考试中，你可能需要根据图构建矩阵，或反之。始终清晰地标记行和列，如果图是无向的，要检查对称性。
4. Representing Graphs: Adjacency List | 图的表示：邻接表
The adjacency list stores an array of lists. Each index corresponds to a vertex, and its list contains the neighbours (or outgoing neighbours for a directed graph). For weighted graphs, the list stores pairs of (neighbour, weight). This representation is memory-efficient for sparse graphs, using O(V+E) space, and is often more convenient for traversal algorithms.
邻接表存储一个列表数组。每个索引对应一个顶点，其列表包含邻居（对于有向图则是出邻居）。对于加权图，列表存储（邻居，权重）对。这种表示法对于稀疏图内存效率高，使用 O(V+E) 空间，并且通常更方便遍历算法。
Using the same directed graph example, the adjacency list would be: 1: [2] 2: [3] 3: [4] 4: [1]
使用同一个有向图示例，邻接表为： 1: [2] 2: [3] 3: [4] 4: [1]
When asked to draw an adjacency list, list vertices in order and show all outgoing edges. If the graph is undirected, each edge appears in two lists. Understand that adding or removing an edge is O(1) in a matrix but may require traversal in a list, while iterating over neighbours is faster with a list.
当要求绘制邻接表时，按顺序列出所有顶点并展示所有出边。如果图是无向的，每条边会出现在两个列表中。要理解，在矩阵中添加或删除边是 O(1)，但在列表中可能需要遍历；而迭代邻居时列表更快。
5. Depth-First Search (DFS) | 深度优先搜索 (DFS)
Depth-first search explores as far as possible along a branch before backtracking. It uses a stack – either an explicit stack or recursion (call stack). The algorithm starts at a given vertex, marks it visited, and then recursively visits an unvisited neighbour until all reachable vertices are visited. The order of visitation depends on the iteration order of neighbours.
深度优先搜索沿着一个分支尽可能深入探索，然后回溯。它使用栈——显式栈或递归（调用栈）。算法从给定顶点开始，将其标记为已访问，然后递归地访问一个未访问的邻居，直到所有可达的顶点都被访问。访问顺序取决于邻居的迭代顺序。
Consider the undirected graph: A-B, A-C, B-D, C-E. Starting DFS at A: visit A. Neighbours are B and C. Suppose B is chosen first: visit B, then visit its unvisited neighbour D. D has no unvisited neighbours, so backtrack to B; B done, backtrack to A. Now visit C, then E. Final DFS order: A, B, D, C, E. The process can be traced by drawing a DFS tree.
考虑无向图：A-B, A-C, B-D, C-E。从 A 开始 DFS：访问 A。邻居是 B 和 C。假设先选 B：访问 B，然后访问其未访问邻居 D。D 没有未访问邻居，回溯到 B；B 完成，回溯到 A。现在访问 C，然后 E。最终 DFS 顺序：A, B, D, C, E。可以通过绘制 DFS 树来追踪过程。
For WJEC, you should be able to simulate DFS on a given graph, showing the stack content and the visited list at each step. DFS is used in maze solving, topological sorting, and cycle detection.
对于 WJEC，你应该能够模拟给定图上的 DFS，显示每一步的栈内容和已访问列表。DFS 用于迷宫求解、拓扑排序和环路检测。
6. Breadth-First Search (BFS) | 广度优先搜索 (BFS)
Breadth-first search explores all neighbours of a vertex before moving to the next level. It uses a queue to manage the frontier. Starting at a source vertex, mark it visited and enqueue it. While the queue is not empty, dequeue a vertex, and for each unvisited neighbour, mark it visited and enqueue it. This guarantees that vertices are visited in increasing order of distance from the source.
广度优先搜索在移动到下一层之前，先探索顶点的所有邻居。它使用队列管理前沿。从源顶点开始，标记已访问并入队。当队列不为空时，出队一个顶点，对于每个未访问的邻居，标记已访问并入队。这保证了顶点按距源点距离递增的顺序被访问。
e E → [D, E]. Dequeue D (no new), dequeue E (no new). BFS order: A, B, C, D, E. This level-by-level behaviour is ideal for finding the shortest path in an unweighted graph.
使用相同的图 A-B, A-C, B-D, C-E，从 A 进行 BFS：队列 = [A]。出队 A，将 B 和 C 入队 → 队列 [B, C]。出队 B，将 D 入队 → [C, D]。出队 C，将 E 入队 → [D, E]。出队 D（无新顶点），出队 E（无新顶点）。BFS 顺序：A, B, C, D, E。这种逐层行为非常适合于在无权图中寻找最短路径。
Examiners often ask for BFS traversal order and the state of the queue after each step. Practice keeping a table with columns for step, dequeued vertex, queue contents, and visited list. BFS is used in web crawling, social network friend suggestions, and GPS unweighted routing.
考官经常要求给出 BFS 遍历顺序以及每一步后队列的状态。练习制作一个表格，列包括步骤、出队顶点、队列内容和已访问列表。BFS 用于网络爬虫、社交网络好友推荐和 GPS 无加权路径规划。
7. Shortest Path Problem and Dijkstra's Algorithm | 最短路径问题与迪杰斯特拉算法
In a weighted graph, the shortest path problem asks for the path with the smallest total weight between two vertices. Dijkstra's algorithm solves this for graphs with non-negative edge weights. It maintains a set of visited vertices and a distance array. Initially, the source distance is 0, all others are infinite. At each step, it selects the unvisited vertex with the smallest distance, marks it visited, and updates its neighbours' distances using the relaxation formula:
在加权图中，最短路径问题要求找到两个顶点之间总权重最小的路径。迪杰斯特拉算法解决了边权非负的图的最短路径问题。它维护一个已访问顶点集和一个距离数组。初始时，源点距离为 0，其余为无穷大。每一步，选择未访问顶点中距离最小的那个，标记为已访问，并使用松弛公式更新其邻居的距离：
if dist[u] + weight(u, v) < dist[v] then dist[v] = dist[u] + weight(u, v)
This greedy approach ensures that once a vertex is visited, its shortest distance is final. The algorithm terminates when all vertices are visited or the target is reached.
这种贪心策略确保一旦一个顶点被访问，其最短距离就是最终的。当所有顶点都被访问或达到目标顶点时，算法终止。
WJEC papers often require a step-by-step execution using a table with columns for vertex, shortest distance from source, and previous vertex. You must be able to reconstruct the shortest path by backtracking from the target using the 'previous' records.
WJEC 试卷通常要求通过一个表格逐步执行，表格列包括顶点、从源点的最短距离和前驱顶点。你必须能够使用“前驱”记录从目标回溯重建最短路径。
8. Step-by-Step Dijkstra Walkthrough | 迪杰斯特拉算法逐步演练
8, C→E: 10, D→E: 2. Find the shortest path from A to E. No negative weights, all directed.
示例加权图：顶点 A, B, C, D, E。边及权重：A→B: 4, A→C: 2, B→C: 1, B→D: 5, C→D: 8, C→E: 10, D→E: 2。求从 A 到 E 的最短路径。无负权，全部有向。
Initialise dist: A=0, others=∞. Prev: all null. Unvisited: {A,B,C,D,E}.
初始化距离：A=0，其余=∞。前驱：全部为空。未访问集：{A,B,C,D,E}。
e B: dist[B] = min(∞, 0+4)=4, prev B=A. Update C: min(∞, 0+2)=2, prev C=A. Mark A visited.
第1步：选择 A (dist=0)。更新 B：dist[B] = min(∞, 0+4)=4，prev B=A。更新 C：min(∞, 0+2)=2，prev C=A。标记 A 已访问。
D] = min(∞, 2+8)=10, prev D=C. For E: dist[E] = min(∞, 2+10)=12, prev E=C. Mark C visited.
第2步：未访问中距离最小的是 C (2)。选择 C。邻居：D, E。对于 D：dist[D] = min(∞, 2+8)=10，prev D=C。对于 E：dist[E] = min(∞, 2+10)=12，prev E=C。标记 C 已访问。
4). Pick B. Neighbour C already visited, D not visited: dist[D] = min(10, 4+5)=9 (improved!), prev D now B. Mark B visited.
第3步：未访问中距离最小的是 B (4)。选择 B。邻居 C 已访问，D 未访问：dist[D] = min(10, 4+5)=9（改善！），prev D 现在为 B。标记 B 已访问。
t dist is D (9). Pick D. Neighbour E: dist[E] = min(12, 9+2)=11, prev E=D. Mark D visited.
第4步：未访问中距离最小的是 D (9)。选择 D。邻居 E：dist[E] = min(12, 9+2)=11，prev E=D。标记 D 已访问。
ns, dist=11. Stop. Shortest path from A to E is A→C→D→E with total weight 11. Backtrack: E ← D ← C ← A.
第5步：只剩下 E，dist=11。停止。从 A 到 E 的最短路径是 A→C→D→E，总权重 11。回溯：E ← D ← C ← A。
Always present your work in a clear table format during exams. Double-check for any possible shorter path through unvisited vertices before finalising each step.
考试时始终以清晰的表格格式展示你的工作。在完成每一步之前，再次检查通过未访问顶点是否可能存在更短的路径。
9. Real-World Applications of Graph Algorithms | 图算法的实际应用
Graph algorithms are not just theoretical; they power many everyday technologies. BFS is used in peer-to-peer networks to find all nodes within a certain distance and in social networks to suggest friends of friends. DFS is used in puzzle solving (e.g., Sudoku solvers) and in detecting cycles in dependency graphs. Dijkstra's algorithm is the backbone of GPS navigation systems for finding the quickest route, and variants handle real-time traffic updates.
图算法不仅仅是理论，它们驱动着许多日常技术。BFS 用于点对点网络中查找一定距离内的所有节点，以及社交网络中
Published by TutorHao | IGCSE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图