Graph Algorithms Revision Notes | 图算法 考点精讲

📚 Graph Algorithms Revision Notes | 图算法 考点精讲

Graphs are abstract data structures consisting of vertices and edges. They model networks such as social connections, road maps, and the internet. For CIE GCSE Computer Science, you need to understand how graphs are represented and how fundamental traversal and path-finding algorithms work.

图是由顶点和边组成的抽象数据结构，广泛应用于社交网络、道路地图和互联网等建模。在 CIE GCSE 计算机科学中，你需要掌握图的表示方法以及基本的遍历和寻路算法。

1. Graph Fundamentals | 图的基本概念

A graph G = (V, E) consists of a set of vertices V and a set of edges E connecting pairs of vertices. Edges can be directed (one-way) or undirected (two-way). Weighted graphs assign a numerical cost or distance to each edge.

图 G = (V, E) 由顶点集合 V 和连接顶点对的边集合 E 组成。边可以是有向的（单向）或无向的（双向）。加权图会为每条边赋予一个数值代价或距离。

In an undirected graph, the edge (A, B) is identical to (B, A). In a directed graph (digraph), an edge (A, B) means you can travel from A to B but not necessarily back. A path is a sequence of vertices connected by edges; a cycle returns to the start vertex without repeating edges.

在无向图中，边 (A, B) 等同于 (B, A)。在有向图中，边 (A, B) 表示可以从 A 到 B，但不一定能返回。路径是边连接的顶点序列；环路则是在不重复边的情况下回到起点的路径。

A graph is connected if there is a path between every pair of vertices. A tree is a connected graph with no cycles. Understanding these properties is essential for choosing the correct traversal algorithm.

如果图中每对顶点之间都存在路径，则该图是连通的。树是一种无环的连通图。理解这些性质对于选择合适的遍历算法至关重要。

---

2. Adjacency Matrix | 邻接矩阵表示法

An adjacency matrix stores a graph in a 2D array of size V × V. The cell [i][j] is 1 (or the edge weight) if there is an edge from vertex i to vertex j, otherwise 0. For undirected graphs the matrix is symmetric across the diagonal.

邻接矩阵用一个大小为 V × V 的二维数组存储图。若顶点 i 到顶点 j 存在边，则单元格 [i][j] 为 1（或边权），否则为 0。对于无向图，矩阵沿对角线对称。

The adjacency matrix allows fast edge look‑ups in O(1) time. However, it uses O(V²) memory, which is wasteful for sparse graphs. Adding or removing a vertex requires resizing the entire matrix, making it inflexible for dynamic graphs.

邻接矩阵可以在 O(1) 时间内快速查询边。但它的内存消耗为 O(V²)，对于稀疏图来说非常浪费。添加或删除顶点需要调整整个矩阵的大小，因此不适合动态变化的图。

	A	B	C
A	0	1	0
B	1	0	1
C	0	1	0

Example adjacency matrix for an undirected graph A-B-C.

无向图 A-B-C 的邻接矩阵示例

---

3. Adjacency List | 邻接表表示法

An adjacency list uses an array of linked lists or dynamic arrays. Each vertex has a list of its neighbouring vertices (and edge weights if applicable). This representation is memory‑efficient, using only O(V + E) space.

邻接表使用一个链表或动态数组的数组。每个顶点都有一个列表，存放其邻接顶点（及边权，如果适用）。这种表示法内存利用率高，仅占用 O(V + E) 空间。

Adding a vertex or an edge is straightforward: append to the relevant list. Looking up whether an edge exists takes O(degree) time, which is acceptable in sparse graphs. Adjacency lists are thus the most common representation in graph algorithms.

添加顶点或边非常简单：只需追加到相应列表。查询是否存在边需要 O(度) 时间，在稀疏图中可以接受。因此邻接表是图算法中最常用的表示方法。

For example, vertex A connects to B and C: list[A] -> B -> C. If the graph is weighted, each list node stores the neighbour and the weight.

例如，顶点 A 连接 B 和 C：list[A] -> B -> C。如果是加权图，每个链表结点存储邻接顶点和权重。

---

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

DFS explores a graph by going as deep as possible along one branch before backtracking. It can be implemented using a stack, either explicitly or via recursion. The algorithm marks each visited vertex to avoid revisiting.

DFS 通过沿一个分支尽可能深入，到达尽头后再回溯的方式探索图。它可以用栈来实现，可以显式使用栈或通过递归。算法会标记每个已访问的顶点以避免重复访问。

The pseudocode steps: push the start vertex to the stack. While the stack is not empty, pop a vertex, mark it as visited, then push all its unvisited neighbours onto the stack. The order of neighbour pushing affects the exact traversal sequence.

伪代码步骤：将起始顶点压入栈。当栈非空时，弹出一个顶点，标记为已访问，然后将其所有未访问的邻接顶点压入栈。邻接顶点的入栈顺序会影响具体的遍历序列。

DFS is particularly useful for solving mazes, detecting cycles, and performing topological sorting on directed acyclic graphs. It naturally uses less memory than BFS in deep graphs.

DFS 尤其适用于迷宫求解、环检测以及在无环有向图上进行拓扑排序。在深度较大的图中，DFS 自然比 BFS 使用更少的内存。

---

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

