📚 Algorithms on Graphs | 图算法
This revision guide covers the graph algorithms required for Edexcel A-Level Computer Science, including graph representations, depth-first search, breadth-first search, Dijkstra’s shortest path algorithm, and the A* search algorithm. It focuses on tracing methods, data structures, and common exam questions.
本复习指南涵盖 Edexcel A-Level 计算机科学要求掌握的图算法，包括图的表示、深度优先搜索、广度优先搜索、Dijkstra 最短路径算法和 A* 搜索算法。重点讲解追踪方法、数据结构和常见考题。
1. Graphs and Basic Terminology | 图与基本术语
A graph is a collection of vertices, also called nodes, connected by edges, also called arcs. In a directed graph each edge has a direction, while in an undirected graph edges are two-way. A weighted graph labels each edge with a cost, distance, or time.
图是由顶点（节点）和边（弧）连接而成的集合。有向图中每条边都有方向，无向图中边是双向的。带权图会给每条边标注代价、距离或时间。
Key terms include a path, which is a sequence of edges; a cycle, which is a path starting and ending at the same vertex; a connected graph, where a path exists between every pair of vertices; and the degree of a vertex, which is the number of edges incident to it.
关键术语包括路径（边的序列）、环（起点和终点相同的路径）、连通图（任意两顶点之间都存在路径）以及顶点的度（与顶点相连的边数）。
Edexcel questions often ask you to model a problem as a graph and then apply a traversal or shortest-path algorithm. Always identify whether the graph is directed or undirected and whether the edges are weighted before tracing.
Edexcel 考题经常要求将问题建模为图，然后应用遍历或最短路径算法。在开始追踪之前，务必先判断图是有向还是无向，以及边是否带权。
2. Representing Graphs: Adjacency Matrix | 图的表示：邻接矩阵
An adjacency matrix is a square grid with one row and one column for each vertex. Cell M[i][j] stores 1 if there is an edge from vertex i to vertex j, and 0 if there is no edge. In a weighted graph, the cell stores the edge weight instead of 1.
邻接矩阵是一个方阵，每个顶点对应一行和一列。单元格 M[i][j] 存储 1 表示从顶点 i 到顶点 j 有边，存储 0 表示没有边。在带权图中，单元格存储的是边的权重而不是 1。
The matrix uses O(V²) space, where V is the number of vertices. Checking whether a specific edge exists takes O(1) time, which is efficient, but iterating over all entries takes O(V²) even if the graph has very few edges.
邻接矩阵使用 O(V²) 空间，其中 V 是顶点数。检查某条边是否存在只需要 O(1) 时间，非常高效；但即使图中的边很少，遍历所有条目也需要 O(V²) 时间。
For an undirected graph, the adjacency matrix is symmetric across the main diagonal. This symmetry is a useful check when drawing or completing a matrix in the exam.
对于无向图，邻接矩阵关于主对角线对称。考试中绘制或补全矩阵时，这种对称性是一个有用的检查方法。
3. Representing Graphs: Adjacency List | 图的表示：邻接表
An adjacency list stores each vertex together with a list of its direct neighbours. For a weighted graph, each neighbour entry also stores the edge weight, often written as a pair such as (neighbour, weight).
邻接表为每个顶点存储一个直接邻居列表。对于带权图，每个邻居条目还会存储边的权重，通常写成一对，如（邻居，权重）。
The total space required is O(V+E), where E is the number of edges. This is more memory-efficient for sparse graphs, and iterating over the outgoing edges from a vertex is straightforward.
邻接表的总空间复杂度为 O(V+E)，其中 E 是边的数量。对于稀疏图，这种表示更节省内存，并且从一个顶点遍历其出边也更直接。
Edexcel candidates should be able to convert between adjacency matrix and adjacency list representations. Both must represent exactly the same set of vertices and edges.
Edexcel 考生应能在邻接矩阵和邻接表之间进行转换。两种表示必须对应完全相同的顶点集和边集。
| Feature | Adjacency Matrix | Adjacency List |
|---|---|---|
| Space | O(V²) | O(V+E) |
| Check edge (u, v) | O(1) | O(deg(u)) |
| List neighbours of u | O(V) | O(deg(u)) |
| Best for | Dense graphs | Sparse graphs |
4. Depth-First Search (DFS) | 深度优先搜索
Depth-first search, or DFS, explores a path as far as possible before backtracking. It can be implemented using a stack, either explicitly or through recursion.
深度优先搜索（DFS）会尽可能沿着一条路径深入，直到无法继续才回溯。它可以使用栈实现，既可以显式使用栈，也可以使用递归。
The basic algorithm marks the start vertex as visited, then for each unvisited neighbour, recursively performs DFS from that neighbour. A vertex is only fully explored after all of its neighbours have been handled.
基本算法先将起始顶点标记为已访问，然后对每个未访问的邻居递归执行 DFS。只有当所有邻居都处理完毕后，该顶点才完成探索。
DFS is useful for cycle detection, path existence checks, maze solving, and topological ordering of directed acyclic graphs.
DFS 适用于环检测、路径存在性判断、迷宫求解以及对有向无环图进行拓扑排序。
5. Breadth-First Search (BFS) | 广度优先搜索
Breadth-first search, or BFS, explores a graph level by level. It uses a queue to visit all vertices at distance k from the start before visiting any vertex at distance k+1.
广度优先搜索（BFS）逐层探索图。它使用队列，在访问距离起点为 k+1 的顶点之前，先访问所有距离为 k 的顶点。
The steps are: enqueue the start vertex and mark it as visited. While the queue is not empty, dequeue vertex u, then enqueue all unvisited neighbours of u and mark them visited.
步骤为：将起始顶点入队并标记为已访问。当队列不为空时，出队顶点 u，然后将 u 的所有未访问邻居入队并标记为已访问。
BFS finds the shortest path in an unweighted graph because the first time a vertex is discovered is via the shortest sequence of edges from the start.
BFS 可以在无权图中找到最短路径，因为顶点第一次被发现时，到达它所经过的边数一定是最少的。
6. DFS and BFS Worked Example | DFS 与 BFS 例题
Consider this undirected graph: A is connected to B and C; B is connected to A, D, and E; C is connected to A and F; D is connected to B; E is connected to B and F; F is connected to C and E. Start at A.
考虑以下无向图：A 与 B、C 相连；B 与 A、D、E 相连；C 与 A、F 相连；D 与 B 相连；E 与 B、F 相连；F 与 C、E 相连。从 A 开始遍历。
If neighbours are processed alphabetically, the DFS order is A, B, D, E, F
Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导