1.
IMPLEMENTATION OF UNINFORMED SEARCHING ALGORITHMS(BFS,DFS)
AIM:
To write a python program to implement uninformed searching algorithms BFS and DFS.
THEORY:
BFS DFS
Depth-First Search (DFS) in a binary tree for searching
Breadth-First Search (BFS) in a binary tree for
involves exploring the tree depth-first, prioritizing the
searching involves systematically exploring the
exploration of one branch as deeply as possible before
tree level by level. Starting from the root node,
backtracking. Beginning at the root node, DFS traverses
BFS visits all nodes at the current level before
the left subtree recursively until reaching the deepest
moving to the next level. It utilizes a queue data
node. It then backtracks and explores the right subtree
structure to manage the order of traversal, ensuring
similarly. DFS utilizes a stack to manage the order of
that nodes are visited in the order they were
traversal, allowing for the depth-first exploration of
encountered.
nodes.
ALGORITHM:
Step 1 : Start the Program.
Step 2 : Define the Node class with attributed for value, left child and right child.
Step 3 : Create a function 'insert' to insert a new node into a binary search tree.
Step 4 : Implement the function for BFS and DFS to search for a target values recursively.
Step 5 : Construct the binary tree from user input values.
Step 6 : Visualize the binary tree structure.
Step 7 : Prompt the user to choose between BFS, DFS or exit options.
Step 8 : Executed the selected search method to find the target value.
Step 9 : Display the result.
Step 10: Stop the Program.
PROGRAM :
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
else:
if value <= root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def DFS(root, target):
if root is None:
return False
print("Visiting node:", root.value) # Print the visited nod
if root.value == target:
return True
left_search = DFS(root.left, target)
if left_search:
return True
right_search = DFS(root.right, target)
return right_search
def BFS(root, target):
if root is None:
return False
queue = [root]
while queue:
current = queue.pop(0)
print("Visiting node:", current.value) # Print the visited node
if current.value == target:
return True
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return False
def construct_tree(values):
root = None
for value in values:
root = insert(root, value)
return root
def visualize_tree(root, level=0):
if root is not None:
visualize_tree(root.right, level + 1)
print(" " * level + str(root.value))
visualize_tree(root.left, level + 1)
def main():
print("Welcome to the Binary Tree Search Program!")
values = input("Enter the values of the tree nodes separated by spaces: ").split()
root = construct_tree(values)
print("\nBinary Tree Visualization:")
visualize_tree(root)
while True:
search_option = input("\nChoose an option:\n1. Breadth-First Search (BFS)\n2. Depth-First Search (DFS)\n3. Exit\nEnter the option
number: ")
if search_option == '1':
target = input("Enter the target value to search for: ").upper()
print("\nUsing BFS:")
if BFS(root, target):
print("Element", target, "found in the binary tree using BFS.")
else:
print("Element", target, "not found in the binary tree using BFS.")
elif search_option == '2':
target = input("Enter the target value to search for: ").upper()
print("\nUsing DFS:")
if DFS(root, target):
print("Element", target, "found in the binary tree using DFS.")
else:
print("Element", target, "not found in the binary tree using DFS.")
elif search_option == '3':
print("Exiting program.")
break
else:
print("Invalid option. Please enter either '1' for BFS, '2' for DFS, or '3' to exit.")
if __name__ == "__main__":
main()
OUTPUT:
Welcome to the Binary Tree Search Program!
Enter the values of the tree nodes separated by spaces: 45 55 35 50 40 25 65
Binary Tree Visualization:
65
55
50
45 40
35
25
Choose an option:
1. Breadth-First Search (BFS)
2. Depth-First Search (DFS)
3. Exit
Enter the option number: 1
Enter the target value to search for: 40
Using BFS:
Visiting node: 45
Visiting node: 35
Visiting node: 55
Visiting node: 25
Visiting node: 40
Element 40 found in the binary tree using BFS
65
55
50
45 40
35
25
Choose an option:
1. Breadth-First Search (BFS)
2. Depth-First Search (DFS)
3. Exit
Enter the option number: 2
Enter the target value to search for: 40
Using DFS:
Visiting node: 45
Visiting node: 35
Visiting node: 25
Visiting node: 40
Element 40 found in the binary tree using DFS.
65
55
50
45 40
35
25
Choose an option:
1. Breadth-First Search (BFS)
2. Depth-First Search (DFS)
3. Exit
Enter the option number: 3
Exiting program.
RESULT:
Thus the Python program to Implementing Uninformed searching algorthims BFS and DFS was coded and
executed successfully.
