📚 GCSE OCR Computer Science: Graph Algorithms Key Points | GCSE OCR 计算机：图算法 考点精讲
Graph algorithms are fundamental tools used to solve problems involving networks of connected data. In GCSE OCR Computer Science, understanding how to represent graphs and apply standard traversal and pathfinding algorithms is essential for both written exams and practical coding challenges. This article will guide you through the key concepts, step-by-step examples, and common exam tips to help you master graph algorithms with confidence.
图算法是解决由连接数据构成的网络问题的基本工具。在 GCSE OCR 计算机科学中，理解如何表示图以及应用标准的遍历和寻路算法，对笔试和编程实践都至关重要。本文将通过核心概念、逐步示例和常见考试技巧，帮助你自信地掌握图算法。
1. What is a Graph? | 什么是图？
A graph is a data structure consisting of a set of nodes (also called vertices) and a set of edges that connect pairs of nodes. Graphs can model many real-world systems such as social networks, transport maps, and the structure of the internet.
图是一种数据结构，由一组节点（或称顶点）以及连接这些节点的边组成。图可以模拟许多现实系统，如社交网络、交通地图和互联网的结构。
2. Graph Terminology | 图的相关术语
Key terms include: vertex (node), edge (connection), adjacent vertices (neighbors), path (sequence of edges), weighted graph (edges have values), directed graph (edges have direction), undirected graph (edges are two-way), and cycle (a path that returns to the start).
关键术语包括：顶点（节点）、边（连接）、相邻顶点（邻居）、路径（边的序列）、带权图（边有权重）、有向图（边有方向）、无向图（边为双向）以及环（回到起点的路径）。
3. Representing Graphs: Adjacency Matrix | 图的表示：邻接矩阵
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 matrix entry [i][j] is 1 (or the weight of the edge in a weighted graph); otherwise it is 0. For undirected graphs the matrix is symmetric.
邻接矩阵是一个大小为 V × V 的二维数组（V 为顶点数）。如果顶点 i 到顶点 j 有边，则矩阵元素 [i][j] 为 1（带权图则为边的权重）；否则为 0。对于无向图，该矩阵是对称的。
4. Representing Graphs: Adjacency List | 图的表示：邻接表
An adjacency list stores a list of neighbors for each vertex. It is more memory-efficient for sparse graphs. For example, vertex A might be stored as A: [B, C] to indicate edges to B and C.
邻接表为每个顶点存储一个邻居列表。对于稀疏图而言，它更节省内存。例如，顶点 A 可存为 A: [B, C] 来表示连向 B 和 C 的边。
5. Depth-First Search (DFS) | 深度优先搜索 (DFS)
DFS explores as far as possible along each branch before backtracking. It can be implemented using a stack (often via recursion). Starting from a root node, it visits one neighbor, then its neighbor, and so on, until a dead end is reached; then it backtracks to explore other branches.
DFS 沿着每条分支尽可能深入，直到无路可走再回溯。它可以用栈实现（通常通过递归）。从根节点开始，访问一个邻居，然后访问该邻居的邻居，依此类推，直至尽头；然后回溯探索其他分支。
6. Breadth-First Search (BFS) | 广度优先搜索 (BFS)
BFS explores all neighbors at the present depth level before moving on to nodes at the next depth level. It uses a queue to keep track of the order. BFS guarantees finding the shortest path in an unweighted graph.
BFS 先访问当前深度的所有邻居，然后再进入下一深度的节点。它使用队列来记录访问顺序。在无权图中，BFS 能保证找到最短路径。
7. Comparing DFS and BFS | 比较DFS和BFS
DFS uses less memory on wide graphs and is useful for topological sorting and solving puzzles. BFS is better for finding the shortest path in unweighted graphs and works level by level. In GCSE exams you may be asked to trace both algorithms on a simple graph.
DFS 在宽图上占用更少内存，适用于拓扑排序和解谜。BFS 更适合无权图最短路径，并逐层工作。GCSE 考试可能要求你在简单图上跟踪这两种算法。
8. Shortest Path Problem and Dijkstra’s Algorithm | 最短路径问题与Dijkstra算法
When edges have weights, the shortest path is the one with the smallest total weight. Dijkstra’s algorithm solves this by repeatedly selecting the unvisited vertex with the smallest tentative distance, updating distances to its neighbors, and marking it visited.
当边有权重时，最短路径是总权重最小的路径。Dijkstra 算法通过反复选择未访问顶点中暂定距离最小的顶点，更新其邻居的距离，然后将其标记为已访问，来解决这个问题。
9. Dijkstra’s Algorithm Worked Example | Dijkstra算法示例
Consider a graph with vertices A, B, C, D, E. A is the start. Weights: A-B 6, A-C 3, B-C 2, B-D 5, C-D 3, C-E 4, D-E 2. The algorithm maintains a distance table (initial distances set to infinity, except start at 0) and a predecessor column.
考虑一个图，顶点为 A、B、C、D、E，起点为 A。权重：A-B 6，A-C 3，B-C 2，B-D 5，C-D 3，C-E 4，D-E 2。算法维护一个距离表（除起点距离为 0 外，初始距离设为无穷大）和前驱列。
| Step | Visited | Dist A | Dist B | Dist C | Dist D | Dist E | Predecessor |
|---|---|---|---|---|---|---|---|
| 0 | – | 0 | ∞ | ∞ | ∞ | ∞ | – |
| 1 | A | 0 | 6 A | 3 A | ∞ | ∞ | A→C, A→B |
| 2 | C | 0 | 5 C | 3 A | 6 C | 7 C | C→B (5), C→D (6), C→E (7) |
| 3 | B | 0 | 5 C | 3 A | 6 C | 7 C | B→D (5+5=10) > 6, no update |
| 4 | D | 0 | 5 C | 3 A | 6 C | 7 C (8 via D >7) | D→E 6+2=8, keep 7 |
| 5 | E | 0 | 5 C | 3 A | 6 C | 7 C | Complete |
The final shortest distances: A→B = 5 (via C), A→C = 3, A→D = 6 (via C), A→E = 7 (via C). This table format is often required in GCSE OCR exam questions.
最终最短距离：A→B = 5（经 C），A→C = 3，A→D = 6（经 C），A→E = 7（经 C）。这种表格格式常出现在 GCSE OCR 考试题目中。
10. Applications of Graph Algorithms | 图算法的应用
Graph algorithms power many technologies: GPS navigation uses Dijkstra’s algorithm to find the fastest route; social networks use BFS to suggest friends of friends; internet routers use shortest-path algorithms to route data; and DFS helps in cycle detection and maze solving.
图算法驱动着众多技术：GPS 导航利用 Dijkstra 算法寻找最快路线；社交网络利用 BFS 推荐好友的好友；互联网路由器使用最短路径算法路由数据；DFS 则有助于环检测和迷宫求解。
11. Exam Tips for Graph Algorithms | 图算法考试技巧
When tackling OCR GCSE graph algorithm questions, always draw the graph clearly and label weights. For DFS and BFS, use a stack or queue record to show the order of visits. For Dijkstra, set up a neat distance table, work systematically, and double-check updates. Even if you make a minor arithmetic error, showing correct steps earns method marks.
在解答 OCR GCSE 图算法题目时，务必清楚绘制图形并标注权重。对于 DFS 和 BFS，使用栈或队列记录访问顺序。对于 Dijkstra，建立一个整洁的距离表，按步骤操作并仔细检查更新。即使有小的计算错误，展示正确步骤依然可以获得方法分。
12. Summary | 总结
Graphs are versatile data structures, and their algorithms—DFS, BFS, and Dijkstra—form the backbone of network analysis. Mastering their representation (matrix and list) and tracing them on paper will prepare you thoroughly for the GCSE OCR Computer Science examination. Practice with past papers and always verify your answers step by step.
图是多用途的数据结构，其算法——DFS、BFS 和 Dijkstra——构成了网络分析的支柱。掌握它们的表示法（矩阵和列表）并在纸上跟踪算法过程，将为你的 GCSE OCR 计算机科学考试做好充足准备。多练习历年真题，并逐步核对你的答案。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导