breadth python in python

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.py
from collections import deque

def bfs(start, goal, graph):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node == goal:
            return True
        
        visited.add(node)
        neighbors = graph.get(node, [])
        for neighbor in neighbors:
            if neighbor not in visited:
                queue.append(neighbor)
    
    return False
420 chars
19 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