Graph Algorithms | 图算法考点精讲

📚 Graph Algorithms | 图算法考点精讲

Graph algorithms form a core part of the A-Level Computer Science syllabus, enabling students to model and solve real-world problems such as network routing, social connections, and dependency analysis. Mastering graph traversal, shortest path, and minimum spanning tree algorithms not only secures high marks in the exam but also builds a solid foundation for further study in computer science. This article breaks down every essential graph algorithm, explaining their mechanisms, providing step-by-step worked examples, and highlighting common pitfalls, all in alignment with A-Level assessment objectives.

图算法是 A-Level 计算机科学课程的核心组成部分，能够让学生建模并解决现实世界中的问题，例如网络路由、社交连接和依赖分析。掌握图的遍历、最短路径和最小生成树算法，不仅能在考试中稳拿高分，还能为后续计算机科学的学习打下坚实基础。本文逐一剖析所有必考图算法，解释其工作机制，提供逐步解题示例，并指出常见易错点，完全贴合 A-Level 评估目标。

1. What Is a Graph? | 什么是图？

A graph is an abstract data structure consisting of vertices (nodes) and edges (arcs) that connect pairs of vertices. Edges can be directed (one-way) or undirected (two-way), and may carry weights to represent cost, distance, or capacity. Graphs are used to represent networks, maps, web links, and more.

图是一种抽象数据结构，由顶点（节点）和连接顶点对的边（弧）组成。边可以是有向的（单向）或无向的（双向），并且可以带有权重，用来表示代价、距离或容量。图用于表示网络、地图、网页链接等。

Key terminology: A vertex is a fundamental unit; an edge e = (u, v) links vertex u to v. In a weighted graph, each edge has a numerical weight. A path is a sequence of vertices where each adjacent pair is connected by an edge. A cycle is a path that starts and ends at the same vertex without repeating edges.

关键术语：顶点是基本单元；边 e = (u, v) 连接顶点 u 和 v。在带权图中，每条边都有一个数值权重。路径是一系列顶点，其中每一对相邻顶点都由一条边连接。环是一条起点和终点相同且不重复边的路径。

2. Graph Representation: Adjacency Matrix vs Adjacency List | 图的表示：邻接矩阵与邻接表

A graph can be stored in a computer using either an adjacency matrix or an adjacency list. The choice depends on the density of the graph and the types of operations required.

图可以用邻接矩阵或邻接表存储在计算机中。选择哪种方式取决于图的密度和所需操作的类型。

An adjacency matrix is a 2D array of size V×V, where V is the number of vertices. If there is an edge from vertex i to vertex j, the cell matrix[i][j] = 1 (or the weight). For undirected graphs, the matrix is symmetric. This representation allows O(1) edge lookups but consumes O(V²) space, making it inefficient for sparse graphs.

邻接矩阵是一个大小为 V×V 的二维数组，其中 V 是顶点数。如果存在从顶点 i 到顶点 j 的边，则单元格 matrix[i][j] = 1（或权重）。对于无向图，矩阵是对称的。这种表示法可以实现 O(1) 的边查找，但占用 O(V²) 空间，对于稀疏图效率低下。

An adjacency list stores, for each vertex, a list of adjacent vertices (and weights if applicable). It uses O(V + E) space, ideal for sparse graphs. However, checking whether a specific edge exists may take O(degree) time.

邻接表为每个顶点存储一个相邻顶点列表（以及适用的权重）。它使用 O(V + E) 空间，非常适合稀疏图。然而，检查某条特定边是否存在可能需要 O(度) 的时间。

Representation	Space	Edge Query	Best for
Adjacency Matrix	O(V²)	O(1)	Dense graphs
Adjacency List	O(V + E)	O(degree)	Sparse graphs

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

DFS explores a graph by going as deep as possible along each branch before backtracking. It can be implemented using a stack (explicitly or via recursion). DFS is particularly useful for topological sorting, cycle detection, and path existence checks.

DFS 通过尽可能深入地沿着每条分支探索图，然后回溯。它可以用栈（显式或通过递归）来实现。DFS 特别适用于拓扑排序、环路检测和路径存在性检查。

Algorithm steps: Start at a given vertex. Mark it as visited. For each unvisited neighbour, recursively perform DFS from that neighbour. If using an explicit stack, push the starting vertex, then while the stack is not empty, pop a vertex, mark and push its unvisited neighbours.

算法步骤：从给定顶点开始。将其标记为已访问。对于每个未访问的邻居，从该邻居递归执行 DFS。如果使用显式栈，则将起始顶点入栈，然后当栈不为空时，弹出一个顶点，标记并将其未访问的邻居入栈。

