Graph Algorithms: Key Concepts for CCEA A-Level Computer Science | 图算法：CCEA A-Level 计算机科学考点精讲

📚 Graph Algorithms: Key Concepts for CCEA A-Level Computer Science | 图算法：CCEA A-Level 计算机科学考点精讲

Graph algorithms form a critical part of the CCEA A-Level Computer Science specification, bridging theoretical understanding with practical problem-solving. This article unpacks the essential graph concepts, traversal techniques, shortest path calculations, and minimum spanning tree constructions that every candidate must master. We explore the underlying data structures, step-by-step algorithm executions, complexity considerations, and typical examination applications.

图算法是 CCEA A-Level 计算机科学考纲的核心组成部分，它将理论理解与实际解题能力结合在一起。本文深入解析了每一位考生必须掌握的基本图概念、遍历技术、最短路径计算以及最小生成树构建。我们将探讨底层数据结构、算法的逐步执行过程、复杂度考量，以及典型的考试应用场景。

1. Graph Terminology and Core Concepts | 图的基本术语与核心概念

A graph G is defined as an ordered pair (V, E), where V is a finite set of vertices (nodes) and E is a set of edges connecting pairs of vertices. In an undirected graph, edges have no direction; the edge (u, v) is identical to (v, u). In a directed graph (digraph), each edge is an ordered pair, so (u, v) is distinct from (v, u). A weighted graph assigns a numeric cost or weight to each edge, enabling algorithms to calculate optimal paths.

图 G 被定义为一个有序对 (V, E)，其中 V 是有限个顶点（节点）的集合，E 是连接顶点对的边集合。在无向图中，边没有方向；边 (u, v) 与 (v, u) 相同。在有向图（有向图）中，每条边是一个有序对，因此 (u, v) 与 (v, u) 不同。加权图给每条边赋予一个数值成本或权重，使算法能够计算最优路径。

Key terms you must recall: a path is a sequence of vertices where each adjacent pair is connected by an edge; the length of a path is the number of edges or the sum of weights. A cycle is a path that starts and ends at the same vertex without repeating edges. A graph is connected if there is a path between every pair of vertices. A tree is a connected, undirected graph with no cycles; it has exactly |V| − 1 edges.

必须牢记的关键术语：路径是一系列顶点序列，其中每一对相邻顶点都由一条边相连；路径的长度可以是边的数量或权重之和。环是一条起点和终点相同且不重复边的路径。如果图中每一对顶点之间都存在一条路径，则该图是连通的。树是一种没有环的连通无向图；它恰好有 |V| − 1 条边。

Term	Definition	中文定义
Adjacent vertices	Vertices connected directly by an edge	由一条边直接相连的顶点
Degree	Number of edges incident to a vertex	与顶点关联的边的数目
Subgraph	A graph whose vertices and edges are subsets of G	顶点和边均为 G 的子集的图
Sparse / Dense	A graph with relatively few / many edges compared to |V|²	相对于 |V|² 边数较少 / 较多的图

---

2. Representing Graphs: Adjacency Matrix and List | 图的表示：邻接矩阵与邻接表

The adjacency matrix is a |V|×|V| two‑dimensional array A, where A[i][j] = 1 (or the edge weight) if an edge exists from vertex i to vertex j, otherwise 0. For an undirected graph the matrix is symmetric. This representation allows O(1) edge existence queries but requires O(|V|²) memory, which is inefficient for sparse graphs.

邻接矩阵是一个 |V|×|V| 的二维数组 A，如果从顶点 i 到顶点 j 存在一条边，则 A[i][j] = 1（或边的权重），否则为 0。对于无向图，该矩阵是对称的。这种表示法支持 O(1) 的边存在性查询，但需要 O(|V|²) 的内存，对于稀疏图而言效率较低。

The adjacency list uses an array of linked lists (or dynamic arrays). Each vertex stores a list of its adjacent vertices. For weighted graphs, each list item contains the neighbour and the edge weight. This representation consumes only O(|V| + |E|) memory, which is ideal for sparse graphs. Iterating over all neighbours of a vertex is proportional to its degree, making it suitable for traversal algorithms like BFS and DFS.

