A-Level OCR Computer Science: Graph Algorithms – Key Concepts | A-Level OCR 计算机：图算法 考点精讲

📚 A-Level OCR Computer Science: Graph Algorithms – Key Concepts | A-Level OCR 计算机：图算法 考点精讲

Graph algorithms are a cornerstone of the OCR A-Level Computer Science curriculum, appearing in both the algorithms and data structures topics. Mastering depth-first search, breadth-first search, Dijkstra’s algorithm, A* search, and minimum spanning tree algorithms is essential for the exams and for understanding efficient problem-solving. This revision guide breaks down each key algorithm, discusses common representations, and provides exam-focused insights.

图算法是 OCR A-Level 计算机科学课程的核心内容，出现在算法和数据结构两大模块中。掌握深度优先搜索、广度优先搜索、迪杰斯特拉算法、A* 搜索以及最小生成树算法对考试和理解高效问题求解至关重要。本精讲逐一拆解关键算法，讨论常见表示方法，并提供备考指导。

---

1. Graphs and Essential Terminology | 图与基础术语

A graph is a collection of vertices (nodes) connected by edges (arcs). In an undirected graph, edges have no orientation; in a directed graph (digraph), each edge has a direction from one vertex to another. Weighted graphs assign a numerical value (weight) to each edge, representing cost, distance, or capacity. Graphs can model real-world systems such as social networks, transport routes, or dependency structures.

图是由边（弧）连接的顶点（节点）的集合。在无向图中，边没有方向；在有向图中，每条边都有明确的方向。有权图给每条边赋予一个数值（权重），表示成本、距离或容量。图能够对社交网络、交通路线或依赖结构等现实系统建模。

Key terms you must know for the OCR exam: adjacent vertices (directly connected), a path (sequence of vertices where each adjacent pair is connected), a cycle (a path that starts and ends at the same vertex without repeating edges), a connected graph (there is a path between every pair of vertices), and a tree (a connected acyclic graph). The degree of a vertex is the number of edges incident to it; in a directed graph we distinguish in-degree and out-degree.

OCR 考试必备术语：相邻顶点（直接相连）、路径（相邻顶点均相连的顶点序列）、环（起点与终点相同且不重复边的路径）、连通图（任意两顶点间存在路径）以及树（连通且无环的图）。顶点的度是指与该顶点相连的边的数量；在有向图中需区分入度和出度。

---

2. Graph Representations | 图的表示方法

OCR expects you to compare adjacency matrices and adjacency lists. An adjacency matrix is a 2D array where cell [i][j] is true (or stores the edge weight) if there is an edge from vertex i to vertex j. For an unweighted graph, it typically stores Boolean values; for a weighted graph it stores the weight, often using infinity (∞) to indicate no edge.

OCR 希望你比较邻接矩阵与邻接列表。邻接矩阵是一个二维数组，若从顶点 i 到顶点 j 存在边，则单元格 [i][j] 为真（或存储边的权重）。对于无权图，通常存储布尔值；对于有权图则存储权重，常用无穷大（∞）表示无边。

An adjacency list representation uses an array or list of lists: each vertex has a list of its neighbouring vertices (and their associated weights). This structure is more space-efficient for sparse graphs (where E is much smaller than V²).

邻接列表表示使用一个数组或列表的列表：每个顶点都有一个包含其邻居（及相关权重）的列表。对于稀疏图（边的数量远小于 V²）而言，这种结构更为节省空间。

Property	Adjacency Matrix	Adjacency List
Space complexity	O(V²)	O(V + E)
Check edge between i and j	O(1)	O(degree) – must scan list
Iterate all neighbours of a vertex	O(V)	O(degree)
Best for	Dense graphs, frequent edge lookups	Sparse graphs, frequent neighbour iteration

Choose the representation based on graph density and the operations you need. In OCR exam questions, you might be asked to deduce the adjacency list from a matrix, or to discuss memory trade-offs.