For a graph with V vertices and E edges, DFS time complexity is O(V + E) because each vertex and edge is processed once. Space complexity is O(V) in the worst case due to the recursion stack or explicit stack.

对于具有 V 个顶点和 E 条边的图，DFS 的时间复杂度为 O(V + E)，因为每个顶点和边只处理一次。由于递归栈或显式栈，最坏情况下的空间复杂度为 O(V)。

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

BFS explores vertices level by level, starting from a source vertex. It uses a queue to keep track of vertices to visit next. BFS is ideal for finding the shortest path in an unweighted graph and for level-order traversal.

BFS 从源顶点开始，逐层探索顶点。它使用一个队列来跟踪接下来要访问的顶点。BFS 非常适合在未加权图中寻找最短路径以及进行层序遍历。

Steps: Enqueue the starting vertex and mark it visited. While the queue is not empty, dequeue a vertex, process it, and enqueue all its unvisited neighbours, marking them visited. This ensures vertices are visited in order of their distance from the source.

步骤：将起始顶点入队并标记为已访问。当队列不为空时，出队一个顶点，处理它，然后将其所有未访问的邻居入队，并标记为已访问。这确保了顶点按照与源顶点的距离顺序被访问。

BFS also runs in O(V + E) time and uses O(V) space. Because of its level-by-level nature, BFS can be used to compute the shortest path (in terms of number of edges) from a source to all other nodes in an unweighted graph.

BFS 的时间复杂度也是 O(V + E)，空间复杂度为 O(V)。由于其逐层特性，BFS 可用于在未加权图中计算从源点到所有其他节点的最短路径（按边数计）。

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

Although both traversals visit all reachable vertices, they differ in data structure, order of visitation, and typical applications. DFS uses a stack (LIFO) while BFS uses a queue (FIFO).

虽然这两种遍历都会访问所有可达顶点，但它们在数据结构、访问顺序和典型应用上有所不同。DFS 使用栈（后进先出），而 BFS 使用队列（先进先出）。

DFS dives deep into a graph, which can lead to finding a path quickly but not necessarily the shortest. It requires less memory for wide graphs. DFS is better for puzzles, maze solving, and topological ordering. BFS, on the other hand, guarantees the shortest path in terms of edges and is preferred in social networking friend suggestions and web crawling.

DFS 深入图内部，可以快速找到路径，但不一定是最短路径。对于宽图，它需要的内存较少。DFS 更适合谜题、迷宫求解和拓扑排序。另一方面，BFS 保证在边数上是最短路径，因此更适合社交网络的好友推荐和网页爬虫。

Feature	DFS	BFS
Data Structure	Stack	Queue
Path Found	Not necessarily shortest	Shortest (unweighted)
Memory	O(V) recursion depth	O(V) queue
Typical Use	Topological sort, cycle detection	Shortest path, level order

6. Shortest Path Problem and Dijkstra’s Algorithm | 最短路径问题与 Dijkstra 算法

In a weighted graph where all edge weights are non-negative, Dijkstra’s algorithm finds the shortest path from a single source to all other vertices. It uses a priority queue to repeatedly select the unvisited vertex with the smallest tentative distance.

在所有权重为非负的带权图中，Dijkstra 算法可以找到从单一源点到所有其他顶点的最短路径。它使用优先队列，重复选择具有最小暂定距离的未访问顶点。

Maintain an array dist[] where dist[source] = 0 and others start as infinity. Also maintain a priority queue of (distance, vertex). Extract the minimum, if the extracted distance is greater than the recorded distance, skip it (outdated entry). For each neighbour of u, if dist[u] + weight(u, v) < dist[v], update dist[v] and push (dist[v], v) into the queue.

维护一个数组 dist[]，其中 dist[源点] = 0，其他初始化为无穷大。同时维护一个 (距离, 顶点) 的优先队列。提取最小值，如果提取出的距离大于已记录的距离，则跳过（过时的条目）。对于 u 的每个邻居 v，如果 dist[u] + weight(u, v) < dist[v]，则更新 dist[v] 并将 (dist[v], v) 压入队列。

Dijkstra’s algorithm does not work with negative edge weights because the greedy assumption fails. Its time complexity with a binary heap is O((V + E) log V).

Dijkstra 算法不适用于负权边，因为贪心假设会失效。使用二叉堆实现时，其时间复杂度为 O((V + E) log V)。

7. Dijkstra’s Algorithm Worked Example | Dijkstra 算法示例

