📚 Graph Algorithms for IGCSE AQA Computer Science | IGCSE AQA 计算机：图算法 考点精讲
Graph algorithms form a fundamental part of theoretical computer science and are key to solving many real-world problems, from GPS navigation to social network analysis. In IGCSE AQA Computer Science, understanding how to represent graphs and apply traversal and pathfinding techniques such as BFS, DFS, and Dijkstra’s algorithm is essential for tackling both paper-based and programming questions. This guide breaks down every concept you need to know, with clear English-Chinese explanations and step-by-step examples.
图算法是理论计算机科学的基础组成部分，也是解决从 GPS 导航到社交网络分析等许多实际问题的关键。在 IGCSE AQA 计算机科学中，理解如何表示图以及应用遍历与寻路技术（如 BFS、DFS 和 Dijkstra 算法）对于应对笔试和编程题至关重要。本指南将拆解每一个你必须掌握的概念，并配以清晰的英中对解释和逐步示例。
1. Graphs: Nodes, Edges, and Types | 图：节点、边与类型
A graph is a collection of vertices (or nodes) connected by edges. Edges can be directed (one-way) or undirected (two-way), and can carry weights representing distance, cost, or capacity. Graphs may be cyclic (containing loops) or acyclic, and connected (all nodes reachable) or disconnected. Understanding these properties helps you choose the right algorithm.
图是由边连接起来的顶点（节点）的集合。边可以是有向的（单向）或无向的（双向），并且可以带有表示距离、成本或容量的权重。图可以是循环的（包含环）或无环的，连通的（所有节点可达）或不连通的。理解这些特性有助于你选择合适的算法。
2. Graph Representation: Adjacency Matrix and List | 图的表示：邻接矩阵与邻接表
The adjacency matrix is a 2D array where matrix[i][j] is 1 (or the weight) if an edge exists from node i to node j, otherwise 0. It provides O(1) edge lookup but uses O(n²) memory. The adjacency list stores a list of neighbours for each node, saving memory on sparse graphs and making it easier to iterate over edges.
邻接矩阵是一个二维数组，如果节点 i 到节点 j 存在边，则 matrix[i][j] 为 1（或权重值），否则为 0。它提供 O(1) 的边查找，但占用 O(n²) 内存。邻接表为每个节点存储一个邻居列表，在稀疏图上节省内存，并使遍历边更加容易。
3. Graph Traversal: Why and How | 图遍历：原因与方法
Traversal means visiting all the nodes in a graph in a systematic way. This is necessary for searching, indexing, or checking connectivity. The two fundamental traversal strategies are Depth-First Search (DFS) and Breadth-First Search (BFS). Both use a discovered/unvisited node tagging system to avoid revisiting.
遍历是指以系统方式访问图中的所有节点。这对于搜索、索引或检查连通性是必要的。两种基本的遍历策略是深度优先搜索 (DFS) 和广度优先搜索 (BFS)。两者都使用已发现/未访问节点的标记系统以避免重复访问。
4. Depth-First Search (DFS) – Stack and Recursion | 深度优先搜索 – 栈与递归
DFS explores as far down one branch as possible before backtracking. It can be implemented using recursion (call stack) or an explicit stack data structure. Starting from a source node, visit an unvisited neighbour, then repeat until stuck, backtrack, and continue. DFS is useful for path-finding in mazes, topological sorting, and detecting cycles.
DFS 会在回溯之前尽可能沿一个分支向下探索。它可以使用递归（调用栈）或显式的栈数据结构来实现。从源节点开始，访问一个未访问的邻居，然后重复直到无法继续，回溯，再继续。DFS 适用于迷宫寻路、拓扑排序和检测环。
5. Breadth-First Search (BFS) – Queue and Layer Order | 广度优先搜索 – 队列与层次顺序
BFS visits all neighbours of a node before moving to the next level. It uses a queue: dequeue a node, visit it, and enqueue all its unvisited neighbours. BFS finds the shortest path in terms of the number of edges in an unweighted graph. It is ideal for peer-to-peer networks, web crawlers, and finding the shortest-hop route.
BFS 在进入下一层之前先访问一个节点的所有邻居。它使用一个队列：将节点出队，访问它，并将其所有未访问的邻居入队。BFS 在无权图中按边数找出最短路径。它非常适用于点对点网络、网络爬虫以及查找最少跳数的路由。
6. Comparing DFS and BFS: When to Use Them | DFS 与 BFS 对比：何时使用
DFS uses less memory on deep graphs and can be easier to implement recursively. BFS is better for finding the shortest path in unweighted graphs but requires more memory to store the queue. In a tree with many solutions, DFS might find a deep solution quickly, whereas BFS guarantees the shallowest solution first. Know their strengths for exam scenarios.
DFS 在深层图中占用内存较少，并且更容易用递归实现。BFS 更适合在无权图中寻找最短路径，但需要更多内存来存储队列。在一个包含许多解的树中，DFS 可能会快速找到一个深层解，而 BFS 则保证首先找到最浅的解。在考试场景中要了解它们的优势。
7. Introduction to Weighted Graphs and Shortest Path | 加权图与最短路径简介
When edges have weights, the shortest path is the one with the minimum total weight, not necessarily the fewest edges. This is a classic problem solved by Dijkstra’s algorithm. Real-world examples include road networks with distances, or network routing with latency. The key is to keep a running cost from the source to each node and update when a cheaper route is found.
当边有权重时，最短路径是指总权重最小的路径，而不一定是边数最少的路径。这是 Dijkstra 算法解决的经典问题。现实世界的例子包括带有距离的道路网络，或带有延迟的网络路由。关键是维护从源点到每个节点的当前成本，并在找到更便宜的路线时进行更新。
8. Dijkstra’s Algorithm Step by Step | Dijkstra 算法逐步解析
Dijkstra’s algorithm works only with non-negative weights. Initialize distances from source to all nodes as infinity, except the source (0). Use a priority queue to repeatedly extract the node with the smallest tentative distance. For that node, relax all neighbouring edges: if neighbour’s distance > current distance + edge weight, update it. Repeat until the queue is empty. The final distances are the shortest paths.
Dijkstra 算法仅适用于非负权重。将源点到所有节点的初始距离设为无穷大，源点自身为 0。使用优先队列反复提取暂定距离最小的节点。对于该节点，对其所有相邻边进行松弛操作：如果邻居的距离大于当前距离 + 边权重，则更新它。重复直到队列为空。最终的距离就是最短路径。
9. Tracing Dijkstra with a Table | 使用表格追踪 Dijkstra
On paper, you often use a table with columns for each node, showing the visited status and current shortest distance from the source. Update the table step by step, crossing out values when a shorter path is found. This systematic approach guarantees marks in exam trace questions. Practice with a simple graph: nodes A – D, weighted edges.
在笔试中，你通常使用一个包含各节点列的表格，显示已访问状态和从源点出发的当前最短距离。逐步更新表格，当发现更短路径时划掉旧值。这种系统化的方法能确保你在考试追踪题中获得分数。用一个简单的图进行练习：节点 A 到 D，带权边。
10. A* Algorithm – Informed Search (Extension) | A* 算法 – 启发式搜索（扩展）
While not always required by all IGCSE curricula, the A* algorithm is useful to know: it improves Dijkstra by adding a heuristic (estimate of cost to the goal). The priority queue uses f(n) = g(n) + h(n), where g(n) is the known cost from start and h(n) is the heuristic. If the heuristic is admissible, A* finds the optimal solution faster. This is widely used in games and GPS.
虽然并非所有 IGCSE 课程都要求，但了解 A* 算法很有用：它通过添加启发式（到目标的估计成本）来改进 Dijkstra。优先队列使用 f(n) = g(n) + h(n)，其中 g(n) 是从起点出发的已知成本，h(n) 是启发式函数。如果启发式是可接受的，A* 能更快找到最优解。该算法广泛用于游戏和 GPS。
11. Efficiency and Big O Notation for Graph Algorithms | 图算法的效率与大 O 表示法
DFS and BFS both have time complexity O(V + E) when using adjacency lists, where V is vertices and E is edges. Dijkstra with a binary heap has O((V+E) log V). Understanding complexity helps you compare algorithms and justify choices. In exams, you may be asked to suggest the most efficient algorithm for a given context.
在使用邻接表时，DFS 与 BFS 的时间复杂度均为 O(V + E)，其中 V 为顶点数，E 为边数。使用二叉堆的 Dijkstra 复杂度为 O((V+E) log V)。理解复杂度有助你比较算法并证明选择的合理性。考试中，你可能会被要求为给定场景建议最高效的算法。
12. Common Exam Pitfalls and Tips | 常见考试陷阱与技巧
Always label ‘visited’ nodes to prevent infinite loops. In matrix representation, check for disconnected components. For Dijkstra, do not apply if a negative weight exists. When drawing trace tables, be consistent with the order of exploring neighbours. Practice both reading and writing pseudocode for DFS/BFS, as programming questions may ask you to complete an algorithm.
务必标记“已访问”节点以防止无限循环。在矩阵表示中，检查是否存在不连通的分量。对于 Dijkstra，如果存在负权重则不可使用。在绘制追踪表格时，探索邻居的顺序要保持一致。练习阅读和编写 DFS/BFS 的伪代码，因为编程题可能要求你补全算法。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导