Graph Algorithms for IGCSE Computer Science | IGCSE 计算机：图算法考点精讲

📚 Graph Algorithms for IGCSE Computer Science | IGCSE 计算机：图算法考点精讲

Graph algorithms are a fundamental topic in IGCSE Computer Science, equipping students with the skills to model and solve real-world problems such as network routing, social connections, and pathfinding. This article breaks down key concepts, representations, traversals, and shortest path algorithms, providing clear explanations, pseudocode, and exam tips to help you master the syllabus.

图算法是 IGCSE 计算机科学中的核心主题，帮助学生掌握建模和解决现实问题的能力，例如网络路由、社交关系与路径搜索。本文将逐一拆解关键概念、图的表示、遍历算法以及最短路径算法，提供清晰的解释、伪代码和考试技巧，助你全面掌握考点。

---

1. What is a Graph? | 什么是图？

A graph is a data structure consisting of a set of vertices (nodes) connected by edges. Graphs can be undirected, where edges have no direction, or directed (digraphs), where each edge points from one vertex to another. Edges may also carry weights to represent cost, distance, or capacity.

图是一种由顶点（节点）集合和连接它们的边组成的数据结构。图可以是无向的（边没有方向）或有向的（有向图），每条边从一个顶点指向另一个顶点。边还可以带有权重，用于表示成本、距离或容量。

For example, a social network can be modeled as a graph where people are vertices and friendships are undirected edges. A road map is a weighted digraph if some roads are one‑way and distances are labelled.

例如，社交网络可以建模为图，其中人是顶点，朋友关系是无向边。道路地图如果包含单行道并标注距离，就是加权有向图。

---

2. Graph Representations | 图的表示方法

IGCSE expects you to understand two common representations: the adjacency matrix and the adjacency list. An adjacency matrix is a 2D array where the element at row i, column j is 1 (or the edge weight) if there is an edge from vertex i to vertex j, and 0 otherwise. An adjacency list uses an array of linked lists or dynamic arrays, where each vertex stores a list of its neighbours.

IGCSE 要求你理解两种常见表示法：邻接矩阵和邻接表。邻接矩阵是一个二维数组，若从顶点 i 到顶点 j 存在边，则第 i 行第 j 列的元素为 1（或边的权重），否则为 0。邻接表则使用一个以链表或动态数组构成的数组，每个顶点存储其邻居列表。

Adjacency matrices allow O(1) edge lookups but consume O(V²) space, making them inefficient for sparse graphs. Adjacency lists are space‑efficient for sparse graphs (approximately V + E references) and enable fast iteration over neighbours, but edge existence checks may require O(degree) time.

邻接矩阵允许 O(1) 的边查找，但占用 O(V²) 空间，对于稀疏图效率较低。邻接表对于稀疏图空间效率高（约 V + E 个引用），并能快速遍历邻居，但检查边是否存在可能需要 O(度) 的时间。

---

3. Graph Traversal Overview | 图遍历概述

Traversing a graph means visiting every vertex in a systematic way. The two principal algorithms are Depth‑First Search (DFS) and Breadth‑First Search (BFS). Both start from a given source vertex and explore the graph by following edges, but they differ in the order of visitation. Understanding traversal is essential for many applications, such as finding connected components, detecting cycles, and solving mazes.

遍历图是指按照一种系统化的方式访问每一个顶点。两种主要的算法是深度优先搜索 (DFS) 和广度优先搜索 (BFS)。两者都从给定的源顶点出发，沿着边探索图，但它们的访问顺序不同。理解遍历对于许多应用至关重要，例如查找连通分量、检测环路和解决迷宫问题。

Both algorithms use a data structure to keep track of vertices to visit next: DFS typically uses a stack (either explicitly or through recursion), while BFS uses a queue. They also maintain a visited array or set to avoid revisiting nodes.

两种算法都使用数据结构来记录接下来要访问的顶点：DFS 通常使用栈（显式或通过递归），而 BFS 使用队列。它们还维护一个已访问数组或集合来避免重复访问节点。

---

4. Depth-First Search (DFS) | 深度优先搜索

DFS explores as far as possible along a branch before backtracking. Starting at the source, it marks the current vertex as visited, then recursively (or using a stack) visits all unvisited neighbours. The process repeats until all reachable vertices have been discovered.

DFS 沿着一个分支尽可能深入探索，然后回溯。从源点开始，标记当前顶点已访问，然后递归地（或使用栈）访问所有未访问的邻居。不断重复，直到所有可达顶点都被发现。

Pseudocode – iterative DFS using stack:

procedure DFS(G, start):
stack.push(start)
while stack is not empty:
v ← stack.pop()
if v not visited:
visit(v)
mark v as visited
for each neighbour n of v:
if n not visited: stack.push(n)

