Suppose you need to get from one place to another in the fewest steps. First, draw the places and their connections as a graph. Breadth-first search (BFS) checks what you can reach in one step, then two steps, then three. It can tell you whether a path exists and find a route with the fewest connections. section 6.1 section 6.3
Find a mango seller
Imagine looking for a mango seller among your friends. Check your friends first. If none sells mangoes, check their friends, then the next group of connections. The first seller you find this way is the closest in your network: a first-degree connection is checked before a second-degree one. section 6.3 section 6.4
To keep that order:
- Put the starting node’s neighbors in a queue. A queue is first in, first out: the first neighbor added is the first checked. section 6.4 section 6.5
- Take the next node from the queue. If it meets your goal, stop; otherwise, add its neighbors. If the queue empties, no match was found. section 6.7
- Keep track of nodes already checked. Shared neighbors otherwise cause repeat work, and cycles can keep the search going forever. section 6.7
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = set() #1
while search_queue:
person = search_queue.popleft()
if not person in searched: #2
if person_is_seller(person):
print(person + " is a mango seller!")
return True
else:
search_queue += graph[person]
searched.add(person) #3
return False
search("you")
#1 This set is how you keep track of which people you’ve searched before.
#2 Only search this person if you haven’t already searched them.
#3 Marks this person as searched
This Python version uses a deque for the search queue and a set to avoid checking the same person twice. It returns whether a seller exists; it does not print a route. section 6.7
If the search visits the whole graph, it follows its connections and handles its nodes. Its running time is O(V + E), where V is the number of vertices and E is the number of edges. section 6.8
BFS can also visit every node rather than stop at a match. To list files in a directory tree, queue folders to inspect and print the files inside them. A tree without cycles needs no checked-node set for this traversal. section 7.2