Consider a graph with vertices A, B, C, D, E. Edges: A-B(6), A-D(1), B-C(5), B-D(2), D-E(1), E-B(2), E-C(5). Find the shortest paths from A.

考虑一个图，顶点为 A, B, C, D, E。边：A-B(6), A-D(1), B-C(5), B-D(2), D-E(1), E-B(2), E-C(5)。求从 A 出发的最短路径。

Initialise dist: A=0, others=∞. Queue: (0,A). Extract A: neighbours D (dist 1) and B (dist 6). Update. Queue: (1,D), (6,B). Extract D (dist=1): neighbours B (1+2=3 < 6) update B to 3; E (1+1=2). Queue: (2,E), (3,B), (6,B). Extract E (2): neighbours B (2+2=4 >3 no update), C (2+5=7). Queue: (3,B), (6,B), (7,C). Extract B (3): neighbour C (3+5=8 >7 no update). Queue: (6,B), (7,C). Extract B (6) outdated skip. Extract C (7). Final distances: A=0, B=3, C=7, D=1, E=2.

初始化 dist：A=0，其他=∞。队列：(0,A)。取出 A：邻居 D（距离 1）和 B（距离 6）。更新。队列：(1,D), (6,B)。取出 D（dist=1）：邻居 B（1+2=3 < 6）更新 B 为 3；E（1+1=2）。队列：(2,E), (3,B), (6,B)。取出 E（2）：邻居 B（2+2=4 >3 不更新），C（2+5=7）。队列：(3,B), (6,B), (7,C)。取出 B（3）：邻居 C（3+5=8 >7 不更新）。队列：(6,B), (7,C)。取出 B（6）过时跳过。取出 C（7）。最终距离：A=0, B=3, C=7, D=1, E=2。

This step-by-step process highlights the importance of ignoring outdated entries in the priority queue, a detail often tested in exams.

这个逐步过程突显了忽略优先队列中过时条目的重要性，而这往往是考试中考查的细节。

8. Minimum Spanning Tree (MST) and Prim’s Algorithm | 最小生成树与 Prim 算法

A minimum spanning tree connects all vertices of a weighted, undirected graph with the smallest total edge weight and without cycles. Prim’s algorithm builds the MST by starting from an arbitrary vertex and repeatedly adding the cheapest edge that connects a tree vertex to a non-tree vertex.

最小生成树用最小的总边权重连接带权无向图的所有顶点，且不含环。Prim 算法从任意顶点开始，重复添加连接树内顶点与树外顶点的最便宜边，从而构建 MST。

Maintain a set of visited vertices. Initialise all key values as infinity except the start vertex (0). Use a priority queue to extract the vertex with the minimum key value, add it to the MST set, and update keys of adjacent unvisited vertices if the edge weight is less than their current key.

维护一个已访问顶点集合。将所有顶点的关键值初始化为无穷大，起始顶点除外（0）。使用优先队列提取具有最小关键值的顶点，将其加入 MST 集合，并更新相邻未访问顶点的关键值（如果边权重小于该顶点的当前关键值）。

Prim’s algorithm closely resembles Dijkstra’s but the key difference is that Prim’s key is the minimum edge weight to connect to the current tree, whereas Dijkstra’s key is the total path length from the source. Both run in O((V + E) log V) with a binary heap.

Prim 算法与 Dijkstra 算法非常相似，但关键区别在于 Prim 的关键值是连接到当前树的最小边权重，而 Dijkstra 的关键值是从源点出发的总路径长度。两者在使用二叉堆时的时间复杂度均为 O((V + E) log V)。

9. Kruskal’s Algorithm | Kruskal 算法

Kruskal’s algorithm is another greedy approach to find the MST. It sorts all edges by weight and adds them one by one to the growing forest, ensuring no cycle is formed, typically using a disjoint-set data structure (union-find).

Kruskal 算法是另一种寻找 MST 的贪心方法。它按权重对所有边进行排序，然后逐一将边添加到不断增长的森林中，同时确保不形成环，通常使用不相交集数据结构（并查集）。

Steps: 1) Sort edges in ascending order of weight. 2) Initialise each vertex as its own set. 3) For each edge (u, v) in sorted order, if u and v belong to different sets, add edge to MST and union their sets. Stop when V-1 edges have been added.

步骤：1) 按权重升序排列所有边。2) 将每个顶点初始化为自己的集合。3) 对于排序后的每条边 (u, v)，如果 u 和 v 属于不同的集合，则将该边加入 MST 并合并它们的集合。当已添加 V-1 条边时停止。

