How do we traverse a graph or tree, and how do Dijkstra's algorithm and A* find a shortest path?
Graph and tree traversal: breadth-first and depth-first traversal of a graph, the pre-order, in-order and post-order traversal of a binary tree, and the shortest-path algorithms Dijkstra's algorithm and A* search.
An OCR H446 answer on traversal and shortest-path algorithms: breadth-first and depth-first graph traversal, the pre-order, in-order and post-order traversal of a binary tree, and how Dijkstra's algorithm and A* search find a shortest path.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this dot point is asking
OCR wants breadth-first and depth-first graph traversal (and the data structure each uses), the three binary-tree traversals (pre-order, in-order, post-order), and the shortest-path algorithms Dijkstra and A* (and how A* differs). Expect a "BFS versus DFS" question and a "how does Dijkstra work, how does A* differ" question.
The answer
Breadth-first and depth-first graph traversal
Binary tree traversals
Dijkstra's algorithm and A*
Examples in context
Sat-navs use A* because its heuristic (straight-line distance to the destination) prunes the search dramatically compared with Dijkstra. Network routing and "fewest hops" use BFS. DFS underlies dependency resolution and cycle detection in build systems. In-order traversal of a BST is how you list its keys in order. OCR links this to data structures (queues, stacks, trees, graphs), to the heuristics computational method, and to Big-O analysis of these algorithms.
Try this
Q1. State the data structure used by a breadth-first traversal and by a depth-first traversal. [2 marks]
- Cue. Breadth-first uses a queue; depth-first uses a stack (or recursion).
Q2. State which binary tree traversal outputs a binary search tree's values in ascending order. [1 mark]
- Cue. In-order traversal (left, node, right).
Q3. Explain how A* differs from Dijkstra's algorithm. [2 marks]
- Cue. A* adds a heuristic estimate of the remaining distance to the goal and expands the node minimising distance-so-far plus estimate, steering the search towards the goal and exploring fewer nodes.
Exam-style practice questions
Practice questions written in the style of OCR exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
OCR 20196 marksExplain the difference between a breadth-first and a depth-first traversal of a graph, stating the data structure each uses, and give one use of each.Show worked answer →
Breadth-first (up to 3): a breadth-first traversal visits all the neighbours of the start node first, then their neighbours, exploring level by level. It uses a queue to hold nodes waiting to be visited. Use: finding the shortest path (fewest edges) in an unweighted graph, or finding all nodes within a certain distance.
Depth-first (up to 3): a depth-first traversal goes as deep as possible along one path before backtracking to explore the next, visiting a node then one of its unvisited neighbours repeatedly. It uses a stack (or recursion). Use: detecting cycles, finding connected components, topological sorting, or solving mazes. Markers reward level-by-level with a queue for BFS, as-deep-as-possible with a stack for DFS, and a valid use of each.
OCR 20216 marksExplain how Dijkstra's algorithm finds the shortest path in a weighted graph, and explain how A* differs from Dijkstra's algorithm.Show worked answer →
Dijkstra (up to 4): Dijkstra's algorithm finds the shortest path from a start node to all others in a weighted graph with non-negative weights. It keeps a tentative shortest distance to each node (start = 0, others = infinity), repeatedly selects the unvisited node with the smallest tentative distance, marks it visited, and updates (relaxes) the tentative distances of its neighbours if a shorter path through it is found. When the destination is visited, its distance is the shortest.
A* difference (up to 2): A* adds a heuristic estimate of the remaining distance from each node to the goal, and selects the node minimising (distance so far + estimated distance to goal) rather than just distance so far. This guides the search towards the goal, so A* usually explores fewer nodes and is faster than Dijkstra when a good heuristic is available. Markers reward tentative distances and relaxation for Dijkstra, and the added heuristic to the goal for A*.
Related dot points
- Searching algorithms: linear search, binary search and binary tree search, how each works with a trace, the precondition for binary search, and their time complexity in Big-O notation.
An OCR H446 answer on searching algorithms: how linear search, binary search and binary tree search work with worked traces, the requirement that binary search needs a sorted list, and the time complexity of each in Big-O notation.
- Sorting algorithms: bubble sort, insertion sort, merge sort and quick sort, how each works with a trace, and their time complexity in Big-O notation including best, average and worst cases.
An OCR H446 answer on sorting algorithms: how bubble sort, insertion sort, merge sort and quick sort order a list with worked traces, and their time complexity in Big-O notation including the difference between the quadratic and the divide-and-conquer sorts.
- Big-O notation for time and space complexity: the constant, logarithmic, linear, linearithmic, polynomial and exponential complexity classes, how to determine the Big-O of an algorithm, and using it to compare and judge the suitability of algorithms.
An OCR H446 answer on Big-O notation: the constant, logarithmic, linear, linearithmic, polynomial and exponential complexity classes for time and space, how to determine an algorithm's Big-O, and using it to compare algorithms and judge their suitability.
- Data structures: arrays, records, tuples and lists, the stack and queue abstract data types and their operations, linked lists, trees and graphs, and hash tables, including how each is used and its advantages.
An OCR H446 answer on data structures: arrays, records, tuples and lists, the stack and queue abstract data types with their operations, linked lists, trees, graphs and hash tables, including how each is used and its advantages and disadvantages.
- Thinking logically: identifying the decision points and conditions that affect the flow of a solution; computational methods including problem recognition, divide and conquer, backtracking, heuristics, performance modelling and visualisation.
An OCR H446 answer on thinking logically and computational methods: identifying decision points and conditions in a solution, and the methods of problem recognition, divide and conquer, backtracking, heuristics, performance modelling and visualisation that make problems solvable.