伪代码 – 使用栈的迭代 DFS：
procedure DFS(G, start):
stack.push(start)
while 栈非空:
v ← stack.pop()
if v 未访问:
访问(v)
标记 v 为已访问
for v 的每个邻居 n:
if n 未访问: stack.push(n)

DFS is particularly useful for tasks that require exploring all possibilities, such as puzzle solving and topological sorting. Its time complexity is O(V + E) when implemented with an adjacency list.

DFS 特别适用于需要探索所有可能性的任务，例如解谜和拓扑排序。使用邻接表实现时，其时间复杂度为 O(V + E)。

---

5. Breadth-First Search (BFS) | 广度优先搜索

BFS explores vertices level by level. It uses a queue to store vertices yet to be visited. Starting at the source, it marks it visited and enqueues it. Then, while the queue is not empty, it dequeues a vertex, visits its unvisited neighbours, marks them, and enqueues them.

BFS 逐层探索顶点。它使用队列存储待访问的顶点。从源点开始，标记已访问并入队。然后，当队列非空时，出队一个顶点，访问其未访问的邻居，标记它们并入队。

Pseudocode:

procedure BFS(G, start):
queue.enqueue(start)
mark start visited
while queue is not empty:
v ← queue.dequeue()
for each neighbour n of v:
if n not visited:
visit(n)
mark n visited
queue.enqueue(n)

伪代码：
procedure BFS(G, start):
queue.enqueue(start)
标记 start 已访问
while 队列非空:
v ← queue.dequeue()
for v 的每个邻居 n:
if n 未访问:
访问(n)
标记 n 已访问
queue.enqueue(n)

BFS guarantees the shortest path in an unweighted graph (in terms of number of edges) from the source to any other vertex. Its time complexity is also O(V + E) with an adjacency list.

在无权图中，BFS 能保证从源点到其他任何顶点的最短路径（以边数计）。使用邻接表时，其时间复杂度同样为 O(V + E)。

---

6. DFS vs BFS: Key Differences | DFS 与 BFS 的关键区别

DFS uses a stack (implicit via recursion or explicit) and goes deep first; BFS uses a queue and goes wide first. DFS may use less memory in a deep, narrow graph, while BFS can consume more memory because it stores an entire level. DFS does not guarantee the shortest path in unweighted graphs, whereas BFS does.

DFS 使用栈（通过递归隐式或显式）并优先深入；BFS 使用队列并优先横向扩展。在深度较大、宽度较窄的图中，DFS 内存消耗可能更少，而 BFS 由于需要存储整层节点，内存消耗可能更大。DFS 不保证无权图中的最短路径，而 BFS 可以保证。

In examinations, you may be asked to trace BFS/DFS on a small graph, describe the data structures used, or explain which algorithm is suitable for a given scenario (e.g., finding the shortest number of connections between two profiles in a social network would favour BFS).

考试中，你可能需要在一个小图上手动跟踪 BFS/DFS 的执行过程，描述所用的数据结构，或解释哪种算法适合特定场景（例如，在社交网络中查找两个用户之间的最短连接数应选用 BFS）。

---

7. Shortest Path Problem | 最短路径问题

When edges have weights, the shortest path is the one with the smallest total weight. BFS no longer works because it only minimises the number of edges. To solve weighted shortest paths, we use algorithms such as Dijkstra’s algorithm. The problem is stated as: given a weighted graph and a starting vertex, find the minimum distance to every other vertex.

当边带有权重时，最短路径是总权重最小的路径。BFS 不再适用，因为它只最小化边的数量。为解决加权最短路径，我们使用诸如 Dijkstra 算法的算法。问题可表述为：给定加权图和起始顶点，求到其他每个顶点的最小距离。

IGCSE typically requires you to understand Dijkstra’s algorithm for graphs with non‑negative weights. The algorithm maintains a set of visited vertices and a priority queue to repeatedly select the unvisited vertex with the smallest tentative distance.

IGCSE 通常要求你理解用于非负权重图的 Dijkstra 算法。该算法维护一组已访问顶点和一个优先队列，反复选取未访问顶点中暂定距离最小的顶点进行扩展。

---

8. Dijkstra’s Algorithm | 迪杰斯特拉算法

Dijkstra’s algorithm works by initialising the distance to the source as 0 and all other vertices as infinity. At each step, it selects the unvisited vertex with the smallest current distance, marks it visited, and updates the distances of its neighbours if a shorter path is found through this vertex. This process repeats until all vertices have been visited or the smallest remaining distance is infinity (unreachable).

