Graph Algorithms | 图算法考点精讲

📚 Graph Algorithms | 图算法考点精讲

Graph algorithms form a critical part of the A-Level WJEC Computer Science specification, enabling us to model and solve real-world problems such as network routing, social connections, and dependency tracking. Understanding how to represent graphs, traverse them, and compute the shortest paths or minimal connections is essential for both the theoretical paper and practical coding tasks. This article consolidates key graph techniques, step‑by‑step examples, and exam tips to help you master every algorithm confidently.

图算法是 A-Level WJEC 计算机科学考试的核心内容，它们能帮助我们建模和解决网络路由、社交关系、依赖追踪等现实问题。掌握图的表示方法、遍历方式，以及最短路径或最小连接的计算，不仅是理论卷的必考重点，也是编程题的基础。本文将系统梳理关键图算法，配合逐步示例与应试技巧，助你轻松掌握所有考点。

1. Graph Terminology & Representations | 图的基础术语与表示方法

A graph G = (V, E) consists of a set of vertices V and a set of edges E. Edges can be directed (ordered pairs) or undirected (unordered pairs). Weighted graphs assign numerical values to edges. The choice between adjacency matrix and adjacency list affects storage efficiency and algorithm speed. An adjacency matrix uses O(|V|²) space and allows O(1) edge existence checks, while an adjacency list uses O(|V|+|E|) space but requires O(degree) to check adjacency.

图 G = (V, E) 由顶点集合 V 与边集合 E 构成。边可以是有向的（有序对）或无向的（无序对）。加权图会给边赋予数值。邻接矩阵与邻接表的选择直接影响存储效率与算法速度：邻接矩阵占用 O(|V|²) 空间，但可在 O(1) 时间内查边；邻接表仅占用 O(|V|+|E|) 空间，但查邻接关系需 O(degree) 时间。

**Adjacency Matrix vs Adjacency List for an Undirected, Unweighted Graph**
Aspect	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Add Edge	O(1)	O(1) (average)
Remove Edge	O(1)	O(degree)
Check Adjacency	O(1)	O(degree)

For WJEC exams you must be able to draw both representations from a diagram and justify your choice based on the graph’s density. In a dense graph where |E| ≈ |V|², matrix is often preferred; in a sparse graph with few edges, adjacent list saves memory.

在 WJEC 考试中，你需要能够根据图画出两种表示，并根据图的稠密度做出选择。稠密图中 |E| ≈ |V|²，矩阵更合适；稀疏图中边很少，邻接表更节省内存。

2. Breadth‑First Search (BFS) | 广度优先搜索

BFS explores a graph level by level from a starting vertex, using a queue. It visits all vertices at distance k before any at distance k+1. This guarantees the shortest path in unweighted graphs. The algorithm has a time complexity of O(V + E) when using an adjacency list. A typical BFS also records visited status and parent pointers to reconstruct the path.

BFS 利用队列从起始顶点逐层遍历图。它会先访问所有距离为 k 的顶点，再到 k+1 层的顶点，从而保证在无权图中找到最短路径。使用邻接表时时间复杂度为 O(V + E)。经典的 BFS 还会记录访问状态与父节点以重建路径。

Step‑by‑step BFS from vertex A:

从 A 出发的 BFS 流程：

Enqueue start node A, mark visited. | 将起点 A 入队并标记已访问。
While queue not empty: dequeue a node, process it, and enqueue all its unvisited neighbours, marking them visited and setting their parent. | 队列不空时：出队一个节点处理之，将其所有未访问的邻居入队、标记并记录父节点。
Continue until queue is empty. | 重复直至队列为空。

WJEC exam questions often ask for the order of traversal or for the contents of the queue after each step. Remember that the order depends on the order you check neighbours (e.g. alphabetical).

WJEC 考题常要求写出遍历顺序或每一步队列的内容。注意遍历顺序取决于检查邻居的顺序（如字母序）。

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

