One way to perform a breadth-first search in Python is to use a queue data structure. We can start by initializing a queue with the starting node of the graph or tree. Then, we can iterate through the nodes in the queue, adding the unvisited neighbor nodes to the back of the queue. We can continue this process until we reach the goal node or we have visited all reachable nodes. Here's an example implementation:
main.py420 chars19 lines
In this implementation, start
is the starting node, goal
is the target node to find, and graph
is a dictionary that represents the graph with nodes as keys and lists of neighboring nodes as values. The visited
set keeps track of the nodes we have already visited to avoid cycles. The queue
is initialized with the starting node and will contain the nodes to visit next in a FIFO order. We continue popping nodes from the front of the queue and adding unvisited neighbors to the back of the queue until we reach the goal or we run out of nodes. If we reach the goal, we return True
, otherwise we return False
.
gistlibby LogSnag