Graph Algorithms for IB & OCR Computer Science | IB OCR 计算机：图算法 考点精讲

📚 Graph Algorithms for IB & OCR Computer Science | IB OCR 计算机：图算法 考点精讲

Graph algorithms form a core part of the IB Computer Science (HL) and OCR A Level specifications, bridging abstract data structures with real‑world problem solving. From depth‑first search to Dijkstra and A*, mastering these methods is essential for both paper‑based tracing questions and algorithmic thinking tasks. This article unpacks every key graph algorithm you need, with parallel English‑Chinese explanations, worked examples, and common pitfalls.

图算法是 IB 计算机科学（高水平）和 OCR A Level 规范中的核心内容，它将抽象数据结构与现实世界的问题求解联系起来。从深度优先搜索到 Dijkstra 和 A* 算法，掌握这些方法对于笔试卷中的跟踪题和算法思维任务都至关重要。本文拆解你需要掌握的每一个关键图算法，提供中英文对照讲解、示例和常见陷阱。

1. Graph Fundamentals and Terminology | 图的基本概念与术语

A graph G = (V, E) consists of a set of vertices (nodes) V and a set of edges E that connect pairs of vertices. In an undirected graph, edges have no direction; in a directed graph (digraph), each edge has an associated direction. A weighted graph assigns a numerical weight to each edge, representing cost, distance, or capacity. Key terms include: path (a sequence of vertices connected by edges), cycle (a path that starts and ends at the same vertex with no repeated edges), degree (the number of edges incident to a vertex), and adjacency (two vertices connected by an edge). Undirected graphs have a maximum of |V|(|V|‑1)/2 edges, while directed graphs can have up to |V|(|V|‑1) edges if self‑loops are excluded. Self‑loops (edges from a vertex to itself) and multiple edges between the same pair of vertices give rise to multigraphs, but most exam contexts assume simple graphs (no self‑loops, no multiple edges).

图 G = (V, E) 由顶点（节点）集合 V 和边集合 E 组成，边连接顶点对。在无向图中，边没有方向；在有向图中，每条边都有指定的方向。加权图为每条边分配一个数值权重，表示成本、距离或容量。关键术语包括：路径（由边连接的顶点序列）、回路（起点和终点相同且没有重复边的路径）、度（与一个顶点关联的边的数量）以及邻接（由一条边连接的两个顶点）。无向图最多有 |V|(|V|‑1)/2 条边，而有向图如果不包含自环，最多有 |V|(|V|‑1) 条边。自环（从顶点到自身的边）以及同一对顶点之间的多条边会构成多重图，但大多数考试情境都默认简单图（无自环，无多重边）。

---

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

Two standard representations dominate exam syllabi: the adjacency matrix and the adjacency list. An adjacency matrix is a 2D array A of size |V| × |V|, where A[i][j] = 1 (or the edge weight) if there is an edge from vertex i to vertex j, and 0 otherwise. For an undirected graph the matrix is symmetric. Memory usage is O(|V|²) — efficient for dense graphs but wasteful for sparse ones. Edge existence queries are O(1); iterating over neighbours takes O(|V|) per vertex.

考试大纲中主要有两种标准表示方法：邻接矩阵和邻接表。邻接矩阵是一个大小为 |V| × |V| 的二维数组 A，如果从顶点 i 到顶点 j 存在一条边，则 A[i][j] = 1（或边的权重），否则为 0。对于无向图，矩阵是对称的。内存开销为 O(|V|²) —— 对稠密图效率高，但对稀疏图很浪费。查询边是否存在的时间复杂度为 O(1)；遍历一个顶点的所有邻居需要 O(|V|) 时间。

An adjacency list stores, for each vertex, a list (or dynamic array) of its adjacent vertices. For a weighted graph, each entry in the list also stores the edge weight. Total memory is O(|V| + |E|) — ideal for sparse graphs. Looking up a specific edge requires O(degree) time; listing all neighbours is O(degree). Because real‑world graphs are often sparse, adjacency lists are generally preferred in practical algorithms when iteration over neighbours is frequent.