DFS uses a stack (or recursion) to explore as far along a branch as possible before backtracking. It marks visited nodes upon first discovery. The time complexity is also O(V + E) with an adjacency list. DFS is useful for cycle detection, topological sorting, and finding connected components.

DFS 利用栈（或递归）尽可能沿着一条分支深入，触底后再回溯。首次发现节点时即标记访问。使用邻接表的时间复杂度同为 O(V + E)。DFS 可用于检测环路、拓扑排序及找出连通分量。

**Comparing BFS and DFS**
Property	BFS	DFS
Data Structure	Queue	Stack (or recursion)
Order	Level‑order	Pre‑order (arbitrary)
Shortest Path (unweighted)	Guaranteed	Not guaranteed
Space Usage	O(V) (queue)	O(V) (call stack)

When tracing DFS, be precise about the backtracking moment. In a recursive implementation, once a vertex has no unvisited neighbours, the recursion returns to the calling vertex.

追踪 DFS 时，要精确描述回溯时机。递归实现中，当某顶点无未访问邻居时，递归返回至上一层调用点。

4. Dijkstra’s Algorithm | 迪杰斯特拉算法

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non‑negative edge weights. It maintains a priority queue of vertices ordered by their current shortest distance estimate. Once a vertex is removed from the queue, its distance is finalised. The time complexity is O((V+E) log V) with a binary heap. You must be able to apply Dijkstra manually on a small graph and show the distance and predecessor table.

Dijkstra 算法可在边权非负的加权图中找出从源点到所有其他顶点的最短路径。它维护一个按当前最短距离估计排序的优先队列。一旦某顶点出队，其距离即被确定。若使用二叉堆，时间复杂度为 O((V+E) log V)。你必须能手动对小型图执行 Dijkstra 并给出距离和前驱表。

Manual tracing procedure: 1) Initialise distance to source = 0, all others = ∞. 2) While unvisited nodes remain, select the unvisited node with smallest distance; for each neighbour, relax the edge if a shorter path is found. 3) Update distances and predecessors. 4) Mark the node as visited.

手动追踪步骤：1) 源点距离初始化为 0，其余为 ∞。2) 尚有未访问节点时，选取距离最小的未访问节点；对其每个邻居，若发现更短路径则松弛该边。3) 更新距离与前驱。4) 标记该节点为已访问。

If the graph contains negative edges, Dijkstra fails; WJEC may ask you to explain why and to identify the need for an alternative like Bellman‑Ford.

若图含负权边，Dijkstra 会失效；WJEC 可能要求解释原因并指出需改用 Bellman‑Ford 等算法。

5. Bellman‑Ford Algorithm (Extension) | 贝尔曼‑福特算法（拓展）

Bellman‑Ford computes shortest paths from a single source to all vertices even when negative edge weights exist, and it can detect negative weight cycles. Its time complexity is O(V·E). The algorithm relaxes every edge V−1 times; if a further relaxation is possible after that, a negative cycle exists. While not as heavily weighted as Dijkstra in WJEC, it appears in some specification statements and is useful for deeper understanding.

Bellman‑Ford 算法可在存在负权边的情况下仍计算单源最短路径，并能检测负权环。时间复杂度为 O(V·E)。算法对每条边松弛 V−1 遍；若此后仍可松弛，则存在负环。虽然在 WJEC 中权重大于 Dijkstra，但部分内容涉及，深入了解有助于拿高分。

6. A* Search Algorithm (Heuristic) | A* 搜索算法（启发式）

A* enhances Dijkstra by introducing a heuristic function h(n) that estimates the cost from node n to the goal. The priority queue orders nodes by f(n) = g(n) + h(n), where g(n) is the cost from start to n. If the heuristic is admissible (never overestimates) and consistent, A* finds the optimal path. Common heuristics for grid maps include Manhattan distance and Euclidean distance. Complexity depends on the heuristic but can be exponential in worst case.

