You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
This lesson covers breadth-first search (BFS) and depth-first search (DFS) — the two fundamental algorithms for traversing (visiting) all vertices in a graph. Both are required by the OCR A-Level Computer Science (H446) specification.
Graph traversal is the process of visiting every vertex in a graph exactly once, starting from a given source vertex. The two main strategies differ in the order in which vertices are visited.
| Algorithm | Strategy | Data Structure | Explores |
|---|---|---|---|
| BFS | Visit all neighbours before going deeper | Queue | Level by level |
| DFS | Go as deep as possible before backtracking | Stack (or recursion) | Branch by branch |
BFS explores a graph level by level — it visits all vertices at distance 1 from the start, then distance 2, then distance 3, and so on.
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.