根据图的稠密度以及所需操作选择合适的表示方式。在 OCR 考题中，可能会要求从矩阵推导出邻接列表，或讨论内存权衡。

---

3. Depth-First Search (DFS) | 深度优先搜索

Depth-first search explores a graph by going as deep as possible along one branch before backtracking. It can be implemented recursively or using an explicit stack. The core idea: start at a source vertex, mark it as visited, then recursively visit each unvisited neighbour. DFS produces a depth-first tree and is used for cycle detection, topological ordering, and solving maze-like puzzles.

深度优先搜索通过沿着一条分支尽可能深入探索，直至无法继续后再回溯。它可以递归实现，也可以使用显式栈。核心思想：从源顶点出发，标记为已访问，然后对每个未访问邻居递归执行 DFS。DFS 生成一棵深度优先树，用于环检测、拓扑排序以及迷宫类难题求解。

A typical recursive pseudocode (in OCR style):
procedure dfs(vertex v)
    mark v as visited
    for each neighbour n of v
        if n is not visited then dfs(n)
end procedure

典型递归伪代码（OCR 风格）：
procedure dfs(vertex v)
    将 v 标记为已访问
    对于 v 的每个邻居 n
        若 n 未访问 则 dfs(n)
end procedure

DFS has a time complexity of O(V + E) when using an adjacency list. Space complexity can be O(V) in the worst case due to the recursion stack (or explicit stack). Exam tip: trace the order of vertex visits on a given graph; OCR often requires you to show the stack contents at each step.

使用邻接列表时，DFS 的时间复杂度为 O(V + E)。最坏情况下空间复杂度为 O(V)，源于递归栈（或显式栈）。备考提示：在给定的图上追踪顶点访问顺序；OCR 经常要求你展示每一步的栈内容。

---

4. Breadth-First Search (BFS) | 广度优先搜索

BFS explores all neighbours at the current depth before moving to vertices at the next depth level. It uses a FIFO queue. Starting from the source, it marks the vertex as visited and enqueues it. Then, while the queue is not empty, it dequeues a vertex u, examines each unvisited neighbour v, marks v as visited, and enqueues v. This level-by-level traversal guarantees the shortest path (in terms of number of edges) in an unweighted graph.

BFS 在移至下一深度层之前，先探索当前深度的所有邻居。它使用先进先出队列。从源点开始，标记顶点为已访问并入队。然后，当队列不为空时，出队顶点 u，检查其每一个未访问邻居 v，标记 v 为已访问并入队。这种逐层遍历保证了在无权图中找到边数最少的最短路径。

BFS pseudocode:
procedure bfs(start)
    create queue Q
    mark start as visited and enqueue start into Q
    while Q is not empty
        u = dequeue(Q)
        for each neighbour v of u
            if v is not visited
                mark v as visited
                enqueue v into Q
end procedure

BFS 伪代码：
procedure bfs(start)
    创建队列 Q
    将 start 标记为已访问并加入 Q
    当 Q 非空时
        u = Q 出队
        对于 u 的每个邻居 v
            若 v 未访问
                标记 v 为已访问
                将 v 入队 Q
end procedure

With an adjacency list, BFS runs in O(V + E) time. It also requires O(V) space for the queue and visited array. BFS is often used for web crawling, social network “friend of a friend” queries, and unweighted shortest path problems.

使用邻接列表时，BFS 的时间复杂度为 O(V + E)。队列和访问数组需要 O(V) 空间。BFS 常用于网络爬虫、社交网络“朋友的朋友”查询以及无权最短路径问题。

---

5. Comparing DFS and BFS | DFS 与 BFS 的比较

Feature	DFS	BFS
Data structure	Stack (recursion or explicit)	Queue
Shortest path in unweighted graph	No – may find a longer path first	Yes – guarantees minimum number of edges
Memory usage	O(V) (stack depth)	O(V) (queue size – can be larger)
Common applications	Topological sort, cycle detection, maze solving	Shortest unweighted path, peer-to-peer search, bipartite testing

