Table of Contents
1 Write a program to implement Breadth First Search.....................................................................1
1.1 Source Code...........................................................................................................................1
1.2 Output Window.....................................................................................................................1
2 Write a program to implement Depth First Search.......................................................................2
2.1 Source Code...........................................................................................................................2
2.2 Output Window.....................................................................................................................2
3 Write a program to implement Greedy Best Search......................................................................3
3.1 Source Code...........................................................................................................................3
3.2 Output Window.....................................................................................................................3
4 Write a program to implement Depth Limit Search......................................................................4
4.1 Source Code...........................................................................................................................4
4.2 Output Window.....................................................................................................................4
5 Write an example for prolog..........................................................................................................5
5.1 Source Code...........................................................................................................................5
5.2 Output Window.....................................................................................................................5
6 Write a program to show relation in prolog..................................................................................6
6.1 Source Code...........................................................................................................................6
6.2 Output Window.....................................................................................................................6
7 Write a program to display factorial of a user defined number using recursion...........................7
7.1 Source Code...........................................................................................................................7
7.2 Output Window.....................................................................................................................7
i
1 Write a program to implement Breadth First Search
1.1 Source Code
graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}
visited = []
queue = []
def bfs(visited, graph, node):
visited.append(node)
queue.append(node)
while queue:
m = queue.pop(0)
print (m, end = " ")
for neighbour in graph[m]:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)
print("Following is the Breadth-FIRST SEARCH")
bfs(visited, graph, '5')
1.2 Output Window
1
2 Write a program to implement Depth First Search
2.1 Source Code
graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}
visited = set() # Set to keep track of visited nodes of graph.
def dfs(visited, graph, node): #function
if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
# Driver Code
print("Following is the DepTH-FIRST SEARCH")
dfs(visited, graph, '5')
2.2 Output Window
2
3 Write a program to implement Greedy Best Search
3.1 Source Code
from queue import PriorityQueue
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = {i: [] for i in range(vertices)}
def add_edge(self, u, v, weight):
self.graph[u].append((v, weight))
def greedy_best_first_search(self, start, goal):
visited = [False] * self.V
pq = PriorityQueue()
pq.put((0, start)) # (priority, vertex)
while not pq.empty():
cost, current = pq.get()
if current == goal:
print(f"Reached goal: {goal} with cost:
{cost}")
return
visited[current] = True
for neighbor, weight in self.graph[current]:
if not visited[neighbor]:
pq.put((weight, neighbor))
print(f"Visiting node {neighbor} with
priority {weight}")
print("Goal not reachable")
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 2, 3)
g.add_edge(1, 3, 4)
g.add_edge(2, 3, 1)
g.add_edge(3, 4, 2)
start = 0
goal = 4
print(f"Greedy Best-First Search from {start} to {goal}:")
g.greedy_best_first_search(start, goal)
3.2 Output Window
3
4 Write a program to implement Depth Limit Search
4.1 Source Code
graph = {
'A':['B','C'],
'B':['D','E'],
'C':['F','G'],
'D':['H','I'],
'E':['J','K']}
def DLS(start,goal,path,level,maxD):
print('\nCurrent level-->',level)
print('Goal node testing for',start)
path.append(start)
if start == goal:
print("Goal test successful")
return path
print('Goal node testing failed')
if level==maxD:
return False
print('\nExpanding the current node',start)
for child in graph[start]:
if DLS(child,goal,path,level+1,maxD):
return path
path.pop()
return False
start = 'A'
goal = input('Enter the goal node:-')
maxD = int(input("Enter the maximum depth limit:-"))
print()
path = list()
res = DLS(start,goal,path,0,maxD)
if(res):
print("Path to goal node available")
print("Path",path)
else:
print("No path available for goal node in given depth
limit")
4.2 Output Window
4
5
5 Write an example for prolog
5.1 Source Code
valuable(gold).
female(sita).
owns(sita,gold).
father(hari,jiya).
5.2 Output Window
5.3
6
6 Write a program to show relation in prolog
6.1 Source Code
animal(elephant).
animal(horse).
animal(dog).
animal(cat).
bigger_than(elephant, horse).
bigger_than(horse, dog).
bigger_than(dog, cat).
color(elephant, grey).
color(horse, brown).
color(dog, black).
color(cat, white).
6.2 Output Window
7
7 Write a program to display factorial of a user defined number using
recursion.
7.1 Source Code
factorial(0,1).
factorial(N,F):-
N>0,
N1 is N-1,
factorial(N1,F1),
F is N*F1.
findfactorial:-
write('\n Enter a number '),
read(Num),
factorial(Num,F),
write('\n Factorial of '),write(Num),write(' is '),write(F).
7.2 Output Window
