📚 A-Level AQA Computer Science: Graph Algorithms Key Points | A-Level AQA 计算机：图算法 考点精讲
Graph algorithms form a core part of the AQA A-Level Computer Science specification, enabling the modelling and analysis of networks, routes, and relationships. Understanding how to represent graphs and traverse them efficiently is essential for solving real-world problems and performing well in examinations.
图算法是 AQA A-Level 计算机科学课程的核心部分，能够对网络、路径和关系进行建模与分析。理解如何表示图以及高效地遍历图，对于解决实际问题和在考试中取得好成绩至关重要。
1. Introduction to Graphs and Their Representations | 图及其表示方法导论
A graph consists of a set of vertices (nodes) connected by edges. Graphs can be directed or undirected, weighted or unweighted. The choice of representation affects algorithm efficiency and memory usage.
图由一组通过边连接的顶点（节点）组成。图可以是有向或无向的，也可以带权值或不带权值。表示方法的选择会影响算法的效率和内存占用。
Two primary representations are used: adjacency matrix and adjacency list. Each has trade-offs in terms of space complexity and operation speed for tasks like adding edges or checking connectivity.
主要使用两种表示方法：邻接矩阵和邻接列表。它们在空间复杂度以及如添加边或检查连接性等操作的执行速度上各有取舍。
2. Adjacency Matrix: Structure and Analysis | 邻接矩阵：结构与分析
i to vertex j, otherwise 0. For weighted graphs, the value stores the edge weight, with a sentinel (often infinity) representing no connection.
邻接矩阵是一个 V×V 的二维数组，其中 V 是顶点的数量。对于无权图，如果存在从顶点 i 到顶点 j 的边，则 matrix[i][j] = 1，否则为 0。对于带权图，该值存储边的权重，并用一个标记值（通常为无穷大）表示无连接。
Space complexity is O(V²), which can be wasteful for sparse graphs. However, checking whether an edge exists is O(1). Adding or removing an edge is also O(1). This makes adjacency matrices suitable for dense graphs.
空间复杂度为 O(V²)，对于稀疏图可能较浪费。然而，检查边是否存在只需 O(1)。添加或移除边也是 O(1)。这使得邻接矩阵适合于稠密图。
- Advantages: fast edge lookups, simple implementation. / 优点：边查找快，实现简单。
- Disadvantages: high memory usage for sparse graphs, iterating over neighbours takes O(V) time. / 缺点：稀疏图占用的内存高，遍历邻居需要 O(V) 时间。
3. Adjacency List: Efficient Storage | 邻接列表：高效存储
An adjacency list represents a graph as an array of lists. Each vertex has a list of its adjacent vertices (and edge weights if weighted). This can be implemented using arrays, linked lists, or dynamic structures.
邻接列表将图表示为一个列表数组。每个顶点都有一个存储其相邻顶点的列表（对于带权图还包含权重）。这可以用数组、链表或动态结构来实现。
Space complexity is O(V + E), where E is the number of edges. Adding an edge is O(1) if we append to the list. Iterating over all neighbours of a vertex takes time proportional to its degree, which is efficient for sparse graphs.
空间复杂度为 O(V + E)，其中 E 是边的数量。如果采用追加的方式，添加边只需 O(1)。遍历一个顶点的所有邻居所需时间与其度成正比，这对于稀疏图很高效。
- Advantages: low memory for sparse graphs, efficient neighbour iteration. / 优点：稀疏图内存消耗低，邻居遍历高效。
- Disadvantages: edge existence check is O(degree) in worst case. / 缺点：边存在性检查在最坏情况下为 O(度)。
4. Breadth-First Search (BFS) Algorithm | 广度优先搜索（BFS）算法
BFS explores a graph level by level, starting from a source vertex. It uses a queue to keep track of vertices to visit. All vertices at distance k from the source are visited before any vertex at distance k+1.
BFS 从源顶点开始，逐层探索图。它使用一个队列来跟踪待访问的顶点。在访问任何距离 k+1 的顶点之前，所有距离源点为 k 的顶点都已被访问。
The algorithm marks each vertex as unvisited initially. It enqueues the source, marks it visited, and while the queue is not empty, dequeues a vertex, processes it, and enqueues all its unvisited neighbours, marking them visited.
算法首先将所有顶点标记为未访问。将源顶点入队并标记为已访问，当队列非空时，出队一个顶点，处理它，然后将其所有未访问的邻居入队并标记为已访问。
Pseudocode: BFS(Graph, source) / 伪代码
- mark source as visited; queue ← [source] / 标记源顶点为已访问；queue ← [source]
- while queue is not empty: / 当队列非空时：
- v ← dequeue; process v / 出队顶点 v；处理 v
- for each neighbour w of v: / 对于 v 的每一个邻居 w：
- if w is not visited: mark visited; enqueue w / 如果 w 未访问：标记为已访问；入队 w
5. Applications and Properties of BFS | BFS 的应用与性质
BFS finds the shortest path in terms of the number of edges in an unweighted graph. It can be used to compute distances from the source or to determine whether a graph is connected.
BFS 可以在无权图中找到边数最少的最短路径。它可以用来计算从源点出发的距离，或判断图是否连通。
Time complexity is O(V + E) when using an adjacency list, because each vertex and edge is processed once. The queue ensures a first-in-first-out order, which is crucial for level-order traversal.
使用邻接列表时，时间复杂度为 O(V + E)，因为每个顶点和每条边都被处理一次。队列保证了先进先出的顺序，这对层次遍历至关重要。
Common applications include web crawling, social network friend suggestions (within limited degrees), and shortest path on grid maps without obstacles.
常见的应用包括网络爬虫、社交网络好友推荐（在限定度数内），以及无障碍网格地图上的最短路径。
6. Depth-First Search (DFS) Algorithm | 深度优先搜索（DFS）算法
DFS explores as far down a branch as possible before backtracking. It can be implemented using recursion (implicit stack) or an explicit stack. The algorithm marks a vertex visited and then recursively visits all its unvisited neighbours.
DFS 在回溯之前会尽可能地沿着一条分支深入探索。它可以通过递归（隐式栈）或显式栈来实现。算法标记一个顶点为已访问，然后递归地访问它所有未访问的邻居。
The recursive version naturally uses the call stack. An iterative version explicitly pushes vertices onto a stack. DFS does not guarantee the shortest path; the order of traversal depends on the order of neighbours.
递归版本自然地利用调用栈。迭代版本显式地将顶点压入栈中。DFS 不保证最短路径；遍历的顺序取决于邻居的访问顺序。
Recursive DFS(v): / 递归 DFS(v)：
- mark v as visited; process v / 标记 v 为已访问；处理 v
- for each neighbour w of v: / 对于 v 的每一个邻居 w：
- if w is not visited: DFS(w) / 如果 w 未访问：DFS(w)
7. Applications and Comparison of DFS | DFS 的应用与对比
DFS is used for topological sorting, detecting cycles, finding strongly connected components, and maze solving. Its time complexity is also O(V + E) with adjacency lists.
DFS 用于拓扑排序、检测环、寻找强连通分量以及迷宫求解。使用邻接列表时，它的时间复杂度也是 O(V + E)。
Unlike BFS, DFS uses less memory in many practical cases because it only needs to store a single path from root to a leaf plus unexplored siblings. BFS needs to store an entire level, which can be large.
与 BFS 不同，DFS 在许多实际情况下使用的内存较少，因为它只需存储从根到叶的一条路径外加未探索的兄弟节点。BFS 需要存储整个层次，这可能会很大。
A key difference in output: BFS visits vertices in increasing distance order; DFS may go deep quickly. Choosing between them depends on the problem: BFS for shortest unweighted paths, DFS for exhaustive searching or backtracking scenarios.
输出的一个关键区别是：BFS 按距离递增的顺序访问顶点；DFS 可能会迅速深入。选择哪一个取决于问题：BFS 用于无权最短路径，DFS 用于穷举搜索或回溯场景。
8. Shortest Path Problem: Dijkstra’s Algorithm | 最短路径问题：Dijkstra 算法
Dijkstra's algorithm finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edge weights. It maintains a set of vertices whose shortest distances are known and repeatedly selects the unvisited vertex with the smallest tentative distance.
Dijkstra 算法用于在边的权值非负的带权图中，找到从单一源点到所有其他顶点的最短路径。它维护一个已知最短距离的顶点集合，并反复从未访问的顶点中选择暂定距离最小的顶点。
riority queue to efficiently retrieve the minimum-distance vertex. For each neighbour, relax the edge: if distance[u] + weight < distance[v], update distance[v] and predecessor.
初始化：设 distance[source] = 0，所有其他顶点设为无穷大。使用优先队列来高效地获取距离最小的顶点。对每一个邻居进行松弛操作：如果 distance[u] + weight < distance[v]，则更新 distance[v] 和前驱节点。
Relaxation condition: / 松弛条件：
if d[u] + w(u,v) < d[v] then d[v] = d[u] + w(u,v)
9. Dijkstra’s Algorithm Step-by-Step | Dijkstra 算法逐步解析
Begin with a table tracking each vertex's shortest distance and visited status. At each step, pick the unvisited vertex with the smallest distance, mark it visited, and update the distances of its unvisited neighbours using the relaxation condition above.
首先建立一个跟踪每个顶点最短距离和已访问状态的表格。每一步，选择具有最小暂定距离的未访问顶点，将其标记为已访问，然后使用上述松弛条件更新其未访问邻居的距离。
t 2), update B (2+1=3) and D (2+5=7). Then pick B (3), update D (3+3=6). Then pick D (6). Final distances: A=0, B=3, C=2, D=6.
例如，考虑一个包含顶点 A、B、C、D 的图。A 是源点。边：A→B (4)，A→C (2)，C→B (1)，B→D (3)，C→D (5)。初始：A=0，其他为无穷。选择 C（距离 2），更新 B（2+1=3）和 D（2+5=7）。然后选择 B（3），更新 D（3+3=6）。然后选择 D（6）。最终距离：A=0，B=3，C=2，D=6。
10. Limitations of Dijkstra’s Algorithm | Dijkstra 算法的局限性
Dijkstra's algorithm does not work with negative edge weights. The presence of negative weights can cause the algorithm to miscalculate distances because once a vertex is marked visited, its distance is never revisited, yet a cheaper path might appear later via a negative edge.
Dijkstra 算法不能处理负权重边。负权重的存在会导致算法计算距离出错，因为一旦某个顶点被标记为已访问，其距离就不再被重新考虑，但之后可能通过负权边出现更短的路径。
It is also not suitable for graphs with negative cycles. For such cases, the Bellman-Ford algorithm should be used. However, in AQA specification, only non-negative weights are typically considered for Dijkstra.
对于带有负环的图，它也不适用。这些情况应使用 Bellman-Ford 算法。不过，在 AQA 考纲中，Dijkstra 算法通常只考虑非负权重。
Time complexity: O((V + E) log V) with an adjacency list and a binary heap priority queue. Without a priority queue (using a simple array), it becomes O(V²), which is acceptable for small dense graphs often found in exam questions.
时间复杂度：使用邻接列表和二叉堆优先队列时为 O((V + E) log V)。如果不使用优先队列（使用简单数组），则为 O(V²)，这对于考试中常见的小型稠密图是可接受的。
11. Exam Tips and Common Pitfalls | 考试技巧与常见陷阱
When tracing BFS, DFS, or Dijkstra on paper, clearly show the state of data structures (queue/stack/priority queue) after each step. For Dijkstra, always list the unvisited vertices with their current tentative distances to make the selection process transparent.
在纸上追踪 BFS、DFS 或 Dijkstra 时，应清晰展示每一步后数据结构（队列/栈/优先队列）的状态。对于 Dijkstra，始终列出未访问顶点及其当前暂定距离，使选择过程一目了然。
Avoid confusing BFS with DFS: BFS uses a queue (FIFO), DFS uses a stack (LIFO) or recursion. In Dijkstra, do not forget to mark a vertex as visited after it is chosen; otherwise you may reintroduce it and create infinite loops.
避免混淆 BFS 和 DFS：BFS 使用队列（FIFO），DFS 使用栈（LIFO）或递归。在 Dijkstra 中，不要忘记在选定顶点后将其标记为已访问；否则可能会再次引入它并导致无限循环。
Be careful with graph representation choices: if a question provides a sparse graph, adjacency list is more memory efficient; if it requires frequent edge existence queries, mention the O(1) advantage of adjacency matrix.
注意图的表示方法选择：如果题目给出了稀疏图，邻接列表在内存上更高效；如果需要频繁查询边的存在性，应提及邻接矩阵 O(1) 的优势。
Always check for negative weights before applying Dijkstra. Explain why it fails with a simple counter-example. This demonstrates deeper understanding and is often awarded marks.
在应用 Dijkstra 之前务必检查是否存在负权重。用一个简单的反例解释为何会失败。这能展示更深入的理解，通常能获得分数。
12. Summary and Key Takeaways | 总结与核心要点
Mastering graph algorithms requires fluent tracing of BFS, DFS, and Dijkstra by hand. Memorise the time complexities in terms of V and E for both adjacency matrix and adjacency list implementations. Understand the purpose and limitations of each algorithm.
掌握图算法需要能熟练地手动追踪 BFS、DFS 和 Dijkstra。要牢记在邻接矩阵和邻接列表实现下，以 V 和 E 表示的时间复杂度。理解每种算法的目的和局限性。
Finally, practise applying these algorithms to unfamiliar contexts, such as network routing, game maps, or dependency graphs. The AQA exam often presents scenario-based questions requiring you to adapt your knowledge.
最后，多练习将这些算法应用于不熟悉的场景中，例如网络路由、游戏地图或依赖图。AQA 考试常出基于场景的题目，需要你灵活运用所学知识。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图