邻接表为每个顶点存储一个列表（或动态数组），其中包含与之相邻的顶点。对于加权图，列表中的每个条目还会存储边的权重。总内存为 O(|V| + |E|) —— 非常适合稀疏图。查询某条特定边需要 O(度) 时间；列出所有邻居为 O(度)。由于现实世界中的图往往是稀疏的，当频繁地遍历邻居时，实际算法通常更倾向于使用邻接表。

---

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

DFS explores a graph by going as deep as possible along a branch before backtracking. It can be implemented recursively (using the call stack) or iteratively with an explicit stack. The algorithm marks vertices as visited to avoid cycles. DFS produces a depth‑first tree (or forest for disconnected graphs) and is used for cycle detection, topological sorting, and finding connected components. The time complexity is O(|V| + |E|) for adjacency‑list representation.

DFS 沿着一条分支尽可能深入，然后再回溯，以此探索图。它可以用递归方式实现（借助调用栈），也可以用显式栈迭代实现。算法会对顶点进行已访问标记以避免循环。DFS 会生成深度优先生成树（不连通图则生成森林），并用于检测回路、拓扑排序以及寻找连通分量。使用邻接表表示时，时间复杂度为 O(|V| + |E|)。

Pseudocode for iterative DFS:

DFS(start):
  stack.push(start)
  while stack not empty:
    v = stack.pop()
    if v not visited:
      mark v as visited
      for each neighbour u of v:
        if u not visited: stack.push(u)

迭代 DFS 的伪代码：

In exams you may be asked to trace DFS on a given graph, showing the order of vertex visits and the state of the stack. A typical pitfall is pushing neighbours in the wrong order (remember the stack reverses the order of processing relative to a recursive implementation unless you push in reverse order). Also, disconnected graphs require a loop over all vertices, calling DFS on each unvisited vertex.

考试中可能会要求你在给定图上跟踪 DFS，展示顶点访问顺序和栈的状态。一个典型的陷阱是邻居入栈的顺序错误（注意，栈的处理顺序与递归实现相反，除非你反过来入栈）。此外，对于不连通图，需要对所有顶点进行循环，为每个未访问的顶点调用 DFS。

---

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

BFS explores a graph level by level, starting from a source vertex. It uses a queue to maintain the frontier of exploration. BFS computes the shortest path in terms of the number of edges (unweighted graphs) and is the basis for many algorithms like Dijkstra. Time complexity is the same as DFS: O(|V| + |E|). BFS is preferred when the shortest unweighted path is needed or when exploring relationships by distance layers.

BFS 从源顶点开始，逐层探索图。它使用队列维护探索前沿。BFS 可以计算出基于边数的最短路径（无权图），而且是 Dijkstra 等许多算法的基础。时间复杂度与 DFS 相同：O(|V| + |E|)。当需要无权图的最短路径，或按照距离层次探索关系时，BFS 是首选。

BFS pseudocode:

BFS(start):
  queue.enqueue(start)
  mark start as visited
  while queue not empty:
    v = queue.dequeue()
    for each neighbour u of v:
      if u not visited:
        mark u as visited
        queue.enqueue(u)

BFS 伪代码：

Typically, a BFS tree is constructed by recording the parent of each newly discovered vertex, which then allows the reconstruction of the shortest path. In OCR questions you may be asked to show the order vertices are dequeued, or to illustrate the BFS tree for a given graph.

通常，通过记录每个新发现顶点的父节点来构建 BFS 树，从而可以重建最短路径。在 OCR 题目中，可能会要求你展示顶点的出队顺序，或者为给定图画出 BFS 树。

---

5. Shortest Paths: Dijkstra’s Algorithm | 最短路径：Dijkstra 算法

Dijkstra’s algorithm finds the shortest paths from a single source to all other vertices in a weighted graph with non‑negative edge weights. It maintains a set of vertices whose final shortest distance from the source is known, and repeatedly selects the vertex with the smallest tentative distance, updating the distances of its neighbours. With a binary heap, the time complexity is O((|V|+|E|) log |V|); with a Fibonacci heap it improves to O(|E| + |V| log |V|).

