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:

1. keep a queue containing the contacts to check
2. pop a person off the queue
3. have we checked this person before?
4. yes, go back to step 2
5. check if this person’s trade is what we are looking for
6. if yes, we are done, return the contractor
7. add the person’s contacts to the queue to search
8. add the person to our checked list
9. if the queue is empty, return none
10. 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