Breadth First Search

Breadth First Search (BFS) is a graph traversal algorithm that visits all the nodes of a graph in breadth-first order, i.e., it visits all the nodes at the current depth before moving on to the nodes at the next depth. The algorithm starts at a root node and explores all the neighboring nodes at the same level before moving to the next level.

BFS uses a queue to keep track of the nodes to be visited. At the start, the root node is added to the queue. Then, while the queue is not empty, the algorithm dequeues the next node in the queue, visits its unvisited neighbors, and enqueues them.

from collections import deque

class Node:
    def __init__(self, name):
        self.name = name
        self.adjacent = []
        self.visited = False

# Breadth First Search function
def bfs(start):
    queue = deque()
    queue.append(start)
    start.visited = True

    while queue:
        node = queue.popleft()
        print(node.name)

        for neighbor in node.adjacent:
            if not neighbor.visited:
                neighbor.visited = True
                queue.append(neighbor)

# Create a graph
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")
node5 = Node("E")
node6 = Node("F")
node7 = Node("G")

node1.adjacent = [node2, node3]
node2.adjacent = [node4, node5]
node3.adjacent = [node6, node7]

# Run BFS
bfs(node1)

In this implementation, the Node class is the same as in the DFS implementation, and the bfs function takes a starting node as input. It initializes an empty queue and adds the starting node to it. Then, while the queue is not empty, it dequeues the next node, visits it, and adds its unvisited neighbors to the queue. The visited flag is used to prevent revisiting nodes that have already been processed.

The code creates a small graph with seven nodes and six edges, and runs the bfs function on the first node. The output should be the names of the nodes visited in breadth-first order, which in this case should be "A", "B", "C", "D", "E", "F", and "G".