Kruskal’s algorithm works well for sparse graphs because sorting edges dominates the time, yielding O(E log E) or O(E log V) since E ≤ V². It is often more intuitive to trace manually in exam questions because of the edge-sorting step.

Kruskal 算法适用于稀疏图，因为排序边是时间复杂度的主导部分，得到 O(E log E) 或 O(E log V)（因为 E ≤ V²）。由于其边排序步骤，在考试题目中手动跟踪往往更直观。

10. Comparing Prim’s and Kruskal’s Algorithms | Prim 与 Kruskal 算法的比较

Both algorithms produce the same minimum total weight if all edge weights are distinct, but the chosen edges may differ if there are multiple minima. Prim’s builds the tree from a single connected component, while Kruskal’s can grow a forest before connecting all components.

如果所有边的权重都互不相同，两种算法将产生相同的最小总权重，但如果存在多个最小值，所选的边可能会有所不同。Prim 算法从单个连通分量构建树，而 Kruskal 算法在连接所有分量之前，可能会先生成森林。

Prim’s is typically faster for dense graphs using adjacency matrix representation (O(V²) without a heap), while Kruskal’s is preferred for sparse graphs because sorting edges is efficient. A-Level questions may ask you to run both on the same graph and note the differences.

Prim 算法使用邻接矩阵表示（无堆时为 O(V²)）时通常在稠密图上更快，而 Kruskal 算法在稀疏图上更受偏爱，因为排序边的效率更高。A-Level 题目可能会要求你在同一个图上运行两种算法，并注意其差异。

Aspect	Prim’s	Kruskal’s
Starting point	Arbitrary vertex	Smallest edge
Growth	Single tree expanding	Forest merging
Data structures	Priority queue, visited set	Disjoint-set (union-find)
Best density	Dense	Sparse

11. Applications of Graph Algorithms | 图算法的应用

Graph algorithms appear in many real-world systems. For example, GPS navigation uses Dijkstra’s algorithm (or A* for efficiency) to find the fastest route. Internet routing protocols like OSPF rely on shortest path trees. The PageRank algorithm, used by Google, analyses the web graph using concepts of random walks and graph centrality.

图算法出现在许多现实系统中。例如，GPS 导航使用 Dijkstra 算法（或为求效率使用 A* 算法）来寻找最快路线。像 OSPF 这样的互联网路由协议依赖于最短路径树。谷歌使用的 PageRank 算法利用了随机游走和图中心性的概念来分析网页图。

In project management, graph theory helps with PERT charts and critical path analysis to minimise project completion time. Social network platforms use BFS to find shortest connection paths and suggest friends. Understanding these applications helps you contextualise theoretical knowledge for A-Level scenario-based questions.

在项目管理中，图论有助于使用 PERT 图和关键路径分析，以最小化项目完成时间。社交网络平台使用 BFS 来查找最短联系路径并推荐好友。了解这些应用有助于你将理论知识融入情境，应对 A-Level 的情景式问题。

12. Common Exam Pitfalls and Tips | 常见考试陷阱与建议

Students often confuse Dijkstra’s with BFS, forgetting that Dijkstra’s works on weighted graphs while BFS is for unweighted ones. Always check that edge weights are non-negative before applying Dijkstra’s; otherwise, the result may be incorrect.

学生经常混淆 Dijkstra 和 BFS，忘记 Dijkstra 适用于带权图，而 BFS 适用于无权图。在应用 Dijkstra 之前，务必检查边权重是否为非负值；否则，结果可能不正确。

When tracing MST algorithms, many lose marks by not updating the tree correctly or by adding an edge that creates a cycle. Practice manually drawing the growing tree and use a separate list for unvisited vertices to avoid mistakes. For Kruskal’s, always re-sort edges if a question provides unsorted data.

在手动追踪 MST 算法时，许多人因没有正确更新树或添加了形成环的边而失分。练习手动绘制不断增长的树，并使用单独的列表记录未访问顶点，以避免错误。对于 Kruskal 算法，如果题目提供的数据未排序，一定要重新排序边。

Time complexity questions require you to state the dominating factor: adjacency list vs matrix, and whether a heap is used. Memorise the standard complexities: DFS/BFS O(V+E), Dijkstra/Prim with heap O((V+E) log V). Read the question carefully to see if it asks for worst-case or best-case.

时间复杂度问题要求你指出主导因素：邻接表还是邻接矩阵，以及是否使用了堆。熟记标准复杂度：DFS/BFS 为 O(V+E)，Dijkstra/Prim 使用堆时为 O((V+E) log V)。仔细阅读题目，看清要求的是最坏情况还是最佳情况。

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

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

Graph Algorithms | 图算法 考点精讲