A* 算法通过引入启发函数 h(n)（估计节点 n 到目标的代价）来改进 Dijkstra。优先队列按 f(n) = g(n) + h(n) 排序，其中 g(n) 为起点到 n 的实际代价。若启发函数是可采纳（不高估）且一致的，A* 就能找到最优路径。网格地图常用曼哈顿距离或欧氏距离作为启发式。复杂度取决于启发函数，最坏情况下可达指数级。

WJEC expects you to understand how heuristics prune the search space and to compare A* with Dijkstra. You should be able to trace A* on a small grid with a given heuristic.

WJEC 希望你能理解启发式如何剪枝搜索空间，并比较 A* 与 Dijkstra。你应能根据给定启发式在小型网格上追踪 A*。

7. Minimum Spanning Tree: Prim’s Algorithm | 最小生成树：普里姆算法

A minimum spanning tree (MST) connects all vertices in a weighted, undirected graph with the minimum total edge weight. Prim’s algorithm builds the MST by starting from an arbitrary vertex and repeatedly adding the smallest edge that connects a tree vertex to an outside vertex. Using a priority queue, complexity is O(E log V). Manual tracing requires maintaining a set of included vertices and selecting the cheapest crossing edge at each step.

最小生成树 (MST) 以最小的总边权连接加权无向图中的所有顶点。Prim 算法从任意顶点出发，不断添加连接树内顶点与外部顶点的最小边来构建 MST。借助优先队列，复杂度为 O(E log V)。手动追踪时需要维护已加入顶点集合并每次选取成本最低的割边。

Example trace: Start at A. Adjacent edges: A‑B = 4, A‑C = 2 → choose A‑C. Include C. Crossing edges: A‑B=4, C‑B=1, C‑D=5 → choose C‑B. Include B, then B‑D=3, and so on until all vertices are connected.

追踪示例：从 A 开始。邻边：A‑B=4, A‑C=2 → 选 A‑C 加入 C。此时割边：A‑B=4, C‑B=1, C‑D=5 → 选 C‑B，加入 B，再选 B‑D=3，以此类推直至所有顶点连通。

8. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树：克鲁斯卡尔算法

Kruskal’s algorithm sorts all edges by weight and adds them one by one, skipping those that would create a cycle (checked via union‑find data structure). It processes edges globally, unlike Prim’s vertex‑focused approach. Complexity is O(E log E) or O(E log V) due to sorting. Exam questions often present a table of edges and ask for the stepwise construction of the MST.

Kruskal 算法先将所有边按权值排序，再逐条加入，若形成环则跳过（使用并查集检测）。与 Prim 的顶点聚焦方式不同，Kruskal 全局处理边。因排序，复杂度为 O(E log E) 或 O(E log V)。考试常给出边表，要求逐步构造 MST。

Sort edges: 1 (C‑B), 2 (A‑C), 3 (B‑D), 4 (A‑B), 5 (C‑D). | 边排序：1(C‑B), 2(A‑C), 3(B‑D), 4(A‑B), 5(C‑D)。
Add C‑B, A‑C, B‑D; skip A‑B (cycle) and C‑D (cycle). | 加入 C‑B, A‑C, B‑D；跳过 A‑B（成环）和 C‑D（成环）。

Both Prim and Kruskal produce the same total weight, but the specific tree can differ if multiple edges have equal weight.

Prim 和 Kruskal 的总权重相同，但当有多条等权边时，具体生成的树可能不同。

9. Topological Sorting | 拓扑排序

Topological sorting applies to directed acyclic graphs (DAGs) and produces a linear ordering of vertices such that for every directed edge u→v, u comes before v. Two common methods are DFS post‑order and Kahn’s algorithm (removing nodes with zero in‑degree). Time complexity is O(V+E). Applications include task scheduling and build dependency resolution.

拓扑排序适用于有向无环图 (DAG)，输出顶点的线性序列，满足每条有向边 u→v 中 u 在 v 之前。常用方法有 DFS 后序法以及 Kahn 算法（删去入度为 0 的节点）。时间复杂度为 O(V+E)。应用包括任务调度和构建依赖解析。

