📚 IGCSE OCR Computer Science: Graph Algorithms – Key Points Explained | IGCSE OCR 计算机：图算法考点精讲
Graphs help us model connections and relationships, from social networks to transport maps. In IGCSE OCR Computer Science, graph algorithms appear regularly, testing your ability to represent networks, traverse them efficiently, and find the shortest path. This article breaks down every essential concept you need to know, with clear examples and exam-style explanations.
图能帮助我们模拟连接和关系，从社交网络到交通路线图。在 IGCSE OCR 计算机科学中，图算法经常出现，考查你表示网络、高效遍历以及寻找最短路径的能力。本文将逐一拆解你需要掌握的每一个核心概念，并配合清晰的示例和贴近考试的讲解。
1. What is a Graph? | 什么是图？
A graph is a data structure consisting of nodes (vertices) and connections between them (edges). Unlike a tree, a graph can have cycles, multiple paths between nodes, and does not necessarily have a single root.
图是一种由节点（顶点）和它们之间的连接（边）组成的数据结构。与树不同，图可以包含环、节点间存在多条路径，并不一定有一个单一的根节点。
Graphs are used to represent real-world networks: computer networks, roads, flights, web pages linked by hyperlinks, and even the spread of diseases. Understanding the basic structure is step one.
图用于表示现实世界中的网络：计算机网络、道路、航班、通过超链接相连的网页，甚至疾病的传播。理解基本结构是第一步。
2. Vertices and Edges | 顶点与边
A vertex (plural: vertices) represents an entity, such as a city in a map or a person in a social network. An edge is a connection between two vertices, showing a direct relationship.
顶点（单数 vertex，复数 vertices）代表一个实体，例如地图中的城市或社交网络中的人。边是连接两个顶点的连线，表示直接的关系。
In IGCSE problems, vertices are often labelled with letters or numbers, and edges might represent distances, durations, or simply the existence of a route. A graph with V vertices and E edges is often described as having size (V, E).
在 IGCSE 的题目中，顶点通常用字母或数字标记，边可以代表距离、耗时或仅表示存在一条路径。一个具有 V 个顶点和 E 条边的图通常描述为规模 (V, E)。
3. Directed and Undirected Graphs | 有向图与无向图
An undirected graph has edges with no direction: you can travel both ways equally. A friendship on a social media network where both follow each other is undirected.
无向图的边没有方向：你可以双向同等通行。社交媒体上互相加为好友的关系就是无向的。
A directed graph (digraph) has edges with an arrow indicating a one-way relationship. Think of a one-way street or a follow on Twitter where A follows B but B may not follow A back.
有向图（有向图）的边带有箭头，表示单向关系。想想单行道，或是 Twitter 上的关注：A 关注了 B，但 B 不一定回关 A。
In the exam, always check the diagram carefully: a line without an arrowhead is undirected; an edge with a single arrow is directed. This affects traversal and pathfinding logic.
考试时，务必仔细检查图示：没有箭头的线是无向的，带一个箭头的边是有向的。这会直接影响遍历和寻路逻辑。
4. Weighted Graphs | 加权图
When edges carry a number – a weight – we call it a weighted graph. The weight might represent distance, cost, time, or bandwidth. Unweighted graphs implicitly have weight 1 on every edge.
当边带有一个数值——即权值——我们称之为加权图。权值可以代表距离、成本、时间或带宽。无权图的每条边默认权值为 1。
Weighted graphs are crucial for shortest path problems. The exam may ask you to find the path with the smallest total weight from a start vertex to a target, using Dijkstra’s algorithm.
加权图对于最短路径问题至关重要。考试可能会要求你使用 Dijkstra 算法，找到从起点到目标顶点总权值最小的路径。
A typical graph might look like: A – 4 – B, B – 2 – C, A – 5 – C. Here the numbers on the arcs are weights.
一个典型的图可能形如：A – 4 – B，B – 2 – C，A – 5 – C。其中弧上的数字就是权值。
5. Representing Graphs: Adjacency Matrix | 图的表示：邻接矩阵
An adjacency matrix is a 2D array of size V × V, where the entry at row i, column j is 1 (or the weight) if there is an edge from vertex i to vertex j, and 0 otherwise. For undirected graphs, the matrix is symmetric.
邻接矩阵是一个 V × V 的二维数组，其中第 i 行第 j 列的值为 1（或权值）如果存在从顶点 i 到顶点 j 的边，否则为 0。无向图的邻接矩阵是对称的。
Example: vertices labelled 0,1,2. Edge 0–1 weight 5, edge 1–2 weight 3. The matrix:
| 0 | 5 | 0 |
| 5 | 0 | 3 |
| 0 | 3 | 0 |
示例：顶点标号 0,1,2。边 0–1 权值为 5，边 1–2 权值为 3。矩阵如上。
Advantages: quick to check if an edge exists – O(1). Disadvantages: uses O(V²) memory, wasteful for sparse graphs with few edges.
优点：检查边是否存在很快——O(1)。缺点：使用 O(V²) 内存，对于边很少的稀疏图很浪费。
6. Representing Graphs: Adjacency List | 图的表示：邻接列表
An adjacency list stores each vertex with a list of its neighbours (and weights if needed). This is more memory-efficient for sparse graphs.
邻接列表为每个顶点存储一个邻接顶点列表（以及权值，如果需要）。对稀疏图更节省内存。
Example: A → (B,5), (C,2); B → (A,5), (C,3); C → (A,2), (B,3). This is often implemented using an array of linked lists or a dictionary of lists in Python.
示例：A → (B,5), (C,2)；B → (A,5), (C,3)；C → (A,2), (B,3)。通常使用链表数组或 Python 中的字典列表来实现。
Exam questions often ask you to draw or interpret both representations for a given graph. You must be able to switch between diagram, matrix, and list forms.
考题经常要求你为给定的图画出来或解读两种表示方法。你必须能够在图示、矩阵和列表形式之间来回转换。
7. Graph Traversal: Depth-First Search (DFS) | 图遍历：深度优先搜索（DFS）
DFS explores a graph by going as deep as possible along one branch before backtracking. It uses a stack (often via recursion) to remember where to return.
DFS 通过沿着一条分支尽可能深入，在回溯之前探索图。它使用栈（通常通过递归）来记住返回的位置。
Algorithm steps: Push start vertex onto stack. While stack not empty: pop a vertex, mark as visited, then push all unvisited neighbours. This gives a depth-first ordering.
算法步骤：将起始顶点压入栈。当栈不为空：弹出一个顶点，标记为已访问，然后将所有未访问的邻居压入栈。这会产生深度优先的顺序。
Using recursion, DFS is simple: visit(node): mark node visited; for each neighbour unvisited, visit(neighbour). The order depends on the neighbour selection order, but the depth-first property always holds.
使用递归实现 DFS 很简单：visit(节点)：标记节点已访问；对每个未访问的邻居，调用 visit(邻居)。顺序取决于邻居的选择顺序，但深度优先的性质始终成立。
8. Graph Traversal: Breadth-First Search (BFS) | 图遍历：广度优先搜索（BFS）
BFS explores a graph level by level, visiting all neighbours of a vertex before moving deeper. It uses a queue to keep track of the frontier.
BFS 按层级探索图，先访问顶点的所有邻居，然后再深入。它使用队列来跟踪前沿。
Algorithm steps: Enqueue start vertex, mark visited. While queue not empty: dequeue a vertex, then for each unvisited neighbour, mark visited and enqueue. This produces a shortest path in terms of number of edges in an unweighted graph.
算法步骤：将起始顶点入队，标记已访问。当队列不为空：出队一个顶点，然后对每个未访问的邻居，标记已访问并入队。在无权图中，这会产生按边数计算的最短路径。
BFS order example starting at A: A, then B and C (if both neighbours), then their neighbours, etc. It is widely used in web crawlers and social network friend suggestions.
以 A 为起点的 BFS 顺序示例：A，然后 B 和 C（如果都是邻居），然后是它们的邻居，依此类推。它广泛用于网络爬虫和社交网络的好友推荐。
9. Comparing DFS and BFS | DFS 与 BFS 的比较
Both DFS and BFS visit all vertices of a connected graph. The key difference lies in the order and the data structure used: DFS uses stack (LIFO), BFS uses queue (FIFO).
DFS 和 BFS 都能访问连通图的所有顶点。关键区别在于访问顺序和所使用的数据结构：DFS 用栈（后进先出），BFS 用队列（先进先出）。
DFS is memory-efficient for deep graphs, can get stuck in infinite loops if cycles not handled, and does not guarantee shortest path. BFS guarantees shortest path in unweighted graphs but uses more memory for the wide frontier.
DFS 对于深层图内存效率高，如果不处理环可能会陷入无限循环，并且不保证最短路径。BFS 保证无权图中的最短路径，但会为较宽的前沿使用更多内存。
In exam tracing questions, you may be asked to give the order of traversal for a specific graph. Always specify the starting vertex and the rule for choosing neighbours (e.g., alphabetical order) if needed.
在考试中的追踪题中，你可能需要给出特定图的遍历顺序。如果需要，一定要指明起始顶点以及选择邻居的规则（例如字母顺序）。
10. Shortest Path: Dijkstra’s Algorithm | 最短路径：Dijkstra 算法
Dijkstra’s algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative weights. It is a classic greedy algorithm.
Dijkstra 算法可以在具有非负权值的加权图中，找到从单一源顶点到所有其他顶点的最短路径。这是一种经典的贪心算法。
Steps: Assign tentative distance 0 to source, ∞ to others. Mark all unvisited. Pick unvisited vertex with smallest tentative distance; update distances to its neighbours if a shorter path is found. Mark visited. Repeat until target is visited or all vertices processed.
步骤：将源点的暂定距离设为 0，其他顶点设为 ∞。全部标记为未访问。选择未访问中暂定距离最小的顶点；若通过它找到更短路径，则更新邻居的距离。标记为已访问。重复直到目标顶点被访问或所有顶点处理完毕。
Example: start A, distances: A=0, B=5, C=3, D=∞. Pick C (3), update D via C: if C to D weight 2, new distance to D = 5. Continue. The algorithm builds a shortest-path tree.
示例：起点 A，距离：A=0，B=5，C=3，D=∞。选择 C（距离 3），通过 C 更新 D：若 C 到 D 权值为 2，则 D 的新距离 = 5。继续。算法会构建一棵最短路径树。
In IGCSE exams, you may need to complete a table of distances and predecessors step by step for a small graph. Keep a neat working.
在 IGCSE 考试中，你可能需要逐步完成一个小型图的距离与前驱顶点表格。工作草稿要保持整洁。
11. Applications of Graph Algorithms | 图算法的应用
Graph algorithms power many real technologies: GPS navigation uses Dijkstra/A* for route planning; social networks use BFS to find degrees of separation; search engines use graph traversal for indexing.
图算法驱动着许多实际技术：GPS 导航使用 Dijkstra/A* 进行路径规划；社交网络使用 BFS 来计算分离度；搜索引擎使用图遍历来建立索引。
Other applications include network routing protocols (link-state algorithms), circuit board design, and even game AI for pathfinding. Understanding the concept helps you think computationally.
其他应用包括网络路由协议（链路状态算法）、电路板设计，甚至游戏 AI 中的寻路。理解这些概念有助于你进行计算思维。
Exam questions often present a scenario and ask you to explain which algorithm is suitable and why. Be ready to justify your choice based on graph type and requirements.
考题经常给出一个场景，要求你解释哪个算法合适以及为什么。准备好根据图的类型和要求来证明你的选择。
12. Exam Tips for Graph Questions | 图算法考题应试技巧
First, always identify the graph type from the question: directed/undirected, weighted/unweighted. This determines which algorithms are applicable.
首先，一定要从题目中识别图的类型：有向/无向、加权/无权。这决定了哪些算法可以使用。
When tracing DFS/BFS, show your data structure (stack or queue) at each step if asked. Clearly indicate the visit order and the content of the structure after each operation.
在追踪 DFS/BFS 时，如果被要求，要展示每一步的数据结构（栈或队列）。清晰地标明访问顺序以及每次操作后结构的内容。
For Dijkstra, create a neat table with columns: Vertex, Shortest Distance, Previous Vertex, Visited? Update it row by row. Even if the final answer is a single path, the working table earns method marks.
对于 Dijkstra 算法，创建一张整洁的表格，列名包括：顶点、最短距离、前驱顶点、是否已访问。逐行更新。即便最终答案只是一条路径，步骤分也会因为工作表格而拿到。
Finally, always double-check the question’s small print – such as alphabetical neighbour order, or whether the start vertex has distance 0. Little details can change the traversal result.
最后，一定要仔细检查题目中的小字说明——比如按字母顺序选择邻居，或者起始顶点距离是否为 0。小细节可能会改变遍历结果。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导