Scribd
Upload
2 views

BFS algorithm.docx

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
2 views

BFS algorithm.docx

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
You are on page 1/ 4

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 = queue.popleft()
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


visited.add(current_node)

# Enqueue unvisited neighbors


for neighbor in graph.get(current_node, []):
if neighbor not in visited and neighbor not in queue:
queue.append(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