Understanding when to use each is crucial. For instance, finding a route with the fewest stops in a road network without weights calls for BFS; exhaustively searching all possibilities in a backtracking puzzle uses DFS. OCR may ask you to explain which algorithm is more appropriate for a given scenario.

理解何时使用哪种算法至关重要。例如，在无权道路网络中寻找最少停靠站的路线应使用 BFS；在回溯谜题中穷举所有可能则使用 DFS。OCR 可能会要求你解释在给定场景下哪种算法更合适。

---

6. Dijkstra’s Shortest Path Algorithm | 迪杰斯特拉最短路径算法

Dijkstra’s algorithm computes the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It maintains an array dist[] of tentative shortest distances, initially dist[source]=0 and all others ∞. It repeatedly selects the unvisited vertex u with the smallest dist[u], marks it as visited, and then relaxes all edges from u:

迪杰斯特拉算法计算非负权重图中从单一源顶点到所有其他顶点的最短路径。它维护暂定最短距离数组 dist[]，初始时 dist[source]=0，其余为 ∞。算法反复选择具有最小 dist[u] 的未访问顶点 u，将其标记为已访问，然后松弛从 u 出发的所有边：

for each neighbour v of u: dist[v] = min(dist[v], dist[u] + weight(u, v))

This relaxation step checks whether a shorter path to v exists via u. When a priority queue (min-heap) is used to extract the vertex with the smallest distance, the time complexity becomes O((V + E) log V). Without a priority queue, the basic implementation is O(V²), which suits dense graphs.

松弛步骤检查是否经由 u 存在到达 v 的更短路径。若使用优先队列（最小堆）提取距离最小的顶点，时间复杂度变为 O((V + E) log V)。基本实现不采用优先队列时为 O(V²)，适合稠密图。

Dijkstra’s algorithm does not work with negative edge weights because it assumes that once a vertex is marked visited, its shortest distance is final; a subsequent negative edge could shorten it. OCR will expect you to state this limitation and explain why it fails with negative weights.

迪杰斯特拉算法不能处理负权重边，因为它假定一旦顶点被标记为已访问，其最短距离即最终确定；后续的负边仍可能缩短该距离。OCR 要求你指出这一局限并解释为何负权重下算法失效。

---

7. Dijkstra’s Algorithm Worked Example | 迪杰斯特拉算法工作示例

Consider a graph with vertices A, B, C, D. Edges: A→B weight 4; A→C weight 2; B→C weight 1; B→D weight 5; C→D weight 8; C→B weight 3. Source = A. Initially dist: A=0, B=∞, C=∞, D=∞. Unvisited: {A,B,C,D}.

考虑一幅具有顶点 A、B、C、D 的图。边：A→B 权重 4；A→C 权重 2；B→C 权重 1；B→D 权重 5；C→D 权重 8；C→B 权重 3。源点 = A。初始 dist：A=0，B=∞，C=∞，D=∞。未访问集：{A,B,C,D}。

Step 1: Pick A (min dist 0). Mark visited. Relax neighbours: B via A (0+4=4 < ∞) → dist[B]=4; C via A (0+2=2 < ∞) → dist[C]=2. Unvisited: {B,C,D}. Distances: A=0, B=4, C=2, D=∞.

第1步：选取 A（最小距离 0）。标记已访问。松弛邻居：经由 A 到 B (0+4=4 < ∞) → dist[B]=4；经由 A 到 C (0+2=2 < ∞) → dist[C]=2。未访问：{B,C,D}。距离：A=0, B=4, C=2, D=∞。

Step 2: Pick C (min dist 2). Mark visited. Relax neighbours from C: To B (2+3=5, but current dist[B]=4, no update); to D (2+8=10 < ∞) → dist[D]=10. Unvisited: {B,D}. Distances: A=0, B=4, C=2, D=10.

第2步：选取 C（最小距离 2）。标记已访问。从 C 松弛邻居：至 B (2+3=5，但当前 dist[B]=4，不更新)；至 D (2+8=10 < ∞) → dist[D]=10。未访问：{B,D}。距离：A=0, B=4, C=2, D=10。