Dijkstra 算法用于在边权重非负的加权图中，寻找从单一源到所有其他顶点的最短路径。它维护一个顶点集合，这些顶点到源点的最终最短距离已经确定，然后不断选择具有最小暂定距离的顶点，并更新其邻居的距离。使用二叉堆时，时间复杂度为 O((|V|+|E|) log |V|)；使用斐波那契堆可改进到 O(|E| + |V| log |V|)。

Simplified Dijkstra pseudocode (without heap optimisations):

Dijkstra(Graph, source):
  dist[source] = 0
  for all other vertices v: dist[v] = ∞
  unvisited = set of all vertices
  while unvisited not empty:
    u = vertex in unvisited with min dist[u]
    remove u from unvisited
    for each neighbour v of u still in unvisited:
      alt = dist[u] + weight(u,v)
      if alt < dist[v]:
        dist[v] = alt
        prev[v] = u

简化的 Dijkstra 伪代码（不含堆优化）：

Dijkstra fails when negative edge weights exist; in that case the Bellman‑Ford algorithm (O(|V|·|E|)) must be used. Neither IB nor OCR typically demands Bellman‑Ford implementation, but recognising the limitation is important. Another frequent exam requirement is tracing Dijkstra step by step with a table of distances and predecessor vertices.

当存在负权边时，Dijkstra 算法会失效；在这种情况下必须使用 Bellman‑Ford 算法（O(|V|·|E|)）。IB 和 OCR 通常不要求实现 Bellman‑Ford，但认识到这一局限性很重要。另一个常见的考试要求是，使用距离和前驱顶点的表格，逐步跟踪 Dijkstra 的过程。

---

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

A* is an informed search algorithm that extends Dijkstra by using a heuristic function h(n) estimating the cost from node n to the goal. It evaluates nodes based on f(n) = g(n) + h(n), where g(n) is the exact cost from the start to n. A* is admissible (guarantees an optimal path) if h(n) never overestimates the true cost. A* is widely used in pathfinding for games, robotics, and OCR A Level questions on route finding. With a perfect heuristic, A* behaves like Dijkstra; with a constant heuristic (h(n)=0), it reduces exactly to Dijkstra. Time complexity depends heavily on the heuristic quality and can be exponential in the worst case, but practically it often outperforms Dijkstra on large grids.

A* 是一种启发式搜索算法，它通过使用启发函数 h(n) 来估计从节点 n 到目标的代价，从而对 Dijkstra 进行扩展。它根据 f(n) = g(n) + h(n) 来评估节点，其中 g(n) 是从起点到 n 的精确代价。如果 h(n) 从未高估真实代价，则 A* 是可采纳的（保证最优路径）。A* 广泛用于游戏寻路、机器人技术以及 OCR A Level 中的路径查找题目。如果启发函数完美，A* 的行为类似于 Dijkstra；如果启发函数为常量（h(n)=0），则完全退化为 Dijkstra。时间复杂度很大程度上取决于启发函数的质量，最坏情况下可能是指数级的，但在实际的大规模网格上通常优于 Dijkstra。

A* pseudocode (simplified):

A*(start, goal):
  openSet = {start}
  g[start] = 0, f[start] = h(start)
  while openSet not empty:
    current = node in openSet with lowest f
    if current == goal: return reconstruct path
    remove current from openSet
    for each neighbour of current:
      tentative_g = g[current] + weight
      if tentative_g < g[neighbour]:
        parent[neighbour] = current
        g[neighbour] = tentative_g
        f[neighbour] = g[neighbour] + h(neighbour)
        if neighbour not in openSet: add it

A* 伪代码（简化）：

A common heuristic for grid maps is the Manhattan distance (|x1‑x2| + |y1‑y2|) when movement is limited to four directions, or Euclidean distance when diagonal movement is allowed. In OCR exams, you may encounter A* with a given heuristic table and be asked to trace the algorithm, noting which node is expanded next and showing the open and closed lists.