邻接表使用一个链表（或动态数组）数组。每个顶点存储其相邻顶点的列表。对于加权图，每个列表项包含邻居和边的权重。这种表示法仅消耗 O(|V| + |E|) 的内存，非常适合稀疏图。遍历某个顶点的所有邻居所需时间与其度数成正比，因此它适用于像 BFS 和 DFS 这样的遍历算法。

CCEA examination questions often ask you to draw the adjacency matrix or adjacency list for a given graph, and to reason about the storage requirements of each representation for different graph densities.

CCEA 考试题常要求你为给定图画邻接矩阵或邻接表，并针对不同的图密度分析每种表示法的存储需求。

---

3. Depth-First Search (DFS): Stack-Based Exploration | 深度优先搜索 (DFS)：基于栈的探索

Depth‑First Search systematically explores a graph by going as far as possible along each branch before backtracking. It uses a stack (either explicit or the call stack via recursion). The algorithm marks vertices when they are first discovered and again when they are completely processed. DFS produces a depth‑first traversal order and can be used to detect cycles, find connected components, and perform topological sorting.

深度优先搜索通过沿着每一个分支尽可能深入地探索图，然后回溯，从而系统地遍历图。它使用栈（显式栈或通过递归使用调用栈）。算法在首次发现顶点时标记它们，并在完全处理完时再次标记。DFS 生成深度优先遍历序列，并可用于检测环、查找连通分量以及进行拓扑排序。

Pseudo‑code for recursive DFS:

DFS(u):
  mark u as visited
  for each neighbour v of u:
    if v is not visited:
      DFS(v)

递归 DFS 的伪代码：

DFS(u):
  将 u 标记为已访问
  对于 u 的每一个邻居 v：
    如果 v 未被访问：
      DFS(v)

The time complexity of DFS is O(|V| + |E|) when using an adjacency list, because each vertex and each edge is examined once. In examination scenarios, you may need to simulate DFS on a given graph, showing the discovery and finishing times, or identify the order vertices are popped from the stack.

使用邻接表时，DFS 的时间复杂度为 O(|V| + |E|)，因为每个顶点和每条边都会被检查一次。在考试情境中，你可能需要在一个给定的图上模拟 DFS，标出发现时间和完成时间，或者确定顶点出栈的顺序。

---

4. Breadth-First Search (BFS): Queue-Based Traversal | 广度优先搜索 (BFS)：基于队列的遍历

Breadth‑First Search explores the graph level by level, starting from a source vertex. It uses a FIFO queue. BFS first visits all vertices at distance 1 from the source, then all vertices at distance 2, and so on. This guarantees finding the shortest path in terms of the number of edges in an unweighted graph.

广度优先搜索从源顶点开始，逐层探索图。它使用一个先进先出 (FIFO) 队列。BFS 首先访问距离源点为 1 的所有顶点，然后是距离为 2 的所有顶点，依此类推。这保证了在无权图中能找到按边数计算的最短路径。

Pseudo‑code for BFS:

BFS(start):
  create queue Q
  mark start as visited and enqueue start
  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

BFS 的伪代码：

BFS(start):
  创建队列 Q
  将 start 标记为已访问并入队
  当 Q 非空时：
    u = 出队(Q)
    对于 u 的每一个邻居 v：
      如果 v 未被访问：
        将 v 标记为已访问
        将 v 入队

Like DFS, BFS has a time complexity of O(|V| + |E|) with an adjacency list. CCEA candidates should be able to trace BFS on a diagram, list the order of visitation, and reconstruct the shortest‑path tree from the predecessor array.

与 DFS 类似，BFS 在使用邻接表时的时间复杂度为 O(|V| + |E|)。CCEA 的考生应能够在图上手工追踪 BFS、列出访问顺序，并从前驱数组中重建最短路径树。

---

5. Applications of DFS and BFS | DFS 与 BFS 的应用