Kahn’s algorithm trace: Compute in‑degree of each vertex. Enqueue vertices with in‑degree zero. While queue not empty: dequeue vertex, append to sorted list, decrease in‑degree of its neighbours by 1; if any neighbour’s in‑degree becomes zero, enqueue it.

Kahn 算法追踪：计算各顶点入度，将入度为 0 者入队。队列不空时：出队顶点加入结果序列，将其所有邻居入度减 1；若某邻居入度变为 0 则入队。

If the sorted list length < |V|, a cycle exists, so topological order is impossible.

若结果列表长度小于 |V|，则图中存在环路，无法进行拓扑排序。

10. Graph Applications & Real‑World Context | 图的应用与现实情境

WJEC papers often contextualise graph algorithms within real‑world scenarios. BFS can model shortest hops in social networks or web crawling. DFS is used in maze solving and circuit board path finding. Dijkstra and A* appear in GPS navigation and logistics. MST algorithms optimise laying utility networks like water pipes or electrical cables with minimal cost. Topological sorting is key in project planning (PERT charts) and university prerequisite chains.

WJEC 试卷常将图算法置于现实情境中。BFS 可模拟社交网络的最少跳数或网页爬取；DFS 用于迷宫求解与电路板路径探测；Dijkstra 与 A* 出现在 GPS 导航与物流领域；MST 算法优化铺设水管、电缆等公用设施网络的最小成本；拓扑排序则在项目计划 (PERT 图) 和大学先修课程链条中起关键作用。

You should be prepared to read a textual description, extract the graph model, select the appropriate algorithm, and justify why it fits the constraints (e.g. weighted/unweighted, directed/undirected, need for heuristic).

你需要能够从文字描述中提取图模型，选择合适的算法，并论证其为何符合约束（如是否加权、是否有向、是否需要启发式）。

11. Tracing Algorithms Step‑by‑Step | 算法逐步追踪技巧

WJEC examination requires detailed, step‑by‑step traces of graph algorithms. Always present your work clearly: include the data structures (queue, stack, priority queue, distance array, predecessor list). For each iteration, record the changes. Label the order of node visits explicitly. Even a small omission can lead to lost marks. Practice handwriting traces for BFS, DFS, Dijkstra, and MST algorithms regularly.

WJEC 考试要求对图算法进行详细的逐步追踪。作答时务必清晰展示所使用的数据结构（队列、栈、优先队列、距离数组、前驱列表），每次迭代记录变化，并明确标出节点访问顺序。细微遗漏都会导致扣分。请定期手写练习 BFS、DFS、Dijkstra 和 MST 的追踪。

Use a separate table for distances, visited flags, and predecessors. | 用独立表格记录距离、访问标记和前驱。
Show priority queue contents after each operation. | 每次操作后展示优先队列的内容。
Use consistent notation, e.g. ∞ for infinity, ⌀ for null predecessor. | 使用统一符号，如 ∞ 表示无穷，⌀ 表示空前驱。

12. Common Pitfalls & Revision Tips | 常见易错点与复习建议

Confusing BFS with DFS order is a frequent error; remember the underlying data structure. Another mistake is applying Dijkstra to negative edge graphs — always check edge weights first. For MST, some students add edges that create cycles because they forget the tree property. When tracing, never assume alphabetical neighbour order is the only possibility; follow the order given in the adjacency list. Finally, in A*, verify the heuristic’s admissibility. Revision tip: create concise algorithm summary cards and practice past paper traces under timed conditions.

混淆 BFS 与 DFS 的访问顺序是常见错误，牢记底层数据结构。另一错误是将 Dijkstra 用于负权图——务必先检查边权。对于 MST，有些学生因遗忘树的无环性质而加入了成环边。追踪时，不要假定邻居顺序一定是字母序；须遵循题目给出的邻接表顺序。最后，在 A* 中验证启发式的可采纳性。复习建议：制作简洁的算法摘要卡片，并限时刷往年真题的追踪题。

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

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

Graph Algorithms | 图算法 考点精讲