Step 3: Pick B (min dist 4). Mark visited. Relax neighbours from B: To D (4+5=9 < 10) → dist[D]=9. Unvisited: {D}. Distances: A=0, B=4, C=2, D=9.

第3步：选取 B（最小距离 4）。标记已访问。从 B 松弛邻居：至 D (4+5=9 < 10) → dist[D]=9。未访问：{D}。距离：A=0, B=4, C=2, D=9。

Step 4: Pick D (min dist 9). Mark visited. No unvisited neighbours remain. Final shortest distances: A→A=0, A→B=4, A→C=2, A→D=9. The shortest path tree is obtained by recording predecessor vertices during relaxation.

第4步：选取 D（最小距离 9）。标记已访问。无剩余未访问邻居。最终最短距离：A→A=0, A→B=4, A→C=2, A→D=9。通过在松弛过程中记录前驱顶点可获得最短路径树。

This trace shows the greedy choice property. OCR often provides a network diagram and asks you to complete a table showing the order of vertex selection and updated distances.

该追踪过程体现了贪心选择性质。OCR 常给出网络图并要求你完成一个表格，显示顶点选择顺序和更新后的距离。

---

8. A* Search Algorithm | A* 搜索算法

A* is an informed search algorithm that extends Dijkstra’s idea by adding a heuristic estimate h(n) of the remaining cost from node n to the goal. It evaluates nodes using the function f(n) = g(n) + h(n), where g(n) is the actual cost from the start to n. A* prioritises nodes with the lowest f(n), using a priority queue. When the heuristic is admissible (never overestimates the true cost) and consistent (monotonic), A* is guaranteed to find the optimal path.

A* 是一种启发式搜索算法，通过添加从节点 n 到目标的剩余代价的启发式估计 h(n) 扩展了迪杰斯特拉的思想。它使用函数 f(n) = g(n) + h(n) 评估节点，其中 g(n) 是从起点到 n 的实际代价。A* 利用优先队列优先处理 f(n) 最小的节点。若启发式是可采纳的（从不高于真实代价）且一致的（单调性），则 A* 保证找到最优路径。

f(n) = g(n) + h(n)

Common heuristics include Manhattan distance (for grid maps), Euclidean distance, or straight-line distance. A* is widely used in GPS navigation and game AI because it explores fewer nodes than Dijkstra in many practical scenarios, while still guaranteeing optimality.

常见启发式包括曼哈顿距离（网格地图）、欧几里得距离或直线距离。A* 广泛应用于 GPS 导航和游戏 AI，因为在许多实际场景中它比迪杰斯特拉探索更少的节点，同时仍保证最优性。

OCR examiners may provide a small grid with obstacles and ask you to apply A* step by step, computing f, g, h values. Remember: if h(n)=0 for all n, A* degenerates to Dijkstra. If h(n) overestimates, the search may be faster but optimality is lost.

OCR 考官可能提供带有障碍物的小型网格，要求你逐步应用 A* 计算 f、g、h 值。记住：若对所有 n 均有 h(n)=0，A* 退化为迪杰斯特拉。若 h(n) 高估，搜索可能更快但会失去最优性。

---

9. Minimum Spanning Tree (MST) Algorithms | 最小生成树算法

A minimum spanning tree of a weighted, connected, undirected graph is a subset of edges that connects all vertices with the minimum possible total edge weight and contains no cycles. OCR covers two classic greedy algorithms: Prim’s and Kruskal’s.

有权连通无向图的最小生成树是一个连接所有顶点且总边权最小且不包含环的边子集。OCR 涉及两种经典的贪心算法：普里姆算法和克鲁斯卡尔算法。

Prim’s Algorithm: Starts from an arbitrary vertex, maintains a set of connected vertices, and repeatedly adds the cheapest edge that connects a vertex in the set to a vertex outside the set, until all vertices are included. Implementation with

Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）