Uninformed search algorithms

 

Expt No: 1                                           Uninformed search algorithms

Date:

 

Aim: To write a program to demonstrate Uninformed search algorithms – BFS and DFS algorithms

 

Program

 

# Uninformed search algorithms

from collections import deque

 

class TreeNode:

    def __init__(self, value):

        self.value = value

        self.children = []

 

    def add_child(self, child_node):

        self.children.append(child_node)

 

def bfs_traversal(root):

    if not root:

        return

 

    queue = deque([root])

 

    while queue:

        node = queue.popleft()

        print(node.value, end='\t')

 

        for child in node.children:

            queue.append(child)

 

def dfs_preorder_traversal(node):

    if not node:

        return

 

    print(node.value, end='\t')

 

    for child in node.children:

        dfs_preorder_traversal(child)

 

def dfs_inorder_traversal(node):

    if not node:

        return

 

    if len(node.children) >= 2:

        dfs_inorder_traversal(node.children[0])

 

    print(node.value, end='\t')

 

    if len(node.children) == 2:

        dfs_inorder_traversal(node.children[1])

 

def dfs_postorder_traversal(node):

    if not node:

        return

 

    for child in node.children:

        dfs_postorder_traversal(child)

 

    print(node.value, end='\t')

 

# Create nodes

root = TreeNode("A")

node_b = TreeNode("B")

node_c = TreeNode("C")

node_d = TreeNode("D")

node_e = TreeNode("E")

 

# Connect nodes

root.add_child(node_b)

root.add_child(node_c)

node_b.add_child(node_d)

node_b.add_child(node_e)

 

# BFS traversal

print("BFS Traversal:")

bfs_traversal(root)

print()

 

# DFS traversals

print("DFS Preorder Traversal:")

dfs_preorder_traversal(root)

print()

 

print("DFS Inorder Traversal:")

dfs_inorder_traversal(root)

print()

 

print("DFS Postorder Traversal:")

dfs_postorder_traversal(root)

 

Result: Thus the program to demonstrate uninformed search algorithms was written and executed

 

 

 

Input Tree

 

 

 

Sample Output

 

AIMLLab>python bfsdfs.py

BFS Traversal:

A       B       C       D       E

DFS Preorder Traversal:

A       B       D       E       C

DFS Inorder Traversal:

D       B       E       A       C

DFS Postorder Traversal:

D       E       B       C       A