IMPLEMENT SIMPLE ADTS AS PYTHON CLASSES

1)a. Stack

stack=[]
#append() functionto push
#element in the stack
stack.append('a')
stack.append('b')
stack.append('c')
print('initial stack')
print(stack)
#element from stack in
#LIFO order
print('\n Elements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\n stack after elements are popped:')
print(stack)

Output:
initial stack
['a', 'b', 'c']
Elements popped from stack:
C
b
a
stack after elements are popped:
[]

1)b. Queue
queue=[]
print('Before Enqueue,Its Empty')
print(queue)
queue=["A","B","C"]
print('After enqueue,The queue is')
print(queue)
print('Now Enqueue or Insertion')
queue.append("D")
queue.append("E")
print(queue)
print ('After Deletion,Dequeue')
print(queue.pop(0))
print(queue)
print(queue.pop(0))
print(queue)
print(queue.pop(0))
print(queue)
print(queue.pop(0))
print(queue)

Output:
Before Enqueue,Its Empty
[]
After enqueue,The queue is
['A', 'B', 'C']
Now Enqueue or Insertion
['A', 'B', 'C', 'D', 'E']
After Deletion,Dequeue
A
['B', 'C', 'D', 'E']
B
['C', 'D', 'E']
C
['D', 'E']
D
['E']

1)c. Flower constructor

class flower:
def __init__(self,txt):
print(txt,"I am in flower class")
class jasmine(flower):
def __init__(self,txt):
print(txt,"I am in Jasmine class")
super().__init__(txt)
class rose(jasmine):
def __init__(self,txt):
print(txt,"I am in Rose class")
super().__init__(txt)
class lilly(rose):
def __init__(self,txt):
print(txt,"I am in lilly class")
super().__init__(txt)
class tulip(lilly,rose):
def __init__(self,txt):
print(txt,"I am in tulip class ")
super().__init__("final Derived")
d=tulip("It is tulip")
h=rose("I am Rose")

Output:

It is tulip I am in tulip class

final Derived I am in lilly class
final Derived I am in Rose class
final Derived I am in Jasmine class
final Derived I am in flower class
I am Rose I am in Rose class
I am Rose I am in Jasmine class
I am Rose I am in flower class
 IMPLEMENT RECURSIVE ALGORITHMS IN PYTHON

2)a. Factorial

num=7
factorial=1
if num<0:
print("Sorry,factorial does not exist for negative numbers")
elif num==0:
print("The factorial of 0 is 1")
else:
for i in range(1,num+1):
factorial=factorial*i
print("The factorial of",num,"is",factorial)

Output:
The factorial of 7 is 5040

2)b. Fibonacci series

def recur_fibo(n):
if n<=1:
return n
else:
return(recur_fibo(n-1)+recur_fibo(n-2))
nterms=10
if nterms<=0:
print("Please enter a positive interger")
else:
print("Fibonacci sequence:")
 for i in range(nterms):
print(recur_fibo(i))

Output:
Fibonacci sequence:
0
1
1
2
3
5
8
13
21
34

2)c. Binary Search

def binary_search(arr,low,high,x):
if high>=low:
mid=(high+low)//2
if arr[mid]==x:
return mid
elif arr[mid]>x:
return binary_search(arr,low,mid-1,x)
else:
return binary_search(arr,mid+1,high,x)
else:
return-1
arr=[2,3,4,10,40]
x=10
result=binary_search(arr,0,len(arr)-1,x)
if result!=-1:
print("Element is present at index",str(result))
else:
print("Element is not present in array")

Output:

Element is present at index 3

3. IMPLEMENT LIST ADT USING PYTHON ARRAYS

import array as arr

a=arr.array('i',[1,2,3])
print("Array before insertion:",end=" ")
for i in range(0,3):
print(a[i],end=" ")
print()
a.insert(1,4)
print("Array after insertion:",end=" ")
for i in (a):
print(i,end=" ")
print()
a.append(5)
print("Array after insertion at end:",end=" ")
for i in (a):
print(i,end=" ")
print()
a.remove(5)
print("Array after Deletion:",end=" ")
for i in (a):
print(i,end=" ")
print()
x=a.index(4)
print("Value 4 is present in location")
print(x)