对于网格地图，当移动方向仅限于四个方向时，常用的启发函数是曼哈顿距离 (|x1‑x2| + |y1‑y2|)；当允许对角线移动时，则使用欧几里得距离。在 OCR 考试中，你可能会遇到带有给定启发函数表的 A* 题目，需要跟踪算法，标注下一个展开的节点，并展示开放列表和关闭列表。

---

7. Minimum Spanning Tree: Kruskal and Prim | 最小生成树：Kruskal 与 Prim 算法

A minimum spanning tree (MST) of a weighted, undirected graph is a subset of edges that connects all vertices with the minimum total edge weight and no cycles. Two classic greedy algorithms are examined: Kruskal’s algorithm and Prim’s algorithm. Kruskal’s sorts all edges by weight and adds them one by one if they do not create a cycle (using a union‑find data structure). Time complexity is O(|E| log |E|) or O(|E| log |V|) with optimisations. Prim’s algorithm grows the MST from an arbitrary starting vertex, always adding the cheapest edge that connects the current tree to a vertex outside. With a binary heap it runs in O(|E| log |V|).

加权无向图的最小生成树（MST）是一个边的子集，它连接所有顶点，总边权最小，且无环。考试中涉及两种经典的贪心算法：Kruskal 算法和 Prim 算法。Kruskal 将所有边按权重排序，然后依次添加不构成回路的边（借助并查集数据结构）。时间复杂度为 O(|E| log |E|) 或经过优化为 O(|E| log |V|)。Prim 算法从任意起始顶点开始逐步构建 MST，始终添加连接当前树与外部顶点的最便宜边。使用二叉堆时，时间复杂度为 O(|E| log |V|)。

Kruskal’s pseudocode:

Kruskal(Graph):
  sort all edges by weight ascending
  MST = empty
  for each edge (u,v) in sorted order:
    if u and v are in different sets:
      add (u,v) to MST
      union the sets of u and v

Kruskal 伪代码：

Prim’s pseudocode:

Prim(Graph, start):
  MST = empty
  priority queue Q (key = edge weight)
  visited = set
  add start to visited
  for each edge from start: push to Q
  while Q not empty and visited ≠ all vertices:
    edge (u,v) = Q.pop() (min weight)
    if v not visited:
      add (u,v) to MST
      add v to visited
      for each edge from v to unvisited w:
        push (v,w) to Q

Prim 伪代码：

Examiners often ask students to run either algorithm on a small graph, writing the order of edge selection or drawing the intermediate stages. IB questions may ask for the purpose of MST algorithms in network design, such as laying cables or minimising road construction costs.

考官经常要求学生在小图上执行算法，写出边选择顺序或画出中间步骤。IB 题目可能会问 MST 算法在网络设计中的用途，例如铺设电缆或最小化道路建设成本。

---

8. Topological Sorting | 拓扑排序

Topological sorting applies only to directed acyclic graphs (DAGs). It produces a linear ordering of vertices such that for every directed edge (u, v), u appears before v. Two standard methods exist: Kahn’s algorithm and DFS‑based approach. Kahn’s algorithm repeatedly removes vertices with in‑degree zero. The DFS method performs a depth‑first search and pushes each vertex onto a stack when its recursion finishes; the final stack contains the topological order (reverse order). Time complexity for both is O(|V| + |E|).

拓扑排序仅适用于有向无环图（DAG）。它生成一个顶点的线性排序，使得对于每一条有向边 (u, v)，u 都出现在 v 之前。存在两种标准方法：Kahn 算法和基于 DFS 的方法。Kahn 算法反复移除入度为零的顶点。DFS 方法执行深度优先搜索，当每个顶点的递归结束时将其压入栈中；最终的栈即为拓扑顺序（逆序）。两者的时间复杂度都是 O(|V| + |E|)。

Kahn’s algorithm pseudocode:

Kahn(Graph):
  compute in‑degree of all vertices
  queue Q = all vertices with in‑degree 0
  topo_order = []
  while Q not empty:
    u = Q.dequeue()
    append u to topo_order
    for each neighbour v of u:
      decrement in‑degree[v]
      if in‑degree[v] == 0: Q.enqueue(v)
  if len(topo_order) ≠ |V|: graph has a cycle

Kahn 算法伪代码：

Topological sorting is frequently tested in IB HL Paper 2 and OCR algorithms questions, often in the context of scheduling tasks with prerequisites. Be careful: a topological order is not unique unless the DAG has a chain structure.

拓扑排序在 IB HL 试卷二和 OCR 算法题中经常出现，通常背景是带有先修条件的任务调度。注意：除非 DAG 具有链状结构，否则拓扑顺序不是唯一的。

---

9. Detecting Cycles in Graphs | 图中的环路检测

Cycle detection depends on the graph type. For undirected graphs, DFS can detect a cycle if a back edge (to an already visited vertex that is not the immediate parent) is found. Keep track of parent vertices to distinguish a back edge from revisiting the parent. In directed graphs, a DFS that colours vertices (white = unvisited, grey = in current recursion stack, black = finished) detects a cycle when an edge leads to a grey vertex. Union‑find also detects cycles for both undirected and directed static graphs, but uses a different principle. Time complexity is O(|V| + |E|) for the DFS methods.

环路检测取决于图的类型。对于无向图，如果 DFS 发现一条回边（指向一个已访问且不是直接父顶点的顶点），则可检测到环路。通过记录父顶点来区分回边和重复访问父顶点。在有向图中，使用对顶点进行着色的 DFS（白色 = 未访问，灰色 = 当前递归栈中，黑色 = 已完成），当一条边指向灰色顶点时即可检测到环路。并查集也可检测无向图和有向静态图的环路，但原理不同。DFS 方法的时间复杂度为 O(|V| + |E|)。

Coloured DFS for directed graph:

DFS_cycle(v):
  colour[v] = grey
  for each neighbour u of v:
    if colour[u] == grey: return true (cycle)
    if colour[u] == white and DFS_cycle(u): return true
  colour[v] = black
  return false

有向图的着色 DFS：

In OCR, cycle detection may be embedded in a larger problem, such as checking whether a dependency graph can be scheduled. IB students should be able to explain and code a simple cycle detection routine.

在 OCR 中，环路检测可能嵌入到更大的问题中，例如检查依赖图是否可被调度。IB 学生应能解释并编写简单的环路检测程序。

---

10. Graph Traversal Tracing and Common Exam Pitfalls | 图的遍历跟踪与常见考试陷阱

Exam questions frequently require manual tracing of BFS, DFS, Dijkstra, or A*. Students lose marks by not following the algorithm’s specific order. For DFS, the order neighbours are pushed onto the stack matters: if the adjacency list gives neighbours as [C, B] and you push them in that order, B will be popped first because of LIFO. For BFS, the queue FIFO order means that if you enqueue A, then B, then C, you dequeue A first. Always simulate the exact data structure (stack or queue) graphically or in a table. A table with columns ‘Vertex’, ‘Distance’, ‘Predecessor’, and ‘Visited’ is recommended for Dijkstra and A*. In A*, always maintain f(n) = g(n) + h(n) and show the open/closed sets distinctly.

考试题目经常要求手动跟踪 BFS、DFS、Dijkstra 或 A* 的过程。学生若未遵循算法指定的顺序就会丢分。对于 DFS，邻居压入栈的顺序很重要：如果邻接表给出的邻居是 [C, B]，你按该顺序压入，那么由于后进先出（LIFO）的特性，B 会先出栈。对于 BFS，队列的先进先出（FIFO）顺序意味着如果你依次入队 A、B、C，你会最先让 A 出队。一定要用图形或表格模拟具体的数据结构（栈或队列）。Dijkstra 和 A* 建议使用包括“顶点”、“距离”、“前驱”、“已访问”等列的表格。在 A* 中，始终维护 f(n) = g(n) + h(n)，并清晰地展示开放集和关闭集。