Both traversals serve as building blocks for more advanced algorithms. DFS is particularly effective for detecting cycles in directed graphs (by checking for back edges), computing topological orderings of directed acyclic graphs (DAGs), and finding strongly connected components via Kosaraju’s or Tarjan’s algorithm. BFS is the foundation of the classic shortest‑path algorithm for unweighted graphs and is used in algorithms like Ford‑Fulkerson for finding augmenting paths.

这两种遍历方法是更高级算法的基础构件。DFS 特别适用于检测有向图中的环（通过检查回边）、计算有向无环图 (DAG) 的拓扑排序，以及通过 Kosaraju 或 Tarjan 算法查找强连通分量。BFS 是无权图经典最短路径算法的基础，并被用于像 Ford‑Fulkerson 这类寻找增广路的算法中。

In CCEA examinations, you may be presented with a scenario (e.g., web crawling, social network friend suggestions, maze solving) and asked to explain why DFS or BFS would be more appropriate. Understanding the memory implications—DFS uses a stack with depth proportional to the longest path, while BFS stores an entire level in the queue—is often examined.

在 CCEA 考试中，你可能遇到一个情境（例如网页爬虫、社交网络好友推荐、迷宫求解），并被要求解释为什么 DFS 或 BFS 更合适。理解内存方面的影响——DFS 使用的栈深度与最长路径成正比，而 BFS 队列中存储的是整层顶点——是常考的内容。

---

6. Shortest Path Problem in Weighted Graphs | 加权图中的最短路径问题

When edges carry non‑negative weights, the shortest path between two vertices is the path that minimises the total sum of edge weights. The most common solution taught at A‑Level is Dijkstra’s algorithm, which works for graphs without negative weight edges. The algorithm maintains a priority queue of vertices with their current shortest distance estimate from the source, and greedily relaxes edges.

当边带有非负权重时，两个顶点之间的最短路径是使边权重总和最小的路径。A‑Level 阶段教授的最常见解法是 Dijkstra 算法，它适用于没有负权重边的图。该算法维护一个顶点优先队列，其中记录着从源点出发的当前最短距离估计值，并贪心地松弛边。

The concept of edge relaxation is pivotal: if the distance to vertex v through intermediate vertex u is shorter than the currently recorded distance to v, we update d[v] = d[u] + weight(u, v). This process continues until all vertices have been finalised.

边松弛的概念至关重要：如果通过中间顶点 u 到顶点 v 的距离比当前记录的到 v 的距离更短，我们就更新 d[v] = d[u] + weight(u, v)。此过程一直持续到所有顶点都被确定为止。

---

7. Dijkstra’s Algorithm Step‑by‑Step | Dijkstra 算法逐步解析

Dijkstra’s algorithm begins by setting the distance to the source as 0 and all other distances to infinity. It repeatedly selects the unvisited vertex with the smallest tentative distance, marks it as visited, and updates the distances of its neighbours. Here is a concrete step‑by‑step description:

Dijkstra 算法首先将到源点的距离设为 0，其他所有距离设为无穷大。它反复选择未访问顶点中暂定距离最小的一个，将其标记为已访问，并更新其邻居的距离。以下是具体的逐步描述：

1. Initialisation: dist[source] = 0; for all other vertices v, dist[v] = ∞; all vertices are unvisited.
   初始化：dist[源点] = 0；对于所有其他顶点 v，dist[v] = ∞；所有顶点均未访问。
2. Select the unvisited vertex u with the smallest dist[u]; mark u as visited.
   选择未访问顶点中 dist[u] 最小的顶点 u；将 u 标记为已访问。
3. For each neighbour v of u that is still unvisited: if dist[u] + weight(u, v) < dist[v], then dist[v] = dist[u] + weight(u, v) and set predecessor[v] = u.
   对于 u 的每一个尚未访问的邻居 v：如果 dist[u] + weight(u, v) < dist[v]，则 dist[v] = dist[u] + weight(u, v) 并设置 predecessor[v] = u。