Output:
Array before insertion: 1 2 3
Array after insertion: 1 4 2 3
Array after insertion at end: 1 4 2 3 5
Array after Deletion: 1 4 2 3
Value 4 is present in location
1

4. IMPLEMENT OF LINKED LIST USING PYTHON LIST

class Node:
def __init__(self,dataval=None):
self.dataval=dataval
self.nextval=None
class slinkedlist:
def __init__(self):
self.headval=None
self.head=None
def atend(self,newdata):
newnode=Node(newdata)
if self.headval is None:
self.headval=newnode
return
last=self.headval
while(last.nextval):
last=last.nextval
last.nextval=newnode
def listprint(self):
printval=self.headval
while printval is not None:
print(printval.dataval)
printval =printval.nextval
def inbetween(self,middle_node,newdata):
if middle_node is None:
print("The mentioned node is absent")
return
newnode=node(newdata)
newnode.nextval=middle_node.nextval
middle_node.nextval=newnode
def removenode(self,removekey):
head=self.headval
if(self.headval is not None):
if(self.headval.dataval==removekey):
self.headval=head.nextval
head=None
return
 prev=None
while(head is not None):
if head.dataval==removekey:
break
prev=head
head=head.nextval
if (head==None):
return
prev.nextval=head.nextval
head=None
list = slinkedlist()
list.atend("Monday")
list.atend("Tuesday")
list.atend("Wednesday")
list.listprint()
list.atend("Thursday")
list.listprint()
l2=list.headval.nextval
list.inbetween(l2,"Friday")
list.listprint()
list.removenode("Tuesday")
list.listprint()

Output:

Monday
Tuesday
Wednesday
Monday
Tuesday
Wednesday
Thursday
Monday
Tuesday
Wednesday
Thursday
Monday
Wednesday
Thursday

5. IMPLEMENTATION OF STACK AND QUEUE ADTS

5a. Stack using array

class stackusingarray:
def __init__(self):
self.stack=[]
def push(self,element):
self.stack.append(element)
def pop(self):
if(not self.isEmpty()):
lastelement=self.stack[-1]
del(self.stack[-1])
return lastelement
else:
return("Stack already Empty")
def isEmpty(self):
return self.stack==[]
def printstack(self):
 print(self.stack)
if __name__=="__main__":
s=stackusingarray()
print("*"*5+"Stack Using Array"+5*"*")
while(True):
print("Enter Your Choice:")
el=int(input("1 for push \n 2 for pop \n 3 to check if it is Empty \n 4 to print stack \n 5 to exit \n"))
if(el==1):
item=input("Enter Element to push in stack\n")
s.push(item)
if(el==2):
print("Popped Element is")
print(s.pop())
if(el==3):
print(s.isEmpty())
if(el==4):
s.printstack()
if(el==5):
break

Output:

*****Stack Using Array*****

Enter Your Choice:
1 for push
2 for pop
3 to check if it is Empty
4 to print stack
5 to exit
1
Enter Element to push in stack
4
Enter Your Choice:
1 for push
2 for pop
3 to check if it is Empty
4 to print stack
5 to exit
1
Enter Element to push in stack
7
Enter Your Choice:
1 for push
2 for pop
3 to check if it is Empty
4 to print stack
5 to exit
2
Popped Element is
7
Enter Your Choice:
1 for push
2 for pop
3 to check if it is Empty
4 to print stack
5 to exit
2
Popped Element is
4
Enter Your Choice:
1 for push
2 for pop
3 to check if it is Empty
4 to print stack
5 to exit
2
Popped Element is
Stack already Empty
Enter Your Choice:
1 for push
2 for pop
3 to check if it is Empty
4 to print stack
5 to exit
5
b. Queue using array

