Scribd
Upload
9 views4 pages

BFS Algorithm

The document outlines the implementation of the Breadth-First Search (BFS) algorithm in Python using a level-order traversal technique. It details the steps for initializing data structures, processing nodes, checking for a goal, and managing visited nodes and neighbors. An example graph is provided, along with a complete Python program demonstrating the BFS algorithm and its successful execution.

Uploaded by

haseenafrn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views4 pages

BFS Algorithm

The document outlines the implementation of the Breadth-First Search (BFS) algorithm in Python using a level-order traversal technique. It details the steps for initializing data structures, processing nodes, checking for a goal, and managing visited nodes and neighbors. An example graph is provided, along with a complete Python program demonstrating the BFS algorithm and its successful execution.

Uploaded by

haseenafrn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1.

​ Implement and demonstrate the BFS algorithm in python


using level-order traversal technique commonly used in
Artificial Intelligence (AI) applications.

Aim:

To implement the Breadth-First Search (BFS) algorithm in Python for traversing a graph
and finding a specific goal node
Algorithm:

 Initialize Data Structures:

●​ Create an empty queue (using deque) and add the starting node to it.
●​ Create an empty set visited to keep track of visited nodes.

 While the Queue is Not Empty:

●​ Dequeue the front node (current_node) from the queue.


●​ Print or process the current_node.

 Check if Goal is Found:

●​ If current_node matches the goal, return a success message.

 Mark the Node as Visited:

●​ Add current_node to the visited set.

 Enqueue Neighbors:

●​ Iterate over the neighbors of current_node in the graph.


●​ For each neighbor:
●​ If it has not been visited and is not already in the queue, add it to the queue.

 End the Search:

●​ If the queue becomes empty and the goal is not found, return a failure message.

Program:
from collections import deque

def bfs(graph, start, goal):


# Initialize the queue with the starting node
queue = deque([start])
# Keep track of visited nodes
visited = set()

while queue:
# Dequeue a node from the queue
current_node = [Link]()
print(f"Visiting: {current_node}")

# Check if the goal is reached


if current_node == goal:
return f"Goal '{goal}' found!"

# Mark the current node as visited


[Link](current_node)

# Enqueue unvisited neighbors


for neighbor in [Link](current_node, []):
if neighbor not in visited and neighbor not in queue:
[Link](neighbor)

return f"Goal '{goal}' not found."

# Example Graph (Adjacency List)


graph = {
'A': ['B', 'C', 'D'],
'B': ['E', 'F'],
'C': ['G'],
'D': ['H', 'I'],
'E': ['J'],
'F': [],
'G': [],
'H': [],
'I': [],
'J': []
}

# Run BFS
start_node = 'A'
goal_node = 'J'
result = bfs(graph, start_node, goal_node)
print(result)

Output:
Result:

The Breadth-First Search (BFS) algorithm was successfully implemented in Python.

You might also like