Topic study hub
Graph-traversal
Official AQA 7517 section 4.3.1.
0
Objectives
5
Flashcards
7
Questions
36 min
Study time
AqaA LevelComputer ScienceFundamentals of algorithms
Choose a revision tool
Start revising Graph-traversal
Syllabus checklist
What you need to know
0 objective pages available
Simple graph-traversal algorithms1 objectives
- Simple graph-traversal algorithms: Be able to trace breadth-first and depth-first search algorithms and describe typical applications of both. Breadth-first: shortest path for an unweighted graph. Depth-first: Navigating a maze.
Key terms
Breadth-first searchDepth-first search
Exam tips
- Show the trace in order: Write down each vertex when it is first visited and follow the neighbour order given in the question.
Common mistakes
- Confusing the two traversal patterns: Remember that breadth-first search explores level by level and is used for shortest paths in unweighted graphs. Depth-first search explores one branch deeply and is used for navigating a maze.
Practice preview
- A breadth-first search starts at A. The neighbours of each vertex are considered in the order shown: A: B, C; B: D; C: E; D: none; E: none. In what order are the vertices visited?
- In an unweighted graph, breadth-first search finds a path from S to G using three edges. What does this indicate?
- A depth-first search starts at A and considers neighbours in the order shown. A: B, C; B: D; C: E; D: F; E: F; F: none. Which is the order in which vertices are first visited?
Continue by objective
Objectives are grouped by subtopic so students can jump straight to the exact skill they want to revise.
Related topics