class queue:
def __init__(self):
self.items=[]
def is_Empty(self):
return self.items==[]
def enqueue(self,data):
self.items.append(data)
def dequeue(self):
return self.items.pop(0)
q=queue()
while True:
print('enqueue<value>')
print('dequeue')
print('quit')
do=input("what would you like to do?").split()
operation=do[0].strip().lower()
if operation=='enqueue':
q.enqueue(int(do[1]))
elif operation=='dequeue':
if q.is_Empty():
print('queue isEmpty:')
else:
print('dequeued value:',q.dequeue())
elif operation=='quit':
break

Output:

enqueue<value>
dequeue
quit
what would you like to do?enqueue 90
enqueue<value>
dequeue
quit
what would you like to do?enqueue 45
enqueue<value>
dequeue
quit
what would you like to do?dequeue
dequeued value: 90
enqueue<value>
dequeue
quit
what would you like to do?dequeue
dequeued value: 45
enqueue<value>
dequeue
quit
what would you like to do?dequeue
queue isEmpty:
enqueue<value>
dequeue
quit
what would you like to do?quit

5c. Stack using linkedlist

class Node:
def __init__(self,data):
self.data=data
self.next=None
class stack:
def __init__(self):
self.head=None
def push(self,data):
if self.head is None:
 self.head=Node(data)
else:
new_node=Node(data)
new_node.next=self.head
self.head=new_node
def pop(self):
if self.head is None:
return None
else:
popped=self.head.data
self.head=self.head.next
return popped
a_stack=stack()
while True:
print('push<value>')
print('pop')
print('quit')
do=input('what would you lke to do?').split()
operation=do[0].strip().lower()
if operation=='push':
a_stack.push(int(do[1]))
elif operation=='pop':
popped=a_stack.pop()
if popped is None:
print('stack is empty.')
else:
print('popped value:',int(popped))
elif operation=='quit':
 break

Output:

push<value>
pop
quit
what would you lke to do?pop
stack is empty.
push<value>
pop
quit
what would you lke to do?push 5
push<value>
pop
quit
what would you lke to do?push 8
push<value>
pop
quit
what would you lke to do?pop
popped value: 8
push<value>
pop
quit
what would you lke to do?pop
popped value: 5
push<value>
pop
quit
what would you lke to do?pop
stack is empty.
push<value>
pop
quit
what would you lke to do?quit

5d. Queue using linkedlist

class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.head = None
self.last = None
def enqueue(self, data):
if self.last is None:
self.head = Node(data)
self.last = self.head
else:
self.last.next = Node(data)
self.last = self.last.next
def dequeue(self):
if self.head is None:
return None
else:
 to_return = self.head.data
self.head = self.head.next
return to_return
a_queue=Queue()
while True:
print("enqueue <value>")
print("dequeue")
print("quit")
do=input("What would you like to do?").split()
operation=do[0].strip().lower()
if operation=='enqueue':
a_queue.enqueue(int(do[1]))
elif operation=='dequeue':
dequeued=a_queue.dequeue()
if dequeued is None:
print('Queue is empty.')
else:
print('Dequeued element:',int(dequeued))
elif operation=='quit':
break

Output:

enqueue <value>
dequeue
quit
What would you like to do?enqueue 4
enqueue <value>
dequeue
quit
What would you like to do?enqueue 9
enqueue <value>
dequeue
quit
What would you like to do?dequeue
Dequeued element: 4
enqueue <value>
dequeue
quit
What would you like to do?dequeue
Dequeued element: 9
enqueue <value>
dequeue
quit
What would you like to do?dequeue
Queue is empty.
enqueue <value>
dequeue
quit
What would you like to do?quit

6. APPLICATION OF STACK

6a. Postfix Evaluation

operators=set(['*','-','+','%','/','**'])
def evaluate_postfix(expression):
stack=[]
for i in expression:
 if i not in operators:
stack.append(i)
else:
a=stack.pop()
b=stack.pop()
if i=='+':
res=int(b)+int(a)
elif i=='-':
res=int(b)-int(a)
elif i=='*':
res=int(b)*int(a)
elif i=='%':
res=int(b)%int(a)
elif i=='/':
res=int(b)/int(a)
elif i=='**':
res=int(b)**int(a)
stack.append(res)
return(''.join(map(str,stack)))
expression=input("Enter the postfix expressions:")
print()
print("postfix expression entered:",expression)
print("evaluation result:",evaluate_postfix(expression))

