📚 Graph Algorithms for IGCSE CIE Computer Science | IGCSE CIE 计算机：图算法 考点精讲
Graph algorithms form a core part of the IGCSE CIE Computer Science syllabus, focusing on traversal, shortest path, and spanning tree methods. Understanding how to represent graphs with adjacency matrices and adjacency lists, and how to trace algorithms like Dijkstra's or Prim's, is essential for scoring well on paper 2. This article unpacks the key theory, worked examples, and common pitfalls you must master.
图算法是 IGCSE CIE 计算机科学教学大纲的核心内容，重点涵盖遍历、最短路径和生成树等方法。理解如何用邻接矩阵和邻接表表示图，以及如何跟踪迪杰斯特拉算法或普里姆算法的执行过程，对于在试卷二中获得高分至关重要。本文将深入剖析必须掌握的关键理论、实例解析和常见陷阱。
1. Graph Representations | 图的表示方法
A graph can be stored in a computer using an adjacency matrix or an adjacency list. An adjacency matrix is a 2D array where rows and columns represent vertices, and a cell contains 1 (or weight) if an edge exists, otherwise 0. An adjacency list is an array of linked lists, each listing neighbours of a vertex.
图可以在计算机中用邻接矩阵或邻接表存储。邻接矩阵是一个二维数组，行和列代表顶点，如果存在边，单元格包含 1（或权值），否则为 0。邻接表是一个链表的数组，每个链表列出某个顶点的邻居。
- Adjacency matrix: memory usage O(V sup2), faster edge lookup O(1).
- 邻接矩阵：内存占用 O(V sup2)，边查找更快 O(1)。
- Adjacency list: memory usage O(V + E), better for sparse graphs.
- 邻接表：内存占用 O(V + E)，更适合稀疏图。
2. Traversal: Breadth-First Search (BFS) | 遍历：广度优先搜索 (BFS)
BFS explores a graph level by level using a queue. Starting from a source node, it visits all neighbours before moving deeper. BFS can find the shortest path in an unweighted graph.
BFS 使用队列逐层遍历图。从源节点开始，它在深入之前先访问所有邻居。BFS 可在未加权图中找到最短路径。
- Data structure: queue.
- 数据结构：队列。
- Order: all nodes at distance k before those at k+1.
- 顺序：距离为 k 的所有节点先于距离 k+1 的节点。
- Application: social network friend suggestions, web crawlers.
- 应用：社交网络好友推荐、网络爬虫。
Example trace on a simple graph: start at A, enqueue A; dequeue A, enqueue B, C; dequeue B, enqueue D; dequeue C, enqueue E; dequeue D, E.
简单图上的跟踪示例：从 A 开始，A 入队；出队 A，B、C 入队；出队 B，D 入队；出队 C，E 入队；出队 D、E。
3. Traversal: Depth-First Search (DFS) | 遍历：深度优先搜索 (DFS)
DFS uses a stack (or recursion) to explore as far as possible along each branch before backtracking. It is memory-efficient for deep graphs and is used in topological sorting and maze solving.
DFS 使用栈（或递归）沿每条分支尽可能深入，然后回溯。对于深度图，它内存效率更高，并用于拓扑排序和迷宫求解。
- Data structure: stack (explicit or call stack).
- 数据结构：栈（显式或调用栈）。
- Order: go deep until dead end, then backtrack.
- 顺序：深入直至死胡同，然后回溯。
- Can be implemented recursively or iteratively.
- 可实现为递归或迭代版本。
Pre-order, in-order, and post-order variants exist for trees, but for general graphs only the order of visitation matters.
对于树，存在前序、中序和后序遍历变体，但对于一般图，只有访问顺序才重要。
4. Dijkstra's Shortest Path Algorithm | 迪杰斯特拉最短路径算法
Dijkstra's algorithm finds the shortest path from a start vertex to all other vertices in a weighted graph with non-negative weights. It uses a priority queue to repeatedly select the unvisited vertex with the smallest tentative distance.
迪杰斯特拉算法在具有非负权值的加权图中找到从起始顶点到所有其他顶点的最短路径。它使用优先级队列反复选择未访问顶点中暂定距离最小的顶点。
- Works only with non-negative weights.
- 仅适用于非负权值。
- Data structures: array for distances, priority queue for efficiency, visited set.
- 数据结构：距离数组、提升效率的优先级队列、已访问集合。
- Time complexity: O((V+E) log V) with binary heap.
- 时间复杂度：使用二叉堆为 O((V+E) log V)。
C(2); pick C(2), update B(3) via C; pick B(3), update D(3+5=8), E(3+6=9); pick D(8), etc.
跟踪示例：从 A(0) 开始，更新邻居 B(4)、C(2)；选择 C(2)，通过 C 更新 B(3)；选择 B(3)，更新 D(3+5=8)、E(3+6=9)；选择 D(8) 等。
5. A* Search Algorithm (Extension) | A* 搜索算法（扩展）
start, h is estimated cost to goal. It is commonly used in pathfinding for games and GPS.
虽然并非 IGCSE CIE 的核心内容，A* 算法通过使用启发式函数来引导搜索朝向目标，改进了迪杰斯特拉算法。f(n) = g(n) + h(n)，其中 g 是从起点出发的成本，h 是到目标的估计成本。常用于游戏和 GPS 的寻路。
- If h(n) never overestimates (admissible), A* finds optimal path.
- 如果 h(n) 从不高估（可采纳），A* 能找到最优路径。
- Heuristic example: straight-line distance in a map.
- 启发式函数示例：地图中的直线距离。
6. Minimum Spanning Tree (MST): Prim's Algorithm | 最小生成树 (MST)：普里姆算法
Prim's algorithm builds a minimum spanning tree by starting from an arbitrary vertex and repeatedly adding the cheapest edge that connects a vertex in the tree to a vertex outside, until all vertices are included. It uses a priority queue.
普里姆算法从一个任意顶点开始，反复添加连接树内顶点与树外顶点的代价最小边，直到包含所有顶点，从而构建最小生成树。它使用优先级队列。
- Works on connected, weighted, undirected graphs.
- 适用于连通、加权、无向图。
- Similar to Dijkstra but the key is edge weight to tree, not cumulative distance.
- 与迪杰斯特拉相似，但关键是到树的边权重，而非累积距离。
- Time complexity: O(E log V).
- 时间复杂度：O(E log V)。
e {A,C}, cheapest edges: CB=1, AB=4, CD=5; pick CB=1. Continue until all vertices in tree.
跟踪示例：从 A 开始，边 AB=4、AC=2；选择 AC=2。现在树为 {A,C}，代价最小边：CB=1、AB=4、CD=5；选择 CB=1。继续直到所有顶点都在树中。
7. Minimum Spanning Tree: Kruskal's Algorithm | 最小生成树：克鲁斯卡尔算法
Kruskal's algorithm sorts all edges by weight and adds them one by one if they do not form a cycle. A disjoint-set (union-find) data structure is used to detect cycles efficiently. It is greedy and optimal for sparse graphs.
克鲁斯卡尔算法将所有边按权重排序，如果添加某条边不会形成环，则逐一添加。使用不相交集（并查集）数据结构来高效检测环。它是一种贪心算法，对于稀疏图最优。
- Edge list sorted ascending.
- 边列表按升序排序。
- Union-Find operations: find parent, union subsets.
- 并查集操作：查找父节点、合并子集。
- Time complexity: O(E log E) or O(E log V).
- 时间复杂度：O(E log E) 或 O(E log V)。
On the same graph, Kruskal would examine edges in order: 1 (C-B), 2 (A-C), 4 (A-B cycle skip), 5 (C-D) etc., constructing the same MST.
在同一个图上，克鲁斯卡尔算法会按顺序检查边：1 (C-B)、2 (A-C)、4 (A-B 形成环跳过)、5 (C-D) 等，构建相同的最小生成树。
8. Topological Sorting | 拓扑排序
Topological sorting orders vertices of a directed acyclic graph (DAG) so that for every directed edge (u -> v), vertex u comes before v in the ordering. It can be performed using DFS (postorder) or Kahn's algorithm (in-degree removal).
拓扑排序对有向无环图 (DAG) 的顶点进行排序，使得对于每条有向边 (u -> v)，顶点 u 在排序中先于 v。可使用 DFS（后序）或卡恩算法（入度移除）来执行。
- Only possible for DAGs; used in task scheduling, build systems.
- 仅适用于 DAG；用于任务调度、构建系统。
- Kahn's algorithm: repeatedly remove nodes with in-degree 0.
- 卡恩算法：反复移除入度为 0 的节点。
- DFS-based: finish times in reverse give topological order.
- 基于 DFS 的算法：按完成时间逆序得到拓扑顺序。
Example: A->B, A->C, B->D, C->D. Order: A, B, C, D or A, C, B, D are valid.
示例：A->B、A->C、B->D、C->D。顺序：A、B、C、D 或 A、C、B、D 均有效。
9. Algorithm Comparison and Use Cases | 算法比较和应用场景
Choosing the right graph algorithm depends on the problem. BFS for unweighted shortest path, Dijkstra for weighted non-negative, A* for heuristic guided, Prim/Kruskal for network design, topological sort for dependency resolution. Understanding their time and space complexities is vital for analysis questions.
选择正确的图算法取决于问题。BFS 用于未加权最短路径，迪杰斯特拉用于加权非负图，A* 用于启发式引导，普里姆/克鲁斯卡尔用于网络设计，拓扑排序用于依赖关系解析。理解它们的时间复杂度和空间复杂度对于分析性问题至关重要。
| 算法 Algorithm | 用途 Use Case | 复杂度 Complexity |
|---|---|---|
| BFS | Unweighted shortest path, level order | O(V+E) |
| DFS | Cycle detection, connected components | O(V+E) |
| Dijkstra | Non-negative weighted shortest path | O((V+E) log V) |
| Prim | MST for dense graphs | O(E log V) |
| Kruskal | MST for sparse graphs | O(E log E) |
10. Common Exam Mistakes and Tips | 常见考试错误与技巧
Many students confuse Dijkstra with Prim, applying cumulative distance where edge weight to tree is needed. Always check whether the algorithm requires a priority queue and what key is used. In tracing, update distances in a table with clear columns for vertex, shortest distance, previous vertex, visited status. For Kruskal, sort edges correctly and always check for cycles before adding an edge.
许多学生将迪杰斯特拉算法与普里姆算法混淆，在需要用到树的边权的地方应用累积距离。务必检查算法是否需要优先级队列以及使用什么键值。在跟踪时，在表格中更新距离，明确列出顶点、最短距离、前驱顶点、访问状态等列。对于克鲁斯卡尔算法，正确排序各边，并在添加边之前始终检查是否形成环。
- Practice trace tables: They are often worth 5-8 marks.
- 练习跟踪表格：通常占 5-8 分。
- Memorise algorithm steps in pseudocode, as paper 2 may ask for a step-by-step description.
- 记住伪代码中的算法步骤，因为试卷二可能要求逐步描述。
- Understand the difference between graph storage representations and traversal output.
- 理解图存储表示与遍历输出之间的区别。
11. Glossary of Key Terms | 关键术语表
Vertex: a node in a graph. Edge: a connection between two vertices. Weight: cost associated with an edge. Adjacent: two vertices connected by an edge. Path: sequence of vertices connected by edges. Cycle: a path that starts and ends at the same vertex. Connected graph: there is a path between every pair of vertices. Tree: a connected, acyclic graph. Spanning tree: a subgraph that includes all vertices and is a tree. Minimum spanning tree: a spanning tree with minimum total weight.
顶点：图中的节点。边：两个顶点之间的连接。权值：与边关联的成本。相邻：由一条边连接的两个顶点。路径：由边连接的顶点序列。环：起点和终点为同一顶点的路径。连通图：每对顶点之间存在路径。树：连通且无环的图。生成树：包含所有顶点且是一棵树的子图。最小生成树：总权值最小的生成树。
12. Revision Checklist for Graph Algorithms | 图算法复习清单
- Define adjacency matrix and list, and draw for a given graph.
- 定义邻接矩阵和邻接表，并为给定图绘制。
- Trace BFS and DFS on a small graph, writing the order of visitation.
- 在小型图上跟踪 BFS 和 DFS，写出访问顺序。
- Trace Dijkstra's algorithm step by step, updating a table.
- 逐步跟踪迪杰斯特拉算法，更新表格。
- Trace Prim's and Kruskal's algorithms, producing an MST with total weight.
- 跟踪普里姆算法和克鲁斯卡尔算法，生成具有总权值的最小生成树。
- Explain the purpose of a priority queue and union-find.
- 解释优先级队列和并查集的用途。
- Compare algorithm efficiencies and choose the right one for a scenario.
- 比较算法效率，并为场景选择合适的算法。
- Recognise that Dijkstra fails with negative weights.
- 认识到迪杰斯特拉算法在负权值下失效。
Published by TutorHao | IGCSE CIE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图