📚 IB WJEC Computer Science: Graph Algorithms – Key Exam Points | IB WJEC 计算机：图算法考点精讲
Graph algorithms are a cornerstone of the IB and WJEC Computer Science syllabus, enabling us to model relationships and solve problems from social networks to GPS navigation. Mastering the fundamental representations, traversal methods, and shortest path algorithms is essential for exam success and computational thinking. This article walks you through every key concept, compares approaches, and provides step‑by‑step examples to consolidate your understanding.
图算法是IB和WJEC计算机科学课程的基石，它让我们能够对关系进行建模，并解决从社交网络到GPS导航的各种问题。掌握基本的图表示、遍历方法和最短路径算法对于考试成功和计算思维至关重要。本文将带你逐一梳理每个关键概念、比较不同方法，并给出分步示例以巩固理解。
1. Graph Basics: Vertices, Edges, and Types | 图基础：顶点、边与分类
A graph is an abstract data structure consisting of a set of vertices (or nodes) connected by edges. Graphs can be undirected, where edges have no orientation, or directed (digraphs), where each edge carries a direction from one vertex to another. Weighted graphs assign a numerical weight to each edge, representing cost, distance, or capacity. Understanding these distinctions is vital because algorithms like Dijkstra only apply to weighted graphs with non‑negative edges, while BFS works on unweighted graphs.
图是一种抽象数据结构，由一组顶点（或称节点）以及连接它们的边组成。图可以是无向的，边没有方向；也可以是有向的，每条边从一个顶点指向另一个顶点。带权图给每条边赋予一个数值权重，表示代价、距离或容量。理解这些区别至关重要，因为像 Dijkstra 这样的算法只适用于非负权重的图，而 BFS 则适用于无权图。
Additional terminology: 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. A connected graph has a path between every pair of vertices; a tree is a connected graph with no cycles. Exam questions frequently ask you to identify these properties or to explain how they influence algorithm choice.
更多术语：一条路径是由边依次连接的顶点序列；一个环是起点和终点相同的路径。连通图中任意两个顶点之间都存在路径；树是一种无环的连通图。考题常会要求你辨认这些属性，或解释它们如何影响算法选择。
2. Graph Representation: Adjacency Matrix and Adjacency List | 图的表示：邻接矩阵与邻接表
Two common ways to represent a graph in memory are the adjacency matrix and the adjacency list. An adjacency matrix is a 2D array of size V×V (V = number of vertices). The entry at row i, column j is 1 (or the edge weight) if an edge exists, otherwise 0 or ∞. This representation allows O(1) edge existence checks but uses O(V²) space, making it inefficient for sparse graphs. An adjacency list stores, for each vertex, a list of its neighbouring vertices (and possibly edge weights). It uses O(V + E) space, where E is the number of edges, and is thus preferred for sparse graphs.
在内存中表示图的两种常见方式是邻接矩阵和邻接表。邻接矩阵是一个 V×V（V 为顶点数）的二维数组。如果存在一条边，则第 i 行、第 j 列的条目为 1（或边的权重），否则为 0 或 ∞。这种表示法可以在 O(1) 时间内检查边是否存在，但需要 O(V²) 的空间，因此对稀疏图效率低下。邻接表为每个顶点存储一个邻居顶点列表（可能包括边的权重）。它的空间复杂度为 O(V + E)，其中 E 是边的数量，因此更适合稀疏图。
In exam scenarios, you may be asked to draw an adjacency matrix from a diagram or to convert between representations. Always keep in mind the trade‑offs: matrix for dense graphs and quick lookup, list for memory efficiency and faster traversal of neighbours.
在考试中，你可能需要根据图画出邻接矩阵，或在两种表示之间转换。始终牢记权衡：矩阵适用于稠密图和快速查找，邻接表更节省内存且遍历邻居更快。
3. Depth‑First Search: Algorithm and Traversal | 深度优先搜索：算法与遍历
Depth‑first search (DFS) explores a graph by going as deep as possible along one branch before backtracking. It can be implemented recursively using a stack (either the call stack or an explicit data structure). Starting from a source vertex, DFS marks the vertex as visited, then recursively visits each unvisited neighbour. The order of traversal produces a DFS tree, and the edges can be classified as tree edges or back edges (in undirected graphs).
深度优先搜索 (DFS) 沿着一条分支尽可能深入，直到无法继续时才回溯。它可以用栈（调用栈或显式数据结构）递归实现。从源顶点开始，DFS 将该顶点标记为已访问，然后递归访问每个未访问的邻居。遍历的顺序产生一棵 DFS 树，边可以分为树边或回边（在无向图中）。
A typical exam question provides a graph and asks you to simulate DFS, listing the vertices in the order they are visited. Always assume neighbours are processed in alphabetical or numerical order unless specified otherwise. DFS is the foundation for topological sorting of directed acyclic graphs, cycle detection, and path finding in maze‑like problems.
典型的考题会给出一个图，要求你模拟 DFS 并按访问顺序列出顶点。除非另有说明，应始终假定按字母或数字顺序处理邻居。DFS 是有向无环图拓扑排序、环检测以及迷宫类问题寻路的基础。
4. Breadth‑First Search: Algorithm and Traversal | 广度优先搜索：算法与遍历
Breadth‑first search (BFS) explores a graph level by level, visiting all neighbours of a vertex before moving to the next depth layer. It uses a queue to keep track of vertices to visit. Starting from the source, BFS enqueues the source, then repeatedly dequeues a vertex, marks it as visited, and enqueues all its unvisited neighbours. This guarantees that vertices are discovered in order of their distance (number of edges) from the source.
广度优先搜索 (BFS) 逐层探索图，先访问某个顶点的所有邻居，再进入下一深度层。它使用一个队列来跟踪待访问的顶点。从源点开始，BFS 将源点入队，然后反复出队一个顶点、标记为已访问并将其所有未访问的邻居入队。这样就能保证顶点按照与源点的距离（边数）顺序被发现。
BFS is uniquely suited for finding the shortest path in unweighted graphs and is used in applications like web crawling and social network analysis. When simulating BFS in an exam, clearly show the queue contents after each step and the resulting distance array.
BFS 非常适合于在无权图中寻找最短路径，并用于网页爬虫和社交网络分析等应用。在考试中模拟 BFS 时，要清晰地展示每一步后的队列内容以及最终的距离数组。
5. Comparing DFS and BFS: Use Cases | DFS 与 BFS 比较：应用场景
DFS requires less memory for deep but narrow graphs and can be implemented easily with recursion. It is used in puzzle solving, generating permutations, and analyzing strongly connected components. BFS, by contrast, consumes more memory on wide graphs but guarantees the shortest path in terms of edge count. Neither algorithm uses edge weights, so they are unsuitable for weighted shortest‑path problems without modifications.
对于深而窄的图，DFS 所需内存较少，并且可以方便地用递归实现。它用于解谜、生成排列以及分析强连通分量。相比之下，BFS 在宽图上消耗更多内存，但能保证找到边数最短的路径。两种算法都不使用边的权重，因此若不加以修改，不适合解决加权的最短路径问题。
The table below summarises their key differences; such comparisons frequently appear in multiple‑choice and structured questions.
下表总结了它们的主要区别；这类比较经常出现在选择题和结构化试题中。
| Feature | DFS | BFS |
|---|---|---|
| Data structure | Stack (implicit or explicit) | Queue |
| Traversal order | Depth‑first (branch then backtrack) | Level‑by‑level (breadth‑first) |
| Shortest path (unweighted) | Not guaranteed | Yes, finds minimum edge count |
| Space complexity | O(V) for recursion stack | O(V) for queue, but can be larger in wide graphs |
6. Dijkstra’s Shortest Path Algorithm | Dijkstra 最短路径算法
Dijkstra’s algorithm computes the shortest path from a single source to all other vertices in a weighted graph with non‑negative edge weights. It maintains a set of unvisited vertices and a distance array initialised to infinity, except for the source which is set to 0. At each step, the unvisited vertex with the smallest tentative distance is selected (the “greedy” choice), and the distances to its neighbours are updated if a shorter path is found via the current vertex. This relaxation process continues until all vertices have been visited.
Dijkstra 算法用于在具有非负边权的带权图中计算从单一源点到所有其他顶点的最短路径。它维护一个未访问顶点集合和一个初始化为无穷大的距离数组，源点距离设为 0。每一步选择未访问顶点中临时距离最小的那个（“贪心”选择），并检查通过当前顶点是否能得到更短的邻居路径，若是则更新邻居的距离。这一松弛过程持续到所有顶点都被访问为止。
Understanding the algorithm is not enough for the exam; you must be able to trace it on a given graph using a table of distances and a priority queue (or manual min‑selection). Remember that Dijkstra fails if any edge weight is negative – the algorithm may produce incorrect results or loop indefinitely.
对于考试而言，光理解算法还不够；你必须能够利用距离表和优先队列（或手动选择最小值）在给定图上追踪算法的执行过程。请记住：只要存在负边权，Dijkstra 算法就会失败——结果可能不正确或陷入无限循环。
7. Dijkstra Worked Example | Dijkstra 逐步示例
Consider the following directed weighted graph with vertices A (source), B, C, D, and E. Edges: A→B (4), A→C (2), B→C (1), B→D (5), C→D (8), C→E (10), D→E (2). We will trace Dijkstra to find the shortest paths from A.
考虑以下有向带权图，顶点为 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)。我们将追踪 Dijkstra 以找出从 A 出发的最短路径。
| Step | Visited Vertex | Distance Array [A,B,C,D,E] | Previous Vertex |
|---|---|---|---|
| Initial | – | [0, ∞, ∞, ∞, ∞] | [-, -, -, -, -] |
| 1 | A (dist=0) | [0, 4, 2, ∞, ∞] | [-, A, A, -, -] |
| 2 | C (dist=2) | [0, 4, 2, 10, 12] (via C: D=2+8=10, E=2+10=12) | [-, A, A, C, C] |
| 3 | B (dist=4) | [0, 4, 2, min(10,4+5)=9, 12] (D updated to 9) | [-, A, A, B, C] |
| 4 | D (dist=9) | [0, 4, 2, 9, min(12,9+2)=11] (E updated to 11) | [-, A, A, B, D] |
| 5 | E (dist=11) | [0, 4, 2, 9, 11] | [-, A, A, B, D] |
The final shortest paths: A→B (4), A→C (2), A→C→B? Actually B is reached directly with 4, not via C. A→D: A→B→D (9), A→E: A→B→D→E (11). This tabular approach is exactly what examiners expect.
最终最短路径：A→B（4），A→C（2），A→D：A→B→D（9），A→E：A→B→D→E（11）。这种表格化的追踪方式正是考官所期望的。
8. A* Search Algorithm: Heuristics and Efficiency | A* 搜索算法：启发式与效率
A* extends Dijkstra by incorporating a heuristic function h(n) that estimates the cost from vertex n to the goal. The algorithm evaluates vertices based on f(n) = g(n) + h(n), where g(n) is the actual cost from the start to n. If h(n) is admissible (never overestimates) and consistent, A* guarantees optimality while often expanding far fewer vertices than Dijkstra. This makes it a powerful tool for pathfinding in games, robotics, and map applications.
A* 算法在 Dijkstra 的基础上引入了一个启发式函数 h(n)，用来估算从顶点 n 到目标的代价。算法根据 f(n) = g(n) + h(n) 评估顶点，其中 g(n) 是从起点到 n 的实际代价。如果 h(n) 是可采纳的（从不高估）且一致的，A* 能保证最优解，同时通常比 Dijkstra 扩展的顶点数少得多。这使它成为游戏、机器人及地图应用寻路的强大工具。
For IB HL and some WJEC specifications, you need to explain why A* is more efficient than Dijkstra on large graphs – the heuristic focuses the search towards the goal. You might also be asked to demonstrate a simple A* simulation with a given heuristic table. Always check that the heuristic is admissible for the graph provided.
对于 IB HL 和部分 WJEC 大纲，你需要解释为什么 A* 在大图上比 Dijkstra 更高效——启发式让搜索聚焦于目标方向。你可能还需要根据给定的启发式表格演示简单的 A* 模拟过程。务必检查启发式对给定图是否可采纳。
9. Applications of Graph Algorithms | 图算法的应用
Graph algorithms underpin many real‑world technologies. BFS and DFS are used in network routing protocols, web crawling, and garbage collection (mark‑and‑sweep). Dijkstra and A* lie at the heart of GPS navigation systems, logistics route planning, and even circuit board design. Social networks leverage graph partitioning and community detection algorithms based on connectivity analysis. Exam questions often contextualise a problem to test your ability to select the right algorithm.
图算法是许多现实技术的基础。BFS 和 DFS 用于网络路由协议、网页爬虫以及垃圾回收（标记‑清除）。Dijkstra 和 A* 是 GPS 导航系统、物流路径规划乃至电路板设计的核心。社交网络利用基于连通性分析的图划分和社区发现算法。考试题目往往将问题放在具体情境中，以测试你选择合适的算法的能力。
When faced with an application scenario, first identify whether the graph is weighted, whether negative weights are present, and whether you need single‑source or all‑pairs shortest paths. Then match the algorithm: unweighted shortest path → BFS; weighted non‑negative → Dijkstra; weighted with heuristic → A*; cycle detection or maze solving → DFS.
遇到应用场景时，首先确定图是否带权、是否存在负权重，以及你需要的是单源还是所有点对的最短路径。然后匹配算法：无权最短路径 → BFS；非负加权 → Dijkstra；带启发式的加权 → A*；环检测或迷宫求解 → DFS。
10. Common Pitfalls and Exam Tips | 常见错误与应考技巧
One frequent mistake is forgetting to initialise distances to infinity, leading to incorrect comparisons. In Dijkstra, always mark a vertex as visited after extracting it from the priority queue, otherwise you may relax its edges multiple times. When tracing BFS/DFS, clearly label visited vertices on the graph and note the queue/stack contents at each stage. For A*, never skip the heuristic admissibility check – using an overestimating heuristic can lead to a suboptimal path.
一个常见错误是忘记将距离初始化为无穷大，从而导致比较错误。在 Dijkstra 中，务必在从优先队列中取出一个顶点后将其标记为已访问，否则可能会多次松弛它的边。在追踪 BFS/DFS 时，要在图上清楚标示已访问的顶点，并记录每一阶段的队列/栈内容。对于 A*，切勿省略启发式可采纳性检查——使用高估的启发式可能导致次优路径。
A final exam tip: practice drawing the distance table for Dijkstra and the traversal tree for DFS/BFS. These are high‑mark questions that reward clear working. Time management is crucial; if a trace becomes messy, restart the table on a fresh page. Use the standard notation (∞, dist[v], prev[v]) exactly as shown in mark schemes.
最后一条应考建议：多练习绘制 Dijkstra 的距离表和 DFS/BFS 的遍历树。这些都是高分题，清晰的步骤能够赢得分数。时间管理至关重要；如果追踪过程变得凌乱，不妨重新在新的一页上绘制表格。请使用标准符号（∞, dist[v], prev[v]），与评分方案完全一致。
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