The Breadth-First Search answers two questions:
- is there a path from node a to node b?
- what is the shortest path from node a to node b?
It is a graph algorithm. Graphs are made up of nodes and edges:
Nodes are connected to other nodes called their neighbors.
A directed graph is a node which has arrows pointed toward them, but no arrows to another node, the relationship is one way.
An undirected graph has no arrows and both nodes are each other’s neighbour.
Both of these graphs are equal.
The breadth-search algorithm requires us to search our neighbours first, if our neighbour is not a match then add their neighbours to our search. We continue in this way until we either find our match, or we exhaust all nodes in our graph. We effectively search across (breadth) before descending (depth), one level at a time. To accomplish this, we use a deque, which is a first in first out (FIFO) data structure.
In the following solution, we will ask a recruiter to search for a contractor among his network.
To implement the graph we need to:
- keep a queue containing the contacts to check
- pop a person off the queue
- have we checked this person before?
- yes, go back to step 2
- check if this person’s trade is what we are looking for
- if yes, we are done, return the contractor
- add the person’s contacts to the queue to search
- add the person to our checked list
- if the queue is empty, return none
- repeat from step 2 until we return a contractor or none
Steps #3, #4, and #8 are very important, because it avoids a potential circular loop.
from dataclasses import dataclass, field from collections import deque @dataclass(frozen=True, order=False) class Contact: id: str name: str trade: str contacts: list = field(default_factory=list, repr=False) # create our recruiter recruiter = Contact(id='012', name='david', trade='recruiter') # create our contractors bob = Contact(id='001', name='bob', trade='bricklayer') matt = Contact(id='002', name='matt', trade='plumber') clint = Contact(id='003', name='clint', trade='sign writer') chris = Contact(id='004', name='chris', trade='electrician') daniel = Contact(id='005', name='daniel',trade='metal worker') jason = Contact(id='006', name='jason', trade='programmer') jon = Contact(id='007', name='jon', trade='editor') fred = Contact(id='008', name='fred', trade='auto electrician') bjorn = Contact(id='009', name='bjorn', trade='cleaner') nick = Contact(id='010', name='nick', trade='spray painter') eric = Contact(id='011', name='eric', trade='comedian') # establish contacts bob.contacts.extend([matt, clint]) matt.contacts.extend([bob]) clint.contacts.extend([matt, chris, bjorn, recruiter]) chris.contacts.extend([matt, clint, recruiter]) daniel.contacts.extend([jason, nick, recruiter]) jon.contacts.extend([eric]) jason.contacts.extend([recruiter]) bjorn.contacts.extend([clint, jon]) nick.contacts.extend([jason, daniel, recruiter]) eric.contacts.extend([recruiter, jon]) recruiter.contacts.extend([matt, chris, clint, daniel, jon]) # the actual breadth-first search algorithm def search(contact, trade): search_queue = deque() search_queue.extend(contact.contacts) searched =  while search_queue: person = search_queue.popleft() if person.id in searched: continue if person.trade == trade: return person search_queue.extend(person.contacts) searched.append(person.id) # ask our recruiter to find a contractor from his contacts def find_contractor(trade): person = search(recruiter, trade) print(person or ('No contractor found for: ' + trade)) find_contractor('comedian') find_contractor('spray painter') find_contractor('plumber') find_contractor('roofer') # outputs: Contact(id='011', name='eric', trade='comedian') Contact(id='010', name='nick', trade='spray painter') Contact(id='002', name='matt', trade='plumber') No contractor found for: roofer