4. Repeat steps 2 and 3 until all vertices are visited or the target vertex is reached.
   重复步骤 2 和 3，直到所有顶点都被访问或达到目标顶点。

The algorithm’s performance depends on the priority queue implementation. Using a binary heap gives O((|V| + |E|) log |V|) time. CCEA exam questions typically require you to fill in a distance table for a small graph, showing the selected vertex at each stage and the corresponding distance updates.

算法的性能取决于优先队列的实现方式。使用二叉堆的时间复杂度为 O((|V| + |E|) log |V|)。CCEA 考题通常要求你为一个较小的图填写距离表，标出每一阶段选择的顶点以及相应的距离更新。

Step	Visited Vertex	A	B	C	D
0	―	0	∞	∞	∞
1	A	0	7	3	∞
2	C	0	5	3	11
3	B	0	5	3	9
4	D	0	5	3	9

Example distance table tracing Dijkstra from vertex A.
示例：从顶点 A 出发追踪 Dijkstra 的距离表。

---

8. A* Algorithm: Heuristic Search | A* 算法：启发式搜索

While not always a mandatory CCEA exam item, the A* algorithm frequently appears in extension material and coursework discussions. A* improves upon Dijkstra by incorporating a heuristic estimate h(n) of the distance from node n to the target. The evaluation function is f(n) = g(n) + h(n), where g(n) is the actual cost from the start to n. A* prioritises nodes with the smallest f(n).

虽然 A* 算法不总是 CCEA 考试的必考项，但它经常出现在拓展材料和课程作业讨论中。A* 算法通过引入节点 n 到目标点距离的启发式估计值 h(n) 来改进 Dijkstra。评估函数为 f(n) = g(n) + h(n)，其中 g(n) 是从起点到 n 的实际代价。A* 优先处理 f(n) 最小的节点。

If the heuristic h(n) is admissible (never overestimates the true remaining cost) and consistent, A* is guaranteed to find the optimal path. A common example is using straight‑line Euclidean distance as a heuristic on a road map. CCEA candidates should be able to contrast A* with Dijkstra: Dijkstra uses h(n) = 0, making it a special case of A*.

如果启发式函数 h(n) 是可采纳的（从不高于真实剩余成本）且一致的，那么 A* 算法保证能找到最优路径。一个常见例子是在道路地图上使用直线欧氏距离作为启发式函数。CCEA 考生应能对比 A* 与 Dijkstra：Dijkstra 使用 h(n) = 0，因此它是 A* 的一种特例。

---

9. Minimum Spanning Trees: Connecting All Vertices Efficiently | 最小生成树：高效连接所有顶点

A spanning tree of a connected, undirected graph is a subgraph that includes all the vertices and is a tree (|V| − 1 edges, no cycles). A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight. MSTs are used in network design, circuit wiring, and clustering. Two classic greedy algorithms are Prim’s and Kruskal’s.

连通无向图的生成树是一个包含所有顶点的树状子图（|V| − 1 条边，无环）。最小生成树 (MST) 是总边权重尽可能最小的生成树。MST 常用于网络设计、电路布线和聚类分析。两种经典的贪心算法是 Prim 算法和 Kruskal 算法。

Both algorithms exploit the cut property: for any partition of vertices, the minimum weight edge crossing the cut must belong to the MST. CCEA candidates are expected to apply both algorithms manually on a given weighted graph and to produce the MST along with its total weight.

这两种算法都利用了割性质：对于任意顶点划分，跨越割的最小权重边必定属于 MST。CCEA 考生应能在给定的加权图上手工执行这两种算法，并得出 MST 及其总权重。

---

10. Prim’s Algorithm: Vertex‑Based Approach | Prim 算法：基于顶点的构建方法

Prim’s algorithm grows the MST one vertex at a time, starting from an arbitrary vertex. At each step, it adds the cheapest edge that connects a vertex already in the tree to a vertex outside the tree, without creating a cycle. This is efficiently implemented with a priority queue storing the minimum connecting edge weight for each vertex not yet in the tree.

Prim 算法每次增加一个顶点来构建 MST，起始顶点可任意选择。每一步，它选取一条连接树内顶点与树外顶点且不会形成环的权重最小的边。这可以用优先队列高效实现，该队列存储尚未加入树的每个顶点的最小连接边权重。

Manual tracing for a small graph involves maintaining a table of the best known connecting edge cost for each vertex, updating those costs as new vertices are incorporated. The process continues until all vertices are included.

对小型图进行手工追踪时，需要为每个顶点维护一个最佳已知连接边成本表，并在新顶点加入时更新这些成本。此过程一直持续到所有顶点都被包含为止。

Time complexity: O(|V|²) for dense graphs using a simple array, or O((|V| + |E|) log |V|) with a binary heap and adjacency list.

时间复杂度：使用简单数组对稠密图为 O(|V|²)，使用二叉堆和邻接表为 O((|V| + |E|) log |V|)。

---

11. Kruskal’s Algorithm: Edge‑Based Approach | Kruskal 算法：基于边的构建方法

Kruskal’s algorithm builds the MST by sorting all edges by weight in ascending order and then adding them one by one, provided they do not form a cycle with the edges already selected. Cycle detection is typically managed through a disjoint‑set (union‑find) data structure, which efficiently determines whether two vertices belong to the same connected component.

Kruskal 算法通过将所有边按权重升序排序，然后逐一添加边来构建 MST，前提是该边不会与已选边形成环。环检测通常通过不相交集（并查集）数据结构来实现，它能高效地判断两个顶点是否属于同一个连通分量。

At the start, each vertex is its own component. For each edge in sorted order, if the edge connects two different components, it is added to the MST and the components are merged. The algorithm stops when |V| − 1 edges have been added.

开始时，每个顶点自身是一个分量。对于按序排列的每条边，如果该边连接了两个不同分量，则将其加入 MST 并合并两个分量。当添加了 |V| − 1 条边时，算法停止。

Kruskal’s algorithm is particularly effective for sparse graphs. Its time complexity is dominated by sorting, giving O(|E| log |E|) or equivalently O(|E| log |V|). CCEA exam questions often provide a list of edges with weights and ask you to draw the MST step by step, clearly showing which edges are rejected due to cycle formation.

Kruskal 算法特别适用于稀疏图。其时间复杂度主要由排序决定，为 O(|E| log |E|) 或等效地 O(|E| log |V|)。CCEA 考题经常提供带权重的边列表，并要求你逐步绘制 MST，清晰地标出哪些边因形成环而被拒绝。

---

12. Comparing Prim’s and Kruskal’s Algorithms | Prim 与 Kruskal 算法对比

Feature	Prim’s Algorithm	Kruskal’s Algorithm
Perspective	Vertex‑focused: grows a tree from a root	Edge‑focused: builds forest and merges
Graph type suited	Dense graphs	Sparse graphs
Cycle handling	Automatically avoids cycles by connecting to unvisited vertices	Explicitly checks for cycles using union‑find
Time (adj. list + PQ)	O((|V| + |E|) log |V|)	O(|E| log |E|)

对比表如下：

特征	Prim 算法	Kruskal 算法
视角	基于顶点：从根开始生长树	基于边：构建森林再合并
适合的图类型	稠密图	稀疏图
环处理	通过连接未访问顶点自动避免环	使用并查集显式检查环
时间（邻接表 + 优先队列）	O((|V| + |E|) log |V|)	O(|E| log |E|)

For CCEA, you must be able to select the most appropriate algorithm given a problem context. If the graph is dense and described as a matrix, Prim’s O(|V|²) implementation is simpler. If edges are given as a list and the graph is sparse, Kruskal’s is often more straightforward to apply manually.

对于 CCEA，你必须能够根据问题情境选择最合适的算法。如果图是稠密的并以矩阵形式描述，Prim 的 O(|V|²) 实现更简单。如果边以列表形式给出且图是稀疏的，Kruskal 算法通常更易于手算应用。

Published by TutorHao | Computer Science Revision Series | aleveler.com

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