📚 Graph Algorithms for CCEA IGCSE Computer Science | CCEA IGCSE 计算机图算法考点精讲
Graphs are powerful data structures used to model networks, such as social media connections, transport routes, and computer networks. In the CCEA IGCSE Computer Science specification, graph algorithms play a key role in understanding how to represent, traverse, and find optimal paths through data. This article provides an in‑depth revision of graph concepts, including adjacency matrices, adjacency lists, depth‑first search, breadth‑first search, Dijkstra's shortest path algorithm, minimum spanning trees, and practical applications. We will break down each topic with clear explanations, examples, and step‑by‑step walkthroughs suitable for IGCSE revision.
图是一种强大的数据结构，适合对网络进行建模，例如社交媒体的好友关系、交通路线和计算机网络。在 CCEA IGCSE 计算机科学考纲中，图算法是理解如何表示数据、遍历数据以及寻找最优路径的核心内容。本文将深入复习图的各个概念，包括邻接矩阵、邻接列表、深度优先搜索、广度优先搜索、Dijkstra 最短路径算法、最小生成树以及实际应用。我们将通过清晰的解释、示例和逐步推演，帮助考生掌握 IGCSE 考点。
1. What is a Graph? | 什么是图？
A graph is a collection of nodes (also called vertices) connected by edges. Graphs can be used to represent relationships and connections in many real‑world systems. In IGCSE Computer Science, graphs are classified into several types: undirected (edges have no direction), directed (edges have a direction, shown with arrows), weighted (edges carry a value such as distance or cost), and unweighted.
图是由节点（又称顶点）和连接它们的边组成的集合。图可以用来表示许多现实世界系统中的关系和连接。在 IGCSE 计算机科学中，图分为几种类型：无向图（边没有方向）、有向图（边有方向，用箭头表示）、加权图（边带有数值，如距离或成本）和无权图。
Vertices are often labelled with letters or numbers. An edge in an undirected graph means a two‑way connection, while in a directed graph it means a one‑way connection. 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 without repeating edges.
顶点通常用字母或数字标注。无向图中的边表示双向连接，而有向图中的边表示单向连接。路径是顶点序列，其中每一对相邻顶点都由一条边相连。环是一条起点和终点为同一顶点且不重复经过边的路径。
2. Graph Representation – Adjacency Matrix | 图的表示 – 邻接矩阵
he entry at row i, column j is 1 (or the weight of the edge) if there is an edge from vertex i to vertex j; otherwise it is 0. For undirected graphs, the matrix is symmetric.
邻接矩阵是用于表示图的二维数组。对于有 n 个顶点的图，我们创建一个 n × n 的矩阵。如果从顶点 i 到顶点 j 存在一条边，则第 i 行第 j 列的条目为 1（或该边的权重）；否则为 0。对于无向图，该矩阵是对称的。
Example: A graph with vertices A, B, C. Edges: A–B, B–C. The adjacency matrix (A=0, B=1, C=2) would be:
示例：具有顶点 A、B、C 的图，边为 A–B、B–C。邻接矩阵（A=0，B=1，C=2）如下：
| A | B | C | |
| A | 0 | 1 | 0 |
| B | 1 | 0 | 1 |
| C | 0 | 1 | 0 |
For a weighted graph, replace 1 with the weight. Advantages: fast to check if an edge exists (O(1)). Disadvantage: uses O(n²) memory even when the graph is sparse.
对于加权图，则将 1 替换为权重。优点：检查是否存在边的速度很快（O(1)）。缺点：即使图是稀疏的，也会占用 O(n²) 内存。
3. Graph Representation – Adjacency List | 图的表示 – 邻接列表
An adjacency list stores a list of neighbours for each vertex. It can be implemented using an array of linked lists, or in Python using a dictionary of lists. For each vertex, you store the vertices directly connected to it.
邻接列表为每个顶点存储一个邻居列表。它可以使用链表数组来实现，在 Python 中则使用列表字典。对于每个顶点，你存储与之直接相连的顶点。
Example: The same graph A–B, B–C. Adjacency list: A: [B], B: [A, C], C: [B]. Advantages: memory efficient for sparse graphs (O(V+E)). Disadvantage: checking if an edge exists may take O(degree) time in the worst case.
示例：同样的图 A–B、B–C。邻接列表：A: [B]，B: [A, C]，C: [B]。优点：对于稀疏图内存效率高（O(V+E)）。缺点：检查边的存在在最坏情况下可能需要 O(度) 的时间。
4. Depth‑First Search (DFS) | 深度优先搜索
DFS is a traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (either implicitly via recursion or explicitly). DFS is useful for finding connected components, topological sorting (for directed acyclic graphs), and solving puzzles like mazes.
深度优先搜索是一种遍历算法，它会沿着每条分支尽可能深入，直到无法继续后再回溯。它使用栈（递归隐式实现或显式实现）。DFS 对查找连通分量、拓扑排序（用于有向无环图）以及解决迷宫类问题非常有用。
Algorithm steps: start at a node, mark it as visited. For each unvisited neighbour, recursively perform DFS. The order of visitation depends on the order of neighbours. With an adjacency list, time complexity is O(V+E).
算法步骤：从一个节点开始，将其标记为已访问。对每个未访问的邻居，递归执行 DFS。访问顺序取决于邻居的排列顺序。使用邻接列表时，时间复杂度为 O(V+E)。
Example on graph A–B, B–C, A–C? If we start at A, a possible DFS traversal: A, B, C. After visiting B, we go to C (instead of back to A) if we follow edges in order.
示例：在 A–B、B–C、A–C 的图上，若从 A 开始，可能的 DFS 遍历顺序是：A, B, C。在访问 B 后，若按顺序先访问 C，则走向 C。
5. Breadth‑First Search (BFS) | 广度优先搜索
BFS explores all neighbours at the present depth before moving on to nodes at the next depth level. It uses a queue to keep track of nodes to visit. BFS is ideal for finding the shortest path in an unweighted graph, and is used in peer‑to‑peer networks, social networking features, and web crawling.
广度优先搜索会先探索完当前深度的所有邻居，再进入下一层深度。它使用队列来记录待访问的节点。BFS 非常适用于在无权图中寻找最短路径，并用于对等网络、社交网络功能以及网络爬虫。
Algorithm: start at a node, mark it visited and enqueue it. While the queue is not empty, dequeue a node, then for each unvisited neighbour, mark, enqueue. BFS guarantees that when you first reach a node, you have found the shortest path in terms of number of edges from the start.
算法：从一个节点开始，将其标记为已访问并加入队列。当队列非空时，取出一个节点，然后对该节点的每个未访问邻居进行标记并入队。BFS 保证在首次到达某个节点时，你已找到从起点出发按边数计算的最短路径。
On the same graph A–B, B–C, A–C, starting from A, BFS order: A, B, C (if B explored before C because it's closer). Actually, neighbours of A are B and C, both enqueued. Then B's neighbour C is already visited, so skip. Order: A, B, C.
在同一个图 A–B、B–C、A–C 上，从 A 开始，BFS 的顺序是：A, B, C（因为 B 和 C 都是 A 的邻居，同时入队，然后 B 先出队，其邻居 C 已访问）。顺序为 A, B, C。
6. Shortest Path – Dijkstra's Algorithm | 最短路径 – Dijkstra 算法
Dijkstra's algorithm finds the shortest path from a starting node to all other nodes in a weighted graph with non‑negative weights. It is a greedy algorithm that repeatedly selects the unvisited node with the smallest tentative distance and updates its neighbours.
Dijkstra 算法用于在具有非负权重的加权图中找到从起点到所有其他节点的最短路径。它是一种贪心算法，反复选择具有最小暂定距离的未访问节点，并更新其邻居的距离。
ark it visited. For each neighbour of this node, calculate the new distance = current node' odes are visited or the smallest distance among unvisited nodes is ∞ (disconnected graph).
步骤：将起始节点的距离设为 0，其他节点的距离设为 ∞。将所有节点标记为未访问。当存在未访问节点时，选择距离最小的未访问节点，标记为已访问。对于该节点的每个邻居，计算新距离 = 当前节点距离 + 边的权重。如果新距离小于已存储的距离，则更新之。重复直到所有节点均已访问，或未访问节点中的最小距离为 ∞（图不连通）。
Example: Nodes A, B, C, D. Edges: A–B (1), A–C (4), B–C (2), B–D (5), C– xt visit C (distance 3), update D: 3+1=4 < 6, so D=4. Final distances: A=0, B=1, C=3, D=4.
示例：节点 A、B、C、D。边：A–B (1)，A–C (4)，B–C (2)，B–D (5)，C–D (1)。从 A 开始。距离：A=0，其他为 ∞。访问 A，更新 B 为 1，C 为 4。接着访问 B（最小距离 1），更新 C：1+2=3 < 4，C 变为 3；更新 D：1+5=6。然后访问 C（距离 3），更新 D：3+1=4 < 6，D 变为 4。最终距离：A=0, B=1, C=3, D=4。
7. Minimum Spanning Tree (MST) | 最小生成树
A spanning tree of a graph is a subgraph that connects all vertices together, without any cycles, and with the minimum possible number of edges (V-1). A minimum spanning tree is a spanning tree with the smallest total edge weight. MSTs are used in designing networks like water supply or electrical grids to minimise cost. Two common algorithms: Prim's and Kruskal's.
图的生成树是一个连通所有顶点且无环的子图，其边数最少（V-1）。最小生成树是边权重总和最小的生成树。MST 用于设计供水网络或电网等以最小化成本。两种常见算法：Prim 算法和 Kruskal 算法。
Prim's algorithm starts from an arbitrary node and grows the tree by repeatedly adding the cheapest edge that connects a node in the tree to a node outside the tree. Kruskal's algorithm sorts all edges by weight and adds the smallest edge that does not create a cycle, using a disjoint‑set data structure. Both have their applications; IGCSE may focus on understanding and executing Prim's algorithm manually on a small graph.
Prim 算法从任意节点开始，通过反复添加连接树内节点与树外节点的最小权重边来扩展生成树。Kruskal 算法将所有边按权重排序，然后依次添加不会产生环的最小边，并利用并查集数据结构。两者各有应用；IGCSE 可能侧重理解并在小规模图上手动执行 Prim 算法。
Example of Prim's on the same weighted graph: start at A. Available edges: A–B (1), A–C (4). Choose A–B. Tree nodes: A, B. New available edges: B–C (2), B–D (5). Cheapest is B–C (2). Add C. Tree nodes: A,B,C. Edges: C–D (1). Add D. Total weight = 1+2+1 = 4. The edges chosen: A–B, B–C, C–D.
在相同的加权图上运行 Prim 算法示例：从 A 开始。可选边：A–B (1)，A–C (4)。选择 A–B。树节点：A, B。新可选边：B–C (2)，B–D (5)。最小的是 B–C (2)。添加 C。树节点：A,B,C。边：C–D (1)。添加 D。总权重 = 1+2+1 = 4。所选边为：A–B, B–C, C–D。
8. Tracing and Simulating Graph Algorithms | 追踪与模拟图算法
IGCSE exams often require you to trace an algorithm on a given graph, showing the state of data structures (visited lists, distances, queues, stacks) after each step. You must be able to write down the sequence of vertex visits, updated distances, and the final output. Practise with pencil and paper using a table to record changes.
IGCSE 考试经常要求你在一个给定的图上追踪算法，展示每一步后数据结构的状态（已访问列表、距离、队列、栈）。你必须能够写出顶点的访问序列、更新的距离以及最终输出。建议用纸笔练习，使用表格记录变化。
For BFS, maintain a queue and an output list. For Dijkstra, maintain a table with columns for each vertex: visited (Boolean), distance, and previous vertex. Update them systematically. Show your working clearly to gain full marks.
对于 BFS，维护一个队列和一个输出列表。对于 Dijkstra，维护一个包含各顶点列的表：是否已访问（布尔值）、距离、前驱顶点。系统地更新这些信息。清晰地展现你的推导过程，以获得满分。
9. Algorithm Efficiency and Choosing the Right Representation | 算法效率与选择合适的表示法
Understanding Big O notation is essential for comparing algorithms. For adjacency matrices, space complexity is O(V²). For adjacency lists, it is O(V+E). BFS and DFS both have O(V+E) time complexity on adjacency lists. Dijkstra's algorithm with a simple array has O(V²), but with a priority queue it improves to O((V+E) log V). In IGCSE you might be asked which representation is more efficient for sparse graphs, or why one algorithm is chosen over another.
理解大 O 表示法对于比较算法至关重要。对于邻接矩阵，空间复杂度为 O(V²)。对于邻接列表，空间复杂度为 O(V+E)。在邻接列表上，BFS 和 DFS 的时间复杂度均为 O(V+E)。使用简单数组的 Dijkstra 算法复杂度为 O(V²)，但配合优先队列可改善至 O((V+E) log V)。在 IGCSE 中，你可能会被问到对于稀疏图哪种表示法更高效，或者为什么选择某种算法。
A sparse graph has relatively few edges (E much less than V²), so adjacency lists save memory. For dense graphs, matrices might be easier and faster for edge lookups. However, traversals like BFS and DFS are generally faster with adjacency lists.
稀疏图具有相对较少的边（E 远小于 V²），因此邻接列表可以节省内存。对于稠密图，矩阵可能更容易，边的查询也更快。但是，BFS 和 DFS 等遍历算法通常使用邻接列表更快。
10. Applications and Exam‑Style Questions | 应用场景与考试题型
Graph algorithms appear in many real‑world contexts relevant to IGCSE: GPS navigation (Dijkstra), social media friend suggestions (BFS for short connection distances), packet routing in computer networks (shortest path), and circuit board design. Be prepared to interpret a scenario, model it as a graph, and apply the appropriate algorithm.
图算法出现在许多与 IGCSE 相关的实际场景中：GPS 导航（Dijkstra）、社交媒体好友推荐（BFS 用于查找短连接距离）、计算机网络中的数据包路由（最短路径）以及电路板设计。你需要准备好解释某个场景，将其建模为图，并应用合适的算法。
Typical exam question: "Using Dijkstra's algorithm, find the shortest distance from A to all other nodes. Show your working." You must present a table with iterations and final values. Another question: "Perform a breadth‑first search starting from node X and list the order in which nodes are visited." Always read the details: is the graph directed or undirected? Are there multiple components? Does the algorithm require a specific order when choosing between equal options? (e.g., alphabetical order)
典型的考试题：“使用 Dijkstra 算法，找到从 A 到所有其他节点的最短距离。请展示你的推导过程。” 你必须呈现带有迭代步骤和最终取值的表格。另一题：“从节点 X 开始执行广度优先搜索，列出节点的访问顺序。” 仔细阅读细节：图是有向的还是无向的？是否存在多个连通分量？当有多个等价选项时，算法是否要求特定顺序？（例如按字母顺序）
11. Common Mistakes to Avoid | 常见错误与避坑指南
1. Confusing directed and undirected edges: a directed edge from A to B does not imply B to A. 2. Forgetting to mark nodes as visited, leading to infinite loops or incorrect traversal order. 3. In Dijkstra, updating distances incorrectly: you must only update if new distance is strictly smaller. 4. Applying Dijkstra to graphs with negative weights – it does not work. 5. Using the wrong data structure for a queue (BFS) or stack (DFS) when simulating by hand. 6. Not resetting distances/infinity and visited flags when restarting an algorithm on the same graph.
1. 混淆有向边和无向边：从 A 到 B 的有向边并不意味着 B 到 A。2. 忘记将节点标记为已访问，导致无限循环或错误的遍历顺序。3. 在 Dijkstra 中错误地更新距离：只有当新距离严格更小时才更新。4. 对含有负权重的图使用 Dijkstra 算法——该算法无效。5. 手动模拟时对 BFS 用了栈，对 DFS 用了队列。6. 在同一张图上重新执行算法时，没有重置距离 / 无穷大和已访问标志。
To avoid these, practise step‑by‑step with small graphs. Use tables and follow the algorithms exactly as defined in your course. Check your work by verifying that all nodes are visited (if connected) and distances make sense.
为避免这些错误，请使用小规模的图进行逐步练习。使用表格并严格遵循课程中定义的算法步骤。通过验证所有节点均已访问（如图连通），以及距离的合理性来检查你的工作。
12. Summary and Key Revision Points | 总结与复习要点
Graphs are fundamental to understanding networks and paths. Ensure you can: define graph terminology (vertex, edge, directed, weighted, cycle); draw and interpret adjacency matrices and adjacency lists; trace DFS and BFS on a given graph; trace Dijkstra's algorithm by hand showing a distance table; explain the purpose of an MST and trace Prim's algorithm; compare representations and algorithm efficiencies; and apply these concepts to real‑world scenarios described in exam questions.
图是理解网络和路径的基础。确保你能够：定义图的术语（顶点、边、有向、加权、环）；绘制并解释邻接矩阵和邻接列表；在给定图上追踪 DFS 和 BFS；手动追踪 Dijkstra 算法并展示距离表；解释 MST 的用途并追踪 Prim 算法；比较不同表示法和算法效率；将这些概念应用到考试题目中描述的实际场景中。
Mastering graph algorithms will not only help you tackle algorithm‑tracing questions but also strengthen your computational thinking and problem‑solving skills, which are essential for the IGCSE Computer Science examination.
掌握图算法不仅有助于你应对算法追踪题，还能增强你的计算思维与问题解决能力，这些是 IGCSE 计算机科学考试所必需的核心素养。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图