BFS explores all neighbours of a vertex before moving to the next level. It uses a queue data structure. The start vertex is enqueued and marked. Then vertices are dequeued one by one; each time all unvisited neighbours are enqueued and marked.

BFS 在进入下一层之前会先探索当前顶点的所有邻居。它使用队列数据结构。起始顶点入队并标记，然后逐个出队顶点，每次将其所有未访问的邻接顶点入队并标记。

Because BFS expands layer by layer, it always finds the shortest path in an unweighted graph in terms of the number of edges. This makes it ideal for navigation applications and social network “degrees of separation” problems.

由于 BFS 逐层扩展，在无权图中它总是能找到最短路径（按边数计）。这使其成为导航应用和社交网络“分离度”问题的理想选择。

Memory consumption can be high if the graph is very wide, as the queue stores many vertices. BFS also requires a boolean visited array to ensure each vertex is processed once.

如果图非常宽，队列会存储大量顶点，内存消耗可能较高。BFS 同样需要一个布尔型 visited 数组来确保每个顶点只处理一次。

---

6. DFS vs BFS: Comparison | DFS 与 BFS 对比

The key difference lies in the order of exploration. DFS uses a stack (LIFO), diving deep; BFS uses a queue (FIFO), spreading wide. This leads to different time and space complexities and different application domains.

关键区别在于探索顺序。DFS 使用栈（后进先出），深入探索；BFS 使用队列（先进先出），逐层扩展。这导致了不同的时空复杂度和应用场景。

Criterion	DFS	BFS
Data structure	Stack (or recursion)	Queue
Path found	Not necessarily shortest	Shortest in unweighted graph
Memory	O(depth) with recursion	O(width) – can be large
Suitable for	Mazes, puzzles, topological sort	Finding shortest hops, web crawling

Comparison of DFS and BFS

DFS 与 BFS 对比

Both algorithms have a time complexity of O(V + E) when using an adjacency list. The choice between them depends on the problem: need the shortest hops? Use BFS. Need to explore all configurations? Use DFS.

两种算法在使用邻接表时的时间复杂度均为 O(V + E)。选择哪种算法取决于具体问题：需要最少跳数？用 BFS。需要探索所有配置？用 DFS。

---

7. Dijkstra’s Shortest Path Algorithm | Dijkstra 最短路径算法

Dijkstra’s algorithm finds the shortest path from a single source to all other vertices in a weighted graph with non‑negative edge weights. It maintains a priority queue of unvisited vertices ordered by their current shortest distance estimate.

Dijkstra 算法可以在边权非负的加权图中找到从单一源点出发到所有其他顶点的最短路径。它维护一个按当前最短距离估计排序的未访问顶点优先队列。

The algorithm initialises the source distance to 0 and all others to infinity. At each step, the unvisited vertex with the smallest distance is marked as visited; its neighbours’ distances are updated if a shorter path is found (relaxation).

算法将源点距离初始化为 0，其余顶点为无穷大。每一步选择距离最小的未访问顶点标记为已访问；如果发现更短路径（松弛操作），则更新其邻接顶点的距离。

The process repeats until all vertices have been visited or the smallest distance among unvisited vertices is infinity (disconnected graph). Dijkstra’s algorithm is used in GPS routing and network protocols like OSPF.

重复此过程直到所有顶点都已访问，或者未访问顶点中的最小距离为无穷大（不连通图）。Dijkstra 算法广泛应用于 GPS 路径规划和 OSPF 等网络协议。

The time complexity with a binary heap priority queue is O((V + E) log V). It is essential to remember that Dijkstra fails if there are negative edge weights.

使用二叉堆优先队列时的时间复杂度为 O((V + E) log V)。必须牢记，如果存在负权边，Dijkstra 算法会失效。

---

8. Exam Tips and Common Pitfalls | 考试技巧与常见误区

When tracing DFS or BFS, always clearly show the data structure (stack or queue) content after each step. Label vertices as visited explicitly. Choose a consistent neighbour order, e.g. alphabetical, to avoid ambiguity.

在追踪 DFS 或 BFS 时，务必在每个步骤后清晰标出数据结构（栈或队列）的内容。明确标记已访问的顶点。选择统一的邻居顺序，例如按字母序，以避免歧义。

For Dijkstra, make a table with columns: Vertex, Shortest distance from start, Previous vertex, and Visited? Update the table iteratively and use it to reconstruct the final path.

对于 Dijkstra 算法，制作一个表格，列名包括：顶点、距起点的最短距离、前驱顶点、是否已访问。迭代更新该表格，并用它重建最终路径。

Be careful not to confuse undirected and directed edges when building adjacency matrices or lists. A common mistake is forgetting to add the reverse edge in an undirected graph or adding it in a directed graph.

在构建邻接矩阵或邻接表时，注意不要混淆无向边与有向边。常见错误包括：在无向图中忘记添加反向边，或在有向图中错误地添加了反向边。

Practise converting between graph representations and tracing algorithms on small graphs of 4–6 vertices. Questions often ask for the traversal order or the final distance values, so systematic working is key.

练习在 4 至 6 个顶点的小图上转换图表示并追踪算法过程。考题常要求写出遍历顺序或最终距离值，因此分步骤的系统性解答至关重要。

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

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