Output:
Enter the postfix expressions:634*+2-
postfix expression entered: 634*+2-
evaluation result: 16
6b. Application of Queue ADT

print("FIRST COME FIRST SERVE SCHEDULLING")

n=int(input("Enter number of processes:"))
d=dict()
for i in range(n):
key="p"+str(i+i)
a=int(input("Enter arival time of process"+str(i+1)+":"))
b=int(input("Enter burst time of process"+str(i+1)+":"))
l=[]
l.append(a)
l.append(b)
d[key]=l
d=sorted(d.items(),key=lambda item: item[1][0])
ET=[]
for i in range(len(d)):
if(i==0):
ET.append(d[i][1][1])
else:
ET.append(ET[i-1]+d[i][1][1])
TAT=[]
for i in range(len(d)):
TAT.append(ET[i]-d[i][1][0])
WT=[]
for i in range(len(d)):
WT.append(TAT[i]-d[i][1][1])
avg_WT=0
for i in WT:
avg_WT+=i
avg_WT=(avg_WT/n)
print("process|arrival|burst|exit|turn around|wait|")
for i in range(n):
print("",d[i][0],"|",d[i][0],"|",d[i][1][1],"|",ET[i],"|",TAT[i],"|",WT[i],"|")
print("Average waiting Time:",avg_WT)

Output:

FIRST COME FIRST SERVE SCHEDULLING

Enter number of processes:3
Enter arival time of process1:1
Enter burst time of process1:4
Enter arival time of process2:0
Enter burst time of process2:3
Enter arival time of process3:2
Enter burst time of process3:5
process|arrival|burst|exit|turn around|wait|
p2 | p2 | 3 | 3 | 3 | 0 |
p0 | p0 | 4 | 7 | 6 | 2 |
p4 | p4 | 5 | 12 | 10 | 5 |
Average waiting Time: 2.3333333333333335

7a. Linear Search

def linear_search(list1,n,key):
for i in range(0,n):
if(list1[i]==key):
return i
return -1
list1=[1,3,5,4,7,9]
key=7
n=len(list1)
res=linear_search(list1,n,key)
if(res==-1):
print("Elements not found")
else:
print("Element found at index:",res)

Output:
Element found at index: 4

7b. Binary Search

def binary_search(list1,n):
low=0
high=len(list1)-1
mid=0
while low<=high:
mid=(high+low)//2
if list1[mid]<n:
low=mid+1
elif list1[mid]>n:
high=mid-1
else:
return mid
return -1
list1=[12,24,32,39,45,50,54]
print(list1)
n=int(input("Enter the element to be searched:"))
result=binary_search(list1,n)
if result!=-1:
print("Element is present at index",str(result))
else:
print("Element is not present in list1")

Output:

[12, 24, 32, 39, 45, 50, 54]

Enter the element to be searched:45
Element is present at index 4

7c. Bubble sort

def bubble_sort(list1):
for i in range(0,len(list1)-1):
for j in range(len(list1)-1):
if(list1[j]>list1[j+1]):
temp=list1[j]
list1[j]=list1[j+1]
list1[j+1]=temp
return list1
list1=[5,3,8,6,7,2]
print("The unsorted list is:",list1)
print("The sorted list is:",bubble_sort(list1))

Output:
The unsorted list is: [5, 3, 8, 6, 7, 2]
The sorted list is: [2, 3, 5, 6, 7, 8]
7d. Insertion sort

def insertionsort(arr):
n=len(arr)
if n<=1:
return
for i in range(1,n):
key=arr[i]
j=i-1
while j>=0 and key<arr[j]:
arr[j+1]=arr[j]
j-=1
arr[j+1]=key
arr=[12,11,13,5,6]
print("before sorting")
print(arr)
insertionsort(arr)
print("Ascending order is")
print(arr)

Output:

before sorting
[12, 11, 13, 5, 6]
Ascending order is
[5, 6, 11, 12, 13]

7e. Selection Sort

def selectionsort(array,size):
for ind in range(size):
 min_index=ind