Other frequent pitfalls: forgetting to check for cycles in DFS/BFS (leading to infinite loops), not resetting visited flags for multiple runs, mixing up the MST algorithms (Kruskal adds edges globally, Prim expands from a tree), and applying Dijkstra to graphs with negative weights. For adjacency matrices, ensure you can convert between matrix and list representations and analyse space complexity. IB Paper 2 may present pseudo‑code with syntax variations; be prepared to interpret and trace code given in a specific format.

其他常见陷阱：DFS/BFS 忘记检测环路（导致无限循环）、多次运行时未重置已访问标记、混淆 MST 算法（Kruskal 全局选边，Prim 从树扩展）、以及对存在负权边的图使用 Dijkstra。对于邻接矩阵，要确保能够在矩阵和列表表示之间进行转换，并分析空间复杂度。IB 试卷二可能会给出带有语法变体的伪代码；要做好准备去解释和跟踪特定格式的代码。

---

11. Comparative Summary of Graph Algorithms | 图算法对比总结

The following table summarises the key algorithms, their use cases, and complexities, providing a quick revision aid for IB and OCR candidates.

下表总结了关键算法的用途和复杂度，为 IB 和 OCR 考生提供快速复习参考。

Algorithm (算法)	Purpose (用途)	Weighted? (加权?)	Time Complexity (时间复杂度)	Special Condition (特殊条件)
DFS	Connectivity, cycle detection, topological order	No	O(|V|+|E|)	—
BFS	Shortest unweighted path, level order	No	O(|V|+|E|)	—
Dijkstra	Single‑source shortest path	Yes (non‑negative)	O((|V|+|E|) log |V|)	No negative weights
A*	Goal‑directed shortest path	Yes (non‑negative)	Depends on heuristic	Admissible heuristic
Kruskal	Minimum spanning tree	Yes	O(|E| log |E|)	Undirected graph
Prim	Minimum spanning tree	Yes	O(|E| log |V|)	Undirected graph
Topological Sort	DAG ordering	No	O(|V|+|E|)	Directed acyclic graph

This comparative view highlights that many graph algorithms share a linear‑plus‑edges component, but details like weight constraints and data structure choices (stack vs queue vs priority queue) critically differentiate them. Practice tracing each type until the mechanics become second nature.

这个对比视图强调了，许多图算法都共享一个“顶点数加边数”的线性部分，但权重约束和数据结构选择（栈、队列、优先队列）等细节，使它们截然不同。请持续练习跟踪每种类型，直到操作机制变为直觉反应。

---

12. Final Examination Tips and Further Reading | 考试技巧与拓展阅读

When approaching IB or OCR graph algorithm questions, always read the problem statement carefully to identify which algorithm is appropriate. Look for keywords: “shortest path” suggests Dijkstra or A* (with heuristic given); “connected components” suggests DFS/BFS; “minimum cost to connect all nodes” implies MST; “ordering of tasks” points to topological sort. If asked to “trace the algorithm” but no heuristic is given, Dijkstra is the safest bet for weighted graphs, and BFS for unweighted grids. For OCR A Level, the A* algorithm often comes with a grid and a heuristic table — do not forget to calculate f(n) at each step and to mark nodes as visited (closed) after expansion.

在处理 IB 或 OCR 图算法问题时，务必仔细阅读题目描述，判断应使用哪种算法。留意关键词：“最短路径” 暗示 Dijkstra 或 A*（提供了启发函数）；“连通分量” 暗示 DFS/BFS；“连接所有节点的最小成本” 意味着 MST；“任务排序” 指向拓扑排序。如果要求“跟踪算法”，但未给出启发函数，那么对于加权图 Dijkstra 最稳妥，对于无权网格则用 BFS。对于 OCR A Level，A* 算法常与网格和启发函数表一起出现——不要忘记每一步都计算 f(n)，并在展开后将节点标记为已访问（关闭）。

Beyond the exam, graph algorithms underpin many modern technologies: routing

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

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