breadth first search in python

To perform a breadth-first search in Python, we can make use of a queue and add the starting node to the queue. Then we will loop through the queue while it is not empty and process each node by adding its neighbors to the queue.

Here's an example of implementing Breadth-First Search in Python:

main.py
from collections import deque

# Define the graph as a dictionary of lists
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# Define the starting node
start_node = 'A'

# Initialize the visited set and the queue
visited = set()
queue = deque([start_node])

# Loop through the queue while it is not empty
while queue:
    # Dequeue the next node
    node = queue.popleft()

    # If the node has not been visited, process it and mark it as visited
    if node not in visited:
        print(node)
        visited.add(node)

        # Add the node's neighbors to the queue
        for neighbor in graph[node]:
            queue.append(neighbor)
705 chars
33 lines

In this example, we define a graph as a dictionary of lists where each key represents a node and its value is a list of its neighbors. We also define the starting node as 'A'. We then initialize a visited set and a queue with the starting node.

We loop through the queue while it is not empty and dequeue the next node. If the node has not been visited, we process it by printing it and adding it to the visited set. We also add its neighbors to the queue. The process continues until the queue is empty, and all nodes reachable from the starting node have been visited.

gistlibby LogSnag