for j in range(ind +1,size):
if array[j]<array[min_index]:
min_index=j
(array[ind],array[min_index])=(array[min_index],array[ind])
arr=[-2,45,0,11,-9,88,-97,-202,747]
size=len(arr)
selectionsort(arr,size)
print("The array after sorting in ascending order by selection sort:")
print(arr)

Output:

The array after sorting in ascending order by selection sort:

[-202, -97, -9, -2, 0, 11, 45, 88, 747]

7f. Quick Sort

def quicksort(arr):
if len(arr)<=1:
return arr
else:
pivot=arr[0]
left=[x for x in arr[1:]if x<pivot]
right=[x for x in arr[1:]if x>=pivot]
return quicksort(left)+[pivot]+quicksort(right)
user_input=input("Enter the array elements seperated by spaces:")
arr=[int(x)for x in user_input.split()]
sorted_arr=quicksort(arr)
print("sorted array:",sorted_arr)
Output:

Enter the array elements seperated by spaces:78 12 5 98 46 73 23

sorted array: [5, 12, 23, 46, 73, 78, 98]

8. Implementation of Hash Table

class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None

class HashTable:
def __init__(self, capacity):
self.capacity = capacity
self.size = 0
self.table = [None] * capacity

def hash(self, key):

return hash(key) % self.capacity
#Insert
def insert(self, key, value):
index = self.hash(key)
if self.table[index] is None:
self.table[index] = Node(key, value)
self.size += 1
else:
 current = self.table[index]
while current:
if current.key == key:
current.value = value
return
current = current.next
new_node = Node(key, value)
new_node=self.table[index]
self.table[index]=new_node
self.size += 1
#Search
def search(self, key):
index = self.hash(key)
current = self.table[index]
while current:
if current.key == key:
return current.value
current = current.next
raise KeyError(key)
#Remove
def remove(self, key):
index = self.hash(key)
previous = None
current = self.table[index]
while current:
if current.key == key:
if previous:
previous.next = current.next
 else:
self.table[index] = current.next
self.size -= 1
return
previous = current
current = current.next
raise KeyError(key)

def __len__(self):
return self.size

def __contains__(self, key):

try:
self.search(key)
return True
except KeyError:
return False

if __name__ == '__main__':
ht = HashTable(5)
ht.insert("apple", 3)
ht.insert("banana", 2)
ht.insert("cherry", 5)
print("apple" in ht)
print("durian" in ht)
print(ht.search("banana"))
ht.insert("banana", 4)
print(ht.search("banana"))
 ht.remove("apple")
print(len(ht))

Output:
True
False
2
4
2

9. Tree Traversal and Traversal Algorithms

class Node:
def __init__(self, data):
self.left = None
self.right =None
self.data =data
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
 else:
self.data = data
def PrintTree(self):
if self.left:
self.left.PrintTree()
print(self.data)
if self.right:
self.right.PrintTree()
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
def preorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.preorderTraversal(root.left)
res = res + self.preorderTraversal(root.right)
return res
def postorderTraversal(self, root):
res = []
if root:
res = self.postorderTraversal(root.left)
res = res + self.postorderTraversal(root.right)
res.append(root.data)
 return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print('Inorder Traversal')
print(root.inorderTraversal(root))
print('Preorder Traversal')
print(root.preorderTraversal(root))
print('Postorder Traversal')
print(root.postorderTraversal(root))

Output:
Inorder Traversal
[10, 14, 19, 27, 31, 35, 42]
Preorder Traversal
[27, 14, 10, 19, 35, 31, 42]
Postorder Traversal
[10, 19, 14, 31, 42, 35, 27]

10. Implemetation of Binary Search Tree

class Node:
def __init__(self, key):
self.key = key
 self.left = None
