📚 IGCSE Edexcel Computer Science: Graph Algorithms | IGCSE Edexcel 计算机：图算法 考点精讲
Graph algorithms are a fundamental part of the IGCSE Edexcel Computer Science specification, focusing on the ways we can model, traverse, and analyse networks of connected data. From social networks and transport maps to the internet itself, graphs provide a powerful abstraction for solving real‑world problems. In this article, we break down every key concept you need to master: graph representations, depth‑first and breadth‑first search, shortest path algorithms, and essential exam tips. By the end, you will be able to confidently trace through algorithms, compare their efficiencies, and apply them to unfamiliar scenarios.
图算法是 IGCSE Edexcel 计算机科学课程的核心内容之一，主要考察我们如何对相互连接的数据网络进行建模、遍历和分析。从社交网络、交通线路图到互联网本身，图提供了一种解决现实问题的强大抽象。本文详细拆解了你需要掌握的每一个关键概念：图的表示方式、深度优先搜索和广度优先搜索、最短路径算法以及必备的考试技巧。读完本文后，你将能够自信地追踪算法执行过程、比较它们的效率，并将它们应用于陌生场景。
1. What Is a Graph? | 什么是图？
A graph is an abstract data structure consisting of a set of vertices (also called nodes) and a set of edges that connect pairs of vertices. Edges can be directed (with an arrow indicating a one‑way relationship) or undirected (bidirectional). They may also carry weights to represent costs, distances, or capacities. Graphs are used to model networks such as road systems, computer networks, hyperlinks between web pages, and dependencies in project planning.
图是一种抽象数据结构，由一组顶点（也称为节点）和连接顶点对的边集合组成。边可以是有向的（用箭头表示单向关系）或无向的（双向）。边还可以携带权重，用来表示代价、距离或容量。图被广泛用于对网络进行建模，例如道路系统、计算机网络、网页之间的超链接以及项目规划中的依赖关系。
Key terminology: a 'neighbour' of a vertex is any vertex directly connected by an edge. The 'degree' of a vertex is the number of edges incident to it. A 'path' is a sequence of vertices where each adjacent pair is connected. A 'cycle' is a path that starts and ends at the same vertex without repeating edges.
关键术语：顶点的“邻居”是指通过一条边直接相连的任何顶点。顶点的“度”是与该顶点相关联的边的数量。“路径”是一系列顶点，其中每一对相邻顶点都由边连接。“环”是一条起点和终点为同一顶点且不重复边界的路径。
2. Representing Graphs | 图的表示
D array of size V × V (where V is the number of vertices). If an edge exists from vertex i to vertex j, the cell at row i, column j contains 1 (or the weight of the edge); otherwise it contains 0. This structure allows O(1) lookup time to check if an edge exists, but it uses O(V²) memory, which is inefficient for sparse graphs.
在考试中，你很可能会遇到在内存中存储图的两种主要方式：邻接矩阵和邻接表。邻接矩阵是一个大小为 V × V 的二维数组（V 为顶点数量）。如果存在从顶点 i 到顶点 j 的边，则第 i 行第 j 列的单元格包含 1（或边的权重）；否则为 0。这种结构可以在 O(1) 时间内检查边是否存在，但它占用 O(V²) 内存，对于稀疏图而言效率较低。
An adjacency list stores each vertex alongside a list of its neighbouring vertices (or pairs of neighbour and weight). It is more memory‑efficient for sparse graphs because it only stores existing edges. However, checking whether a specific edge exists can take O(k) time, where k is the average degree. Most real‑world networks are sparse, so adjacency lists are common in practice.
邻接表存储每个顶点及其邻居顶点列表（或邻居-权重对）。对于稀疏图，它更节省内存，因为它只存储实际存在的边。然而，检查某条特定边是否存在可能需要 O(k) 时间，其中 k 是平均度数。大多数现实网络是稀疏的，因此邻接表在实践中非常常见。
3. Graph Traversal Algorithms | 图的遍历算法
Traversal means visiting every vertex in a graph in a systematic way. The two fundamental traversal algorithms are depth‑first search (DFS) and breadth‑first search (BFS). Both start from a given source vertex and explore all reachable vertices, but they differ in the order of exploration. Understanding their mechanisms is essential for solving maze problems, finding connected components, and building the foundation of more advanced algorithms.
遍历是指以一种系统化的方式访问图中的每一个顶点。两种基本的遍历算法是深度优先搜索（DFS）和广度优先搜索（BFS）。它们都从一个给定的源顶点开始，探索所有可达顶点，但它们的探索顺序不同。理解它们的机制对于解决迷宫问题、寻找连通分量以及为更高级的算法打下基础至关重要。
In IGCSE questions, you are frequently asked to trace DFS and BFS on a given graph and to identify the order in which vertices are visited, or to write simple pseudocode illustrating the use of a stack or queue. Always read the question carefully: sometimes a specific visiting order is required (e.g. alphabetical, numerical) when neighbours are processed.
在 IGCSE 考题中，经常要求你在给定的图上追踪 DFS 和 BFS，确定顶点的访问顺序，或编写简单的伪代码来说明栈或队列的使用。务必仔细读题：有时在处理邻居时要求按特定顺序（例如字母顺序、数值顺序）访问。
4. Depth‑First Search (DFS) | 深度优先搜索
DFS explores a graph by going as deep as possible along one branch before backtracking. It uses a stack data structure (either explicitly, or implicitly via recursion). Starting from the source, DFS pushes the current vertex onto the stack, marks it as visited, and recursively visits an unvisited neighbour. When no unvisited neighbours remain, it backtracks by popping from the stack.
DFS 通过尽可能沿一条分支深入探索到底，然后再回溯。它使用栈数据结构（显式使用或通过递归隐式使用）。从源点开始，DFS 将当前顶点压入栈中，标记为已访问，并递归访问一个未访问的邻居。当没有未访问的邻居时，它通过弹栈进行回溯。
Typical DFS pseudocode (iterative):
function DFS(start):
create empty stack S
push start onto S
while S is not empty:
current = S.pop()
if current not visited:
mark current as visited
for each neighbour of current:
if neighbour not visited: push neighbour onto S
典型的 DFS 伪代码（迭代版）：
函数 DFS(start):
创建空栈 S
将 start 压入 S
当 S 非空时：
current = S.pop()
如果 current 未访问：
标记 current 为已访问
对于 current 的每个邻居：
如果邻居未访问：将邻居压入 S
5. Breadth‑First Search (BFS) | 广度优先搜索
BFS explores a graph level by level. Starting from the source, it visits all neighbours first (the first 'layer'), then the neighbours of those neighbours, and so on. BFS uses a queue (FIFO) to manage the frontier. Each vertex is enqueued, then dequeued and processed; its unvisited neighbours are added to the back of the queue.
BFS 按层次逐层探索图。从源点开始，它先访问所有邻居（第一“层”），然后访问这些邻居的邻居，依此类推。BFS 使用队列（先进先出）来管理探索边界。每个顶点先入队，然后出队并被处理；其未访问的邻居被添加到队列末尾。
BFS pseudocode:
function BFS(start):
create empty queue Q
enqueue start into Q
mark start as visited
while Q is not empty:
current = Q.dequeue()
for each neighbour of current:
if neighbour not visited:
mark neighbour as visited
enqueue neighbour into Q
BFS 伪代码：
函数 BFS(start):
创建空队列 Q
将 start 入队 Q
标记 start 为已访问
当 Q 非空时：
current = Q.dequeue()
对于 current 的每个邻居：
如果邻居未访问：
标记邻居为已访问
将邻居入队 Q
6. Comparing DFS and BFS | DFS 与 BFS 的比较
DFS and BFS both have a time complexity of O(V + E) for an adjacency list, as each vertex and edge is processed at most once. They differ mainly in order of vertex discovery and memory usage. DFS uses a stack and can be simpler to implement using recursion, while BFS uses a queue. DFS may use less memory on deep, narrow graphs, but can suffer from stack overflow in recursive implementations; BFS can require large memory for wide graphs as it stores an entire layer at once.
对于邻接表，DFS 和 BFS 的时间复杂度均为 O(V + E)，因为每个顶点和每条边最多处理一次。它们的主要区别在于顶点发现的顺序和内存使用。DFS 使用栈，通过递归实现会更简单；BFS 使用队列。DFS 在深而窄的图上可能使用更少内存，但递归实现时可能发生栈溢出；BFS 在宽图上可能需要大量内存，因为它一次存储整个层级。
BFS finds the shortest path in an unweighted graph (by number of edges), while DFS does not guarantee the shortest path. DFS is useful for tasks like topological sorting, detecting cycles, and exploring all possibilities (e.g. maze solving). BFS is used in social networking 'friends at distance k' queries, web crawling, and any scenario where the minimal number of steps matters.
BFS 在无权图中可以找到最短路径（按边数计算），而 DFS 则不能保证最短路径。DFS 适用于拓扑排序、检测环以及探索所有可能性（例如走迷宫）等任务。BFS 常用于社交网络中的“距离为 k 的好友”查询、网络爬虫以及任何关注最少步数的场景。
7. Applications of DFS and BFS | DFS 和 BFS 的应用
In your IGCSE exam, you should be able to recognise practical uses of graph traversal. Examples include: finding whether a path exists between two airports (DFS or BFS), printing all web pages reachable from a homepage (BFS for levels), checking if a maze has a solution (DFS), and discovering connected components in a network (both, by iterating over unvisited vertices). These applications reinforce why choosing the correct algorithm matters.
在 IGCSE 考试中，你应能识别图遍历的实际用途。示例包括：寻找两个机场之间是否存在路径（DFS 或 BFS）、打印从主页可到达的所有网页（BFS 按层级）、检查迷宫是否有解（DFS）以及发现网络中的连通分量（两者均可，通过迭代未访问顶点）。这些应用强化了为什么选择合适的算法至关重要。
Always link the algorithm to the underlying data structure: stack‑based DFS naturally mirrors backtracking problems, while queue‑based BFS mirrors level‑order processing. A common exam scenario gives you a graph and asks you to simulate the steps, ensuring you follow the required order when selecting neighbours.
请务必将算法与其底层数据结构联系起来：基于栈的 DFS 自然地反映了回溯问题，而基于队列的 BFS 则反映了层级顺序处理。常见的考试情境是给你一个图并要求你模拟步骤，确保你在选择邻居时遵循要求的顺序。
8. The Shortest Path Problem | 最短路径问题
Many real‑world problems involve finding the fastest, cheapest, or shortest route between two vertices in a weighted graph. This is known as the shortest path problem. If the graph is unweighted, BFS already provides the shortest path in terms of edge count. For weighted graphs, more sophisticated algorithms like Dijkstra's algorithm are needed.
许多现实问题都涉及在加权图中寻找两个顶点之间最快、最便宜或最短的路线。这就是最短路径问题。如果图是无权的，BFS 已经可以按照边数提供最短路径。对于加权图，则需要更复杂的算法，如 Dijkstra 算法。
The Edexcel specification expects you to understand and trace Dijkstra's algorithm on a given weighted graph, recording the working values at each step. You must be able to explain how the algorithm progressively builds the shortest path tree by expanding the currently closest unvisited vertex.
Edexcel 大纲要求你理解并能够在给定的加权图上追踪 Dijkstra 算法，记录每一步的工作值。你必须能够解释该算法如何通过扩展当前最近的未访问顶点来逐步构建最短路径树。
9. Dijkstra's Algorithm | 迪杰斯特拉算法
Dijkstra's algorithm solves the single‑source shortest path problem for graphs with non‑negative weights. It maintains two sets of vertices: visited (for which the final shortest distance is known) and unvisited. Initially, the distance to the source is set to 0, and to all others as infinity. At each step, the unvisited vertex with the smallest tentative distance is selected, marked as visited, and its neighbours' distances are updated if a shorter path is found through it.
Dijkstra 算法解决了具有非负权重的图的单源最短路径问题。它维护两个顶点集合：已访问（已确定最终最短距离的顶点）和未访问。初始时，到源点的距离设为 0，到其他所有顶点的距离设为无穷大。每一步，选择未访问顶点中暂定距离最小的顶点，标记为已访问，如果经由该顶点能找到更短路径，则更新其邻居的距离。
The algorithm is summarised as:
function Dijkstra(Graph, source):
dist[source] = 0
for each vertex v except source: dist[v] = ∞
create empty set of visited
while there are unvisited vertices:
u = unvisited vertex with smallest dist[u]
add u to visited
for each neighbour v of u not visited:
alt = dist[u] + weight(u, v)
if alt < dist[v]: dist[v] = alt
算法总结如下：
函数 Dijkstra(图, 源点):
dist[源点] = 0
对于除源点外的每个顶点 v：dist[v] = ∞
创建空的已访问集合
当存在未访问顶点时：
u = 未访问顶点中 dist[u] 最小的
将 u 加入已访问
对于 u 的每个未访问邻居 v：
alt = dist[u] + 权重(u, v)
如果 alt < dist[v]：将 dist[v] 设为 alt
10. Dijkstra's Algorithm Worked Example | Dijkstra 算法实例演示
Consider a simple graph with vertices A, B, C, D, E. Edges: A–B (4), A–C (2), B–C (1), B–D (5), C–D (8), C–E (10), D–E (2). Source is A. We trace Dijkstra step‑by‑ Add C, update B=min(4, 2+1)=3, D=min(∞, 2+8)=10, E=min(∞, 2+10)=12. Next: B (3). Update D=min(10, 3+5)=8. Then D (8): update E=min(12, 8+2)=10. Finally E (10). Shortest paths from A: A→A=0, A→C=2, A→B=3, A→D=8, A→E=10.
考虑一个简单的图，顶点为 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。我们逐步追踪 Dijkstra 算法，维护距离表。初始：dist[A]=0，其他为 ∞。未访问中最小：A。加入 A，更新 B=4，C=2。下一个未访问最小：C (2)。加入 C，更新 B=min(4, 2+1)=3，D=min(∞, 2+8)=10，E=min(∞, 2+10)=12。下一个：B (3)。更新 D=min(10, 3+5)=8。然后 D (8)：更新 E=min(12, 8+2)=10。最后 E (10)。从 A 出发的最短路径：A→A=0，A→C=2，A→B=3，A→D=8，A→E=10。
In the exam, you are often asked to fill in such a table or to list the final distances and shortest paths. Show your workings clearly, and remember to cross out old values when they are updated, replacing them with the new smaller distances.
在考试中，常常要求你填写这样的表格，或者列出最终距离和最短路径。清晰地展示你的计算过程，并记得在旧值被更新时将其划掉，用新的更小距离替换。
11. A* Search Algorithm Overview | A* 搜索算法概述
While Dijkstra explores evenly in all directions, A* (A‑ A* evaluates vertices using the function f(n) = g(n) + h(n), where g(n) is the actual cost from the start to vertex n, and h(n) is a heuristic estimate of the cost from n to the goal. A* expands vertices with the lowest f(n) first.
Dijkstra 算法均匀地向所有方向扩展，而 A*（A 星）算法使用启发式函数引导搜索朝向目标，使其在 GPS 导航或游戏 AI 等许多寻路任务中更加高效。A* 使用函数 f(n) = g(n) + h(n) 来评估顶点，其中 g(n) 是从起点到顶点 n 的实际代价，h(n) 是从 n 到目标的代价启发式估计。A* 优先扩展 f(n) 最小的顶点。
For A* to be optimal, the heuristic must be admissible – it must never overestimate the true remaining cost. In grid‑based maps, a common heuristic is the Manhattan distance or straight‑line distance. The Edexcel IGCSE may not require you to trace A* in the same depth as Dijkstra, but you should understand its purpose, how it differs, and where it is used.
为了保证 A* 的最优性，启发式函数必须是可采纳的——它决不能高估真实的剩余代价。在基于网格的地图中，常见的启发式是曼哈顿距离或直线距离。Edexcel IGCSE 可能不要求你像追踪 Dijkstra 那样详尽地追踪 A*，但你应理解其目的、它与 Dijkstra 的区别以及它的应用场景。
12. Exam Tips and Common Pitfalls | 考试技巧与常见误区
When answering graph algorithm questions, always read the requirements carefully: note whether the graph is directed or undirected, weighted or unweighted, and whether a specific neighbour order is stated. If tracing DFS/BFS, show the data structure (stack/queue) contents at each step. For Dijkstra, explicitly write the distance table and clearly indicate the vertex being visited at each stage.
在回答图算法问题时，务必仔细阅读要求：注意图是有向的还是无向的、加权的还是无权的，以及是否规定了特定的邻居顺序。如果要追踪 DFS/BFS，展示每一步数据结构（栈/队列）的内容。对于 Dijkstra，明确写出距离表，并清楚标明每一步正在访问的顶点。
Common mistakes include: forgetting to mark vertices as visited, causing infinite loops; using the wrong data structure (e.g. stack for BFS); misreading weights; and mixing up the update condition in Dijkstra. Also remember that Dijkstra fails if there are negative edge weights. Practise with past papers and time yourself – these questions can be procedural and mechanical, so accuracy under pressure is key.
常见错误包括：忘记标记顶点为已访问，导致无限循环；使用了错误的数据结构（例如 BFS 使用了栈）；读错权重；以及在 Dijkstra 中混淆更新条件。还要记住，如果存在负权边，Dijkstra 会失效。通过历年真题进行练习并计时——这些问题常常是程序化和机械化的，因此在压力下保持准确性是关键。
Published by TutorHao | IGCSE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图