Dijkstra 算法将源点的距离初始化为 0，其他顶点初始化为无穷大。每一步，它选取未访问顶点中当前距离最小的顶点，将其标记为已访问，如果通过该顶点能找到更短路径，则更新其邻居的距离。重复该过程，直到所有顶点都被访问或剩余最小距离为无穷大（不可达）为止。

Here is a worked example on a small graph: vertices A, B, C, D. Edges: A–B (4), A–C (2), B–D (5), C–B (1), C–D (8). Starting at A:

以下是一个小图的演示例：顶点 A, B, C, D。边：A–B (4), A–C (2), B–D (5), C–B (1), C–D (8)。从 A 开始：

Step	Vertex	A dist	B dist	C dist	D dist
0	–	0	∞	∞	∞
1	A	0*	4	2	∞
2	C	0*	min(4, 2+1)=3	2*	2+8=10
3	B	0*	3*	2*	min(10, 3+5)=8
4	D	0*	3*	2*	8*

Final shortest distances from A: A=0, B=3 (path A–C–B), C=2, D=8 (path A–C–B–D).

最终从 A 的最短距离：A=0, B=3 (路径 A–C–B), C=2, D=8 (路径 A–C–B–D)。

---

9. Dijkstra’s Algorithm Pseudocode | 迪杰斯特拉算法伪代码

Here is a typical pseudocode representation that you might encounter in IGCSE‑style exam questions. It uses a priority queue (or simple list scan in small exam‑traced examples). The algorithm assumes non‑negative weights.

以下是你在 IGCSE 风格考题中可能遇到的典型伪代码表示。它使用优先队列（或在小型考试跟踪示例中简单遍历列表）。算法假设权重非负。

procedure Dijkstra(G, source):
dist[source] ← 0
for each vertex v ≠ source: dist[v] ← ∞
unvisited ← set of all vertices
while unvisited is not empty:
u ← vertex in unvisited with smallest dist[u]
remove u from unvisited
for each neighbour v of u:
alt ← dist[u] + weight(u, v)
if alt < dist[v]:
dist[v] ← alt
return dist

procedure Dijkstra(G, source):
dist[源点] ← 0
for 每个顶点 v ≠ 源点: dist[v] ← ∞
unvisited ← 所有顶点的集合
while unvisited 非空:
u ← unvisited 中 dist[u] 最小的顶点
从 unvisited 移除 u
for u 的每个邻居 v:
alt ← dist[u] + weight(u, v)
if alt < dist[v]:
dist[v] ← alt
return dist

Time complexity depends on the implementation: scanning the unvisited set each time gives O(V²); using a binary heap priority queue improves it to O((V+E) log V). For IGCSE exam tracing, you’ll typically simulate the table as shown above.

时间复杂度取决于实现：每次扫描 unvisited 集合为 O(V²)；使用二叉堆优先队列可改进至 O((V+E) log V)。对于 IGCSE 考试跟踪，你通常需要像前面那样模拟表格。

---

10. Common Pitfalls and Exam Tips | 常见误区与考试技巧

Pitfall 1: Confusing DFS and BFS. Remember: DFS goes deep via a stack, BFS goes broad via a queue. Mnemonic: ‘D’ for depth and ‘Stack’ share the ‘S’? Not quite – just practice.

误区一：混淆 DFS 和 BFS。记住：DFS 通过栈深入，BFS 通过队列横向扩展。记忆方法：深度 (Depth) 和栈 (Stack) 都包含字母 ‘S’？不完全准确 – 多练习即可。

Pitfall 2: Applying BFS on weighted graphs for shortest path. BFS only guarantees the shortest number of edges, not the minimum total weight. Use Dijkstra for weighted graphs with non‑negative weights.

误区二：在加权图上应用 BFS 求最短路径。BFS 仅保证最少边数，不是最小总权重。对非负权重图应使用 Dijkstra 算法。

Pitfall 3: Forgetting to update distances in Dijkstra’s algorithm when a shorter path is found. Always compare and update if the new alternative distance is smaller.

误区三：在 Dijkstra 算法中，找到更短路径时忘记更新距离。务必比较并在新的备选距离更小时进行更新。

Pitfall 4: Assuming the adjacency matrix is always best. For a sparse graph with many vertices but few edges, an adjacency list is far more memory‑efficient.

误区四：认为邻接矩阵总是最优的。对于一个具有大量顶点但边数很少的稀疏图，邻接表的内存效率要高得多。

Exam tip: When tracing, clearly show a table with columns for each vertex and rows for each iteration. Mark visited nodes with an asterisk (*). Use a neat layout to avoid careless mistakes.

考试技巧：在跟踪执行时，清晰地展示一个表格，每列代表一个顶点，每行代表一次迭代。用星号 (*) 标记已访问节点。布局整齐以避免粗心错误。

---

Published by TutorHao | IGCSE Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）