self.right = None
def inorder(root):
if root is not None:
inorder(root.left)
print(str(root.key) + "->", end=' ')
inorder(root.right)
def insert(node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
return node
def minValueNode(node):
current = node
while(current.left is not None):
current = current.left
return current
def maxValueNode(node):
current=node
while(current.right is not None):
current=current.right
return current
def search(root,value):
if root==None:
return False
 elif root.key==value:
return True
elif root.key<value:
return search(root.right,value)
else:
return search(root.left,value)
def deleteNode(root, key):
if root is None:
return root
if key < root.key:
root.left = deleteNode(root.left, key)
elif(key > root.key):
root.right = deleteNode(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = minValueNode(root.right)
root.key = temp.key
root.right = deleteNode(root.right, temp.key)
return root
root = None
root = insert(root, 8)
root = insert(root, 3)
root = insert(root, 1)
root = insert(root, 6)
root = insert(root, 7)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 4)
print("Inorder traversal: ", end=' ')
inorder(root)
print("\nDelete 10")
root = deleteNode(root, 10)
print("Inorder traversal: ", end=' ')
inorder(root)
print("\nMinimum Value")
temp=minValueNode(root)
print(temp.key)
print("\nMaximum Value")
temp=maxValueNode(root)
print(temp.key)
print('Searching 14')
print(search(root,14))
print('Searching 22')
print(search(root,22))

Output:
Inorder traversal: 1-> 3-> 4-> 6-> 7-> 8-> 10-> 14->
Delete 10
Inorder traversal: 1-> 3-> 4-> 6-> 7-> 8-> 14->
Minimum Value: 1
Maximum Value: 14
Searching 14: True
Searching 22: False

11.Implemetation of Heaps

def min_heapify(A,k):
l=left(k)
r=right(k)
if l<len(A) and A[l]<A[k]:
smallest=l
else:
smallest=k
if r<len(A) and A[r]<A[smallest]:
smallest=r
if smallest!=k:
A[k],A[smallest]=A[smallest],A[k]
min_heapify(A,smallest)
def left(k):
return 2*k+1
def right(k):
return 2*k+2
def build_min_heap(A):
n=int((len(A)//2)-1)
for k in range(n,-1,-1):
min_heapify(A,k)
A=[3,9,2,1,4,5]
build_min_heap(A)
print(A)

Output:
[1, 3, 2, 9, 4, 5]

12. Python Program To Implement Breadth First Search

12a.bfs
graph={
'A':['B','C'],
'B':['D','E'],
'C':['F'],
'D':[],
'E':['F'],
'F':[]
}
visited=[]
queue=[]
def bfs(visited,graph,node):
visited.append(node)
queue.append(node)
while queue:
s=queue.pop(0)
print(s,end=" ")
for neighbour in graph[s]:
if neighbour not in visited:
 visited.append(neighbour)
queue.append(neighbour)
bfs(visited,graph,'A')

Output:

A B C D E F

12b.dfs

graph={
'A':['B','c'],
'B':['D','E'],
'c':['F'],
'D':[],
'E':['F'],
'F':[]
}
visited=set()
def dfs(visited,graph,node):
if node not in visited:
print(node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited,graph,neighbour)
dfs(visited,graph,'A')

Output:
A
B
D
E
F
C

13. Implementation of Single Source Shortest Path Algorithm

class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]

def print_solution(self, dist):

print("Vertex \t Distance from Source")
for node in range(self.V):
print(node, "\t", dist[node])

def min_distance(self, dist, spt_set):

min_distance = float('inf')
min_index = -1

for v in range(self.V):
if dist[v] < min_distance and not spt_set[v]:
min_distance = dist[v]
min_index = v
 return min_index

def dijkstra(self, src):

dist = [float('inf')] * self.V
dist[src] = 0
spt_set = [False] * self.V

for _ in range(self.V):
u = self.min_distance(dist, spt_set)
spt_set[u] = True

for v in range(self.V):
if (self.graph[u][v] > 0 and
not spt_set[v] and
dist[v] > dist[u] + self.graph[u][v]):
dist[v] = dist[u] + self.graph[u][v]
self.print_solution(dist)

# Create a graph instance

g = Graph(9)
g.graph = [
[0, 4, 0, 0, 0, 0, 8, 0, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
 [0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
g.dijkstra(0)

Output:
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 20
5 10
6 8
7 9
8 14

14.Implementation of Minimum Spanning Tree Algorithms

14a. Prim’s Algorithm

INF=99999
N=5
G=[[0,19,5,0,0],
[19,0,5,9,2],
[5,5,0,1,6],
 [0,9,1,0,1],
[0,2,6,1,0]]
selected_node=[False]*N
no_edge=0
selected_node[0]=True
print("edge:weight \n")
while(no_edge<N-1):
minimum=INF
a=0
b=0
for m in range(N):
if selected_node[m]:
for n in range(N):
if((not selected_node[n])and G[m][n]):
if minimum>G[m][n]:
minimum=G[m][n]
a=m
b=n
print(str(a)+"_"+str(b)+":"+str(G[a][b]))
selected_node[b]= True
no_edge+=1

Output:
Edge : weight
0_2 : 5
2_3 : 1
3_4 : 1
4_1 : 2
14b. Kruska’s Algorithm

class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []

def add_edge(self, u, v, w):

self.graph.append([u, v, w])

def find(self, parent, i):

if parent[i] == i:
return i
return self.find(parent, parent[i])

def apply_union(self, parent, rank, x, y):

xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskal_algo(self):
result = []
i, e = 0, 0
 self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i=i+1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e=e+1
result.append([u, v, w])
self.apply_union(parent, rank, x, y)
for u, v, weight in result:
print("%d - %d: %d" % (u, v, weight))

g = Graph(6)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 2)
g.add_edge(1, 0, 4)
g.add_edge(2, 0, 4)
g.add_edge(2, 1, 2)
g.add_edge(2, 3, 3)
g.add_edge(2, 5, 2)
g.add_edge(2, 4, 4)
g.add_edge(3, 2, 3)
g.add_edge(3, 4, 3)
g.add_edge(4, 2, 4)
g.add_edge(4, 3, 3)
g.add_edge(5, 2, 2)
g.add_edge(5, 4, 3)
g.kruskal_algo()

Output:
1–2 : 2
2–5 : 2
2–3 : 3
3–4 : 3
0–1 : 4

15. Implementation of AVL Tree Algorithm

class treeNode(object):
def __init__(self, value):
self.value = value
self.l = None
self.r = None
self.h = 1

class AVLTree(object):
def insert(self, root, key):
if not root:
 return treeNode(key)
elif key < root.value:
root.l = self.insert(root.l, key)
else:
root.r = self.insert(root.r, key)
root.h = 1 + max(self.getHeight(root.l), self.getHeight(root.r))
b = self.getBal(root)
if b > 1 and key < root.l.value:
return self.rRotate(root)
if b < -1 and key > root.r.value:
return self.lRotate(root)
if b > 1 and key > root.l.value:
root.l = self.lRotate(root.l)
return self.rRotate(root)
if b < -1 and key < root.r.value:
root.r = self.rRotate(root.r)
return self.lRotate(root)
return root

def lRotate(self, z):

y = z.r
T2 = y.l
y.l = z
z.r = T2
z.h = 1 + max(self.getHeight(z.l), self.getHeight(z.r))
y.h = 1 + max(self.getHeight(y.l), self.getHeight(y.r))
return y
 def rRotate(self, z):
y = z.l
T3 = y.r
y.r = z
z.l = T3
z.h = 1 + max(self.getHeight(z.l), self.getHeight(z.r))
y.h = 1 + max(self.getHeight(y.l), self.getHeight(y.r))
return y

def getHeight(self, root):

if not root:
return 0
return root.h

def getBal(self, root):

if not root:
return 0
return self.getHeight(root.l) - self.getHeight(root.r)

def preOrder(self, root):

if not root:
return
print("{0}".format(root.value), end="")
self.preOrder(root.l)
self.preOrder(root.r)

# Driver code
Tree = AVLTree()
root = None
root = Tree.insert(root, 1)
root = Tree.insert(root, 2)
root = Tree.insert(root, 3)
root = Tree.insert(root, 4)
root = Tree.insert(root, 5)
root = Tree.insert(root, 6)
print("PreOrder traversal of the constructed AVL tree is:")
Tree.preOrder(root)
print()

Output:

PreOrder traversal of the constructed AVL tree is:

4 2 1 3 5 6