BREADTH FIRST SEARCH

 Ex No: 1      Implementation of Uninformed search algorithms (BFS)

CLICK HERE : PROGRAM LINK

 -------------------------------------------------------------------------------------------------------------

NOTE:

BFS - Uninformed Search (Blind Search)

Uninformed search algorithms don't have additional information about the problem, except for the structure of the problem itself. They explore the search space based on the current state, without using any specific knowledge or heuristics to guide the search.

Pros:

• Simplicity: Easy to implement.
• Completeness: Guaranteed to find a solution (if one exists) in some cases (like BFS or Uniform Cost Search).

Cons:

• Inefficiency: May explore large parts of the search space unnecessarily.
• High memory consumption or slow processing in some cases (e.g., DFS).

         -------------------------------------------------------------------------------------------------------------

Aim

The aim of implementing Breadth-First Search (BFS) algorithms is to traverse a graph or a tree data structure in a systematic way, visiting all nodes and edges in the structure in a particular order, without revisiting any node twice.

Algorithm

Breadth-First Search (BFS) algorithm:

1. Create an empty queue and enqueue the starting node

2. Mark the starting node as visited

3. While the queue is not empty, dequeue a node from the queue and visit it

4. Enqueue all of its neighbors that have not been visited yet, and mark them as visited

5. Repeat steps 3-4 until the queue is empty.

PROGRAM:

# Define the graph

graph = {

    '5' : ['3','7'],

    '3' : ['2', '4'],

    '7' : ['8'],

    '2' : [],

    '4' : ['8'],

    '8' : []

}

visited = []  # List for visited nodes

queue = []    # Initialize a queue

# BFS function

def bfs(visited, graph, node):

    visited.append(node)  # Mark the starting node as visited

    queue.append(node)    # Add the starting node to the queue

    while queue:  # Continue visiting nodes as long as the queue is not empty

        m = queue.pop(0)  # Get the first node from the queue

        print(m, end=" ")  # Print the node

        # Visit all the unvisited neighbors

        for neighbour in graph[m]:

            if neighbour not in visited:

                visited.append(neighbour)

                queue.append(neighbour)

# Driver Code

print("Following is the Breadth-First Search:")

bfs(visited, graph, '5')

O/P

Following is the Breadth-First Search

5 3 7 2 4 8

Result

Thus the program for BFS is executed successfully and output is verified