One advantage of a breadth-first search over a depth-first search is that we can extract the shortest distance between two nodes.
One way of doing this (at the cost of a little extra space) is to use a queue whose elements consist not simply of nodes but of pairs (d, n) where n is a node and d is an integer recording the distance from the start node.
where we have assumed that we are given a function is_end_node that tells us if a particular node is the one we are searching for.
Consider the following problem (from Hackerrank):
start with a connected and coloured graph
given a single colour
find the shortest path between nodes of that colour
The idea is to find the first node n1 of the correct colour c and find the shortest path starting at that node to another node n2 of colour c.
Then – marking the nodes n1 and n2 as visited – find the nearest n3 of colour c to n2 that is not marked as visited.
Repeating we will take into account every node of colour c because the graph is connected.
Then we can record the shortest of the lengths of the paths we calculated.
The full solution might look like: