R.V.

GOVERNMENT ARTS COLLEGE

CHENGALPATTU – 603 001.
(Affiliated to University of Madras)
P.G. Department of Computer Science

PRACTICAL RECORD NOTEBOOK

Register Number :

Name :

Class :

Subject :

Semester :
 R.V. GOVERNMENT ARTS COLLEGE
CHENGALPATTU – 603 001.
(Affiliated to University of Madras)

P.G. Department of Computer Science

Register No. : _______________________________

Class : M.Sc., Computer Science – First Year

Subject : Practical I – Data Structure and Algorithms Lab

This is to certify that this is a Bonafide Record of Practical

workdone by ………………………………………, P.G. Department of Computer
Science, R.V. Government Arts College, Chengalpattu – 603001during the
academic year 2022 - 2023.

Staff In-Charge Head of the Department

Submitted for the M.Sc., Degree University Practical

Examinationheldon ……………………….. at R.V. Government Arts
College, Chengalpattu.

Internal Examiner External Examiner

 Date
Ex.No. Program Name Page Signature
No.
Singly linked list.
i)Creation
ii) Insertion
1 iii) Deletion
iv) Traversal

Doubly linked list.

i)Creation
ii)Insertion
2 iii) Deletion
iv) Traversal in both ways.
Implements using java generic
3 class, the stack (its operations)
Implements using java generic
4 class, the queue (its operations)
5 Quick sort method.

6 Merge sort method.

7 SHELL sort method

Program to perform :
i) Creating a Binary Tree of
8 integers
ii) Traversing the above
binary tree in preorder,
inorder and postorder.
9 Program to perform :
i) Creating a AVL Tree
ii) insertion
iii) deletion
iv) Traversing the above AVL
tree in preorder, inorder
and postorder.
Program to perform :
10 i) Creating a SplayTree
ii) Traverse
Program to perform :
11 i) Creating a B-Tree of integers
ii) insertion
iii) deletion
12 Kruskal’s algorithm

13 Traversing algorithms.

14 Finding the minimal spanning tree

of a graph using the Prim’s
algorithm.
15 Finding shortest path using
Bellman Ford's Algorithm.
Exp no. 1 Singly linked list

Date:

AIM :

To write a python program to perform the following operations on a

heterogeneous singly linked list. i) Creation ii) Insertion iii) Deletion iv)
Traversal

ALGORITHM:

STEP 1: Check if the script is being run as the main program (if __name__
== "__main__":).

STEP 2: Create an instance of the LinkedList class called linked_list.

STEP 3: Insert elements of different data types into the linked list using the
insert method.

STEP 4: Print the initial linked list using the traverse method.

STEP 5: Delete a node from the linked list with the value 3.14 using the delete
method.

STEP 6: Print the modified linked list after the deletion.

1
PROGRAM:

class Node:

def __init__(self, data):

self.data = data

self.next = None

class LinkedList:

def __init__(self):

self.head = None

def insert(self, data):

new_node = Node(data)

new_node.next = self.head

self.head = new_node

def delete(self, target_data):

current = self.head

prev = None

while current:

if current.data == target_data:

if prev is None:

self.head = current.next

else:

prev.next = current.next

return

prev = current

current = current.next

def traverse(self):

2
 current = self.head

while current:

print(current.data, end=' ')

current = current.next

print()

if __name__ == "__main__":

linked_list = LinkedList()

linked_list.insert(42)

linked_list.insert(3.14)

linked_list.insert("Hello, World!")

print("Linked List: ", end='')

linked_list.traverse()

linked_list.delete(3.14)

print("Modified List: ", end='')

linked_list.traverse()

OUTPUT:

Linked List: Hello, World! 3.14 42

Modified List: Hello, World! 42

RESULT:

Thus the above python program is executed successfully.

3
Exp no.2 Doubly linked list

Date:

AIM:

To write a python program to perform the following operations on a

heterogeneous doubly linked list. i) Creation ii) Insertion iii) Deletion iv)
Traversal in both ways.

ALGORITHM:

STEP 1: Check if the script is being run as the main program (if __name__ ==
"__main__":).

STEP 2: Create an instance of the HeterogeneousDoublyLinkedList class called

linked_list.

STEP 3: Insert elements of different data types into the linked list using the
insert method.

STEP 4: Print the linked list in both forward and backward directions using
the traverse_backward methods

STEP 5: Delete a node with the value "Hello" from the linked list using the
delete method.

STEP 6: Print the modified linked list in both directions again.

4
PROGRAM:

class Node:

def __init__(self, data):

self.data = data

self.prev = None

self.next = None

class HeterogeneousDoublyLinkedList:

def __init__(self):

self.head = None

def insert(self, data):

new_node = Node(data)

if not self.head:

self.head = new_node

else:

current = self.head

while current.next:

current = current.next

current.next = new_node

new_node.prev = current

def delete(self, data):

if not self.head:

return

if self.head.data == data:

self.head = self.head.next

if self.head:

5
 self.head.prev = None

return

current = self.head

while current:

if current.data == data:

current.prev.next = current.next

if current.next:

current.next.prev = current.prev

return

current = current.next

def traverse_forward(self):

current = self.head

while current:

print(current.data, end=" <-> ")

current = current.next

print("None")

def traverse_backward(self):

current = self.head

if not current:

print("None")

return

while current.next:

current = current.next

while current:

print(current.data, end=" <-> ")

6
 current = current.prev

print("None")

if __name__ == "__main__":

linked_list = HeterogeneousDoublyLinkedList()

linked_list.insert(5)

linked_list.insert("Hello")

linked_list.insert(3.14)

linked_list.insert(True)

linked_list.traverse_forward()

linked_list.traverse_backward()

linked_list.delete("Hello")

linked_list.traverse_forward()

OUTPUT:

5 <-> Hello <-> 3.14 <-> True <-> None

True <-> 3.14 <-> Hello <-> 5 <-> None

5 <-> 3.14 <-> True <-> None

RESULT:

Thus the above python program is executed successfully.

7
Exp no. 3 Stack Operations

Date.

AIM:

To create a program that implements using python generic class, the stack
(its operations).

ALGORITHM:

STEP 1:Create an instance of the Stack class called stack.

STEP 2:Push various elements of different types (integer, string, float) onto the
stack.

STEP 3:Check if the stack is empty using stack.is_empty().

STEP 4:Pop items from the stack using stack.pop() and print the removed
items.

STEP 5:Peek at the top element of the stack using stack.peek(), and print the
top item.

STEP 6:Check the size of the stack using stack.size() and print the size.

8
PROGRAM:

class Stack:

def __init__(self):

self.items = []

def is_empty(self) -> bool:

return len(self.items) == 0

def push(self, item):

self.items.append(item)

def pop(self):

if not self.is_empty():

return self.items.pop()

else:

raise IndexError("Stack is empty, cannot pop an item.")

def peek(self):

if not self.is_empty():

return self.items[-1]

else:

raise IndexError("Stack is empty, cannot peek.")

def size(self) -> int:

return len(self.items)

if __name__ == "__main__":

stack = Stack()

stack.push(1)

stack.push("Hello")

stack.push(3.14)

9
 print("Is the stack empty?", stack.is_empty())

print("Popped item:", stack.pop())

print("Popped item:", stack.pop())

print("Top item (peek):", stack.peek())

print("Size of the stack:", stack.size())

OUTPUT:

Is the stack empty? False

Popped item: 3.14

Popped item: Hello

Top item (peek): 1

Size of the stack: 1

RESULT:

Thus the above python program is executed successfully.

10
Exp no.4 Queue Operations

Date:

AIM:

To create a program that implements using python generic class, the queue
(its operations).

ALGORITHM:

STEP 1: Create an instance of the generic queue class Queue for integers
(Queue[int]).

STEP 2: Enqueue several elements (1, 2, 3) into the queue.

STEP 3: Check if the queue is empty using is_empty and print the result.

STEP 4: Dequeue elements from the queue using dequeue and print the
removed elements.

STEP 5: Get the front element using front and print the value.

STEP 6: Determine the size of the queue using size and print the size.

11
PROGRAM:

from typing import TypeVar, Generic, List

T = TypeVar("T")

class Queue(Generic[T]):

def __init__(self):

self.items: List[T] = []

def is_empty(self) -> bool:

return len(self.items) == 0

def enqueue(self, item: T) -> None:

self.items.append(item)

def dequeue(self) -> T:

if not self.is_empty():

return self.items.pop(0)

else:

raise IndexError("Queue is empty, cannot dequeue an item.")

def front(self) -> T:

if not self.is_empty():

return self.items[0]

else:

raise IndexError("Queue is empty, cannot get the front item.")

def size(self) -> int:

return len(self.items)

if __name__ == "__main__":

queue = Queue[int]()

queue.enqueue(1)

12
 queue.enqueue(2)

queue.enqueue(3)

print("Is the queue empty?", queue.is_empty())

print("Dequeued item:", queue.dequeue())

print("Dequeued item:", queue.dequeue())

print("Front item:", queue.front())

print("Size of the queue:", queue.size())

OUTPUT:

Is the queue empty? False

Dequeued item: 1

Dequeued item: 2

Front item: 3

Size of the queue: 1

RESULT:

Thus the above python program is executed successfully.

13
Exp no. 5 Quick sort method

Date:

AIM:

To create a python program that implements the Quick sort method.

ALGORTHIM:

STEP 1:Define a quick_sort function that takes an unsorted list arr as its
input.

STEP 2:Check if the length of the list arr is less than or equal to 1. If so, the
list is considered s sorted, and it is returned as is.

STEP 3: Otherwise, select a pivot element. In this implementation, the pivot is

chosen as the middle element of the list (index len(arr) // 2).

STEP 4:Recursively apply the quick_sort function to the left and right sublists
and concatenate them with the middle sublist to form the final sorted list.

STEP 5:Print the unsorted list and the sorted list to demonstrate the sorting
process.

14
PROGRAM:

def quick_sort(arr):

if len(arr) <= 1:

return arr

pivot = arr[len(arr) // 2]

left = [x for x in arr if x < pivot]

middle = [x for x in arr if x == pivot]

right = [x for x in arr if x > pivot]

return quick_sort(left) + middle + quick_sort(right)

if __name__ == "__main__":

unsorted_list = [3, 6, 8, 10, 1, 2, 1]

sorted_list = quick_sort(unsorted_list)

print("Unsorted list:", unsorted_list)

print("Sorted list:", sorted_list)

OUTPUT:

Unsorted list: [3, 6, 8, 10, 1, 2, 1]

Sorted list: [1, 1, 2, 3, 6, 8, 10]

RESULT:

Thus the above python program is executed successfully.

15
Exp no. 6 Merge sort

Date:

AIM:

To create a python program that implement the Merge sort method.

ALGORITHM:

STEP 1:The merge_sort function takes an array arr as input.

STEP 2:If the length of the array is less than or equal to 1, it's already
considered sorted, so the function returns the array as is.

STEP 3:Otherwise, it splits the array into two halves, left_half and right_half,
and recursively applies merge_sort to both halves.

STEP 4:The sorted halves are merged back together using the merge function.

STEP 5:The merge function takes two sorted arrays, left and right, and merges
them into a single sorted array, result.

STEP 6:In the example usage section, an unsorted list is defined, and the
merge_sort function is called to sort it.

STEP 7:The sorted list is printed along with the unsorted list to demonstrate
the sorting process.

16
PROGRAM:

def merge_sort(arr):

if len(arr) <= 1:

return arr

mid = len(arr) // 2

left_half = arr[:mid]

right_half = arr[mid:]

left_half = merge_sort(left_half)

right_half = merge_sort(right_half)

return merge(left_half, right_half)

def merge(left, right):

merged = []

left_index, right_index = 0, 0

while left_index < len(left) and right_index < len(right):

if left[left_index] < right[right_index]:

merged.append(left[left_index])

left_index += 1

else:

merged.append(right[right_index])

right_index += 1

merged.extend(left[left_index:])

merged.extend(right[right_index:])

return merged

if __name__ == "__main__":

unsorted_list = [3, 6, 8, 10, 1, 2, 1]

17
 sorted_list = merge_sort(unsorted_list)

print("Unsorted list:", unsorted_list)

print("Sorted list:", sorted_list)

OUTPUT:

Unsorted list: [3, 6, 8, 10, 1, 2, 1]

Sorted list: [1, 1, 2, 3, 6, 8, 10]

RESULT:

Thus the above python program is executed successfully.

18
Exp No. 7 Shell sort method

Date:

AIM:

To create a program that implement the SHELL sort method.

ALGORITHM:

STEP 1:The program defines a shell_sort function that takes an unsorted list
as input.

STEP 2:It initializes the gap to half of the list size (n // 2).

STEP 3:The program uses a while loop to iterate through the sorting process
until the gap becomes 0.

STEP 4:Within the loop, it performs an insertion sort on sublists created by

considering every gap-th element in the list.

STEP 5:The insertion sort algorithm is implemented within the inner while
loop.

STEP 6:The gap is reduced by half in each iteration until it becomes 0.

19
PROGRAM:

def shell_sort(arr):

n = len(arr)

gap = n // 2

while gap > 0:

for i in range(gap, n):

temp = arr[i]

j=i

while j >= gap and arr[j - gap] > temp:

arr[j] = arr[j - gap]

j -= gap

arr[j] = temp

gap //= 2

if __name__ == "__main__":

unsorted_list = [3, 6, 8, 10, 1, 2, 1]

print("Unsorted list:", unsorted_list)

shell_sort(unsorted_list)

print("Sorted list:", unsorted_list)

20
OUTPUT:

Unsorted list: [3, 6, 8, 10, 1, 2, 1]

Sorted list: [1, 1, 2, 3, 6, 8, 10]

RESULT:

Thus the above python program is executed successfully.

21
Exp no. 8 Creating a Binary Tree

Date:

AIM:

To create a python program to perform the following: i) Creating a Binary Tree

of integers ii) Traversing the above binary tree in preorder, inorder and
postorder.

ALGORITHM:

STEP 1:Define a TreeNode class with attributes for the node's value, left child,
and right child.

STEP 2:Create the create_binary_tree function to construct a sample binary

tree with integer values.

STEP 3:Implement three traversal functions:

 preorder_traversal: Performs a preorder traversal (Root -> Left -> Right)

and prints the value of each node.
 inorder_traversal: Performs an inorder traversal (Left -> Root -> Right)
and prints the value of each node.
 postorder_traversal: Performs a postorder traversal (Left -> Right -> Root)
and prints the value of each node.

STEP 4:In the if __name__ == '__main__': block, create the binary tree using
create_binary_tree and call each of the traversal functions to print the values in
the specified order.

22
PROGRAM:

class TreeNode:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def create_binary_tree():

root = TreeNode(1)

root.left = TreeNode(2)

root.right = TreeNode(3)

root.left.left = TreeNode(4)

root.left.right = TreeNode(5)

root.right.left = TreeNode(6)

root.right.right = TreeNode(7)

return root

def preorder_traversal(node):

if node:

print(node.value, end=' ')

preorder_traversal(node.left)

preorder_traversal(node.right)

def inorder_traversal(node):

if node:

inorder_traversal(node.left)

print(node.value, end=' ')

inorder_traversal(node.right)

23
def postorder_traversal(node):

if node:

postorder_traversal(node.left)

postorder_traversal(node.right)

print(node.value, end=' ')

if __name__ == '__main__':

root = create_binary_tree()

print("Preorder Traversal:")

preorder_traversal(root)

print("\nInorder Traversal:")

inorder_traversal(root)

print("\nPostorder Traversal:")

postorder_traversal(root)

24
OUTPUT:

Preorder Traversal:

1245367

Inorder Traversal:

4251637

Postorder Traversal:

4526731

RESULT:

Thus the above python program is executed successfully.

25
Exp no. 9 Creating a AVL Tree

Date:

AIM:

To create a program to perform the following: i) Creating a AVL Tree ii)

insertioniii)deletion iv) Traversing the above AVL tree in preorder, inorder and
postorder.

ALGORITHM:

STEP 1:Define a class AVLNode representing nodes in the AVL tree. Each node
stores a key (integer), left and right child nodes, and the height of the subtree
rooted at that node.

STEP 2:Implement helper functions for the AVL tree:

STEP 3:Implement the insert_avl(root, key) function to insert a new node with
the specified key into the AVL tree.

STEP 4:Define three traversal functions: preorder_traversal, inorder_traversal,

and postorder_traversal, to print the nodes in pre-order, in-order, and post-
order, respectively.

26
PROGRAM:

class AVLNode:

def __init__(self, key):

self.key = key

self.left = None

self.right = None

self.height = 1

def height(node):

if not node:

return 0

return node.height

def balance_factor(node):

if not node:

return 0

return height(node.left) - height(node.right)

def update_height(node):

if not node:

return

node.height = max(height(node.left), height(node.right)) + 1

def rotate_right(node):

new_root = node.left

node.left = new_root.right

new_root.right = node

update_height(node)

update_height(new_root)

27
 return new_root

def rotate_left(node):

new_root = node.right

node.right = new_root.left

new_root.left = node

update_height(node)

update_height(new_root)

return new_root

def insert_avl(root, key):

if not root:

return AVLNode(key)

if key < root.key:

root.left = insert_avl(root.left, key)

elif key > root.key:

root.right = insert_avl(root.right, key)

else:

return root

update_height(root)

balance = balance_factor(root)

if balance > 1:

if key < root.left.key:

return rotate_right(root)

else:

root.left = rotate_left(root.left)

return rotate_right(root)

28
 if balance < -1:

if key > root.right.key:

return rotate_left(root)

else:

root.right = rotate_right(root.right)

return rotate_left(root)

return root

def preorder_traversal(node):

if node:

print(node.key, end=' ')

preorder_traversal(node.left)

preorder_traversal(node.right)

def inorder_traversal(node):

if node:

inorder_traversal(node.left)

print(node.key, end=' ')

inorder_traversal(node.right)

def postorder_traversal(node):

if node:

postorder_traversal(node.left)

postorder_traversal(node.right)

print(node.key, end=' ')

if __name__ == '__main__':

root = None

keys = [10, 20, 30, 40, 50, 25]

29
 for key in keys:

root = insert_avl(root, key)

print("Preorder Traversal:")

preorder_traversal(root)

print("\nInorder Traversal:")

inorder_traversal(root)

print("\nPostorder Traversal:")

postorder_traversal(root)

OUTPUT:

Preorder Traversal:

30 20 10 25 40 50

Inorder Traversal:

10 20 25 30 40 50

Postorder Traversal:

10 25 20 50 40 30

RESULT:

Thus the above python program is executed successfully.

30
Exp No. 10 Creating a SplayTree

Date:

Aim:

To create a python program that uses functions to perform the following: i)

Creating a SplayTree ii) traverse.

ALGORITHM:

STEP 1:The SplayTreeNode class represents a node in the Splay Tree. Each
node contains a key and references to its left and right children.

STEP 2:The SplayTree class initializes an empty tree with a root node set to
None.

STEP 3:The splay method is used to perform the splaying operation.

STEP 4:The _splay method is a recursive function that splays the tree.

STEP 5:The rotate_right and rotate_left methods are used to perform the right
and left rotations, respectively, for splaying.

STEP 6:The insert method allows inserting a key into the Splay Tree.

STEP 7:The _insert method performs insertion and splaying at the same time.
It ensures that the newly inserted key becomes the root after insertion.

STEP 8:The in_order_traversal method is used to perform an in-order traversal

of the Splay Tree. It returns the keys in sorted order.

31
PROGRAM:

class SplayTreeNode:

def __init__(self, key):

self.key = key

self.left = None

self.right = None

class SplayTree:

def __init__(self):

self.root = None

def splay(self, key):

self.root = self._splay(self.root, key)

def _splay(self, node, key):

if node is None or node.key == key:

return node

if key < node.key:

if node.left is None:

return node

if key < node.left.key:

node.left.left = self._splay(node.left.left, key)

node = self.rotate_right(node)

elif key > node.left.key:

node.left.right = self._splay(node.left.right, key)

if node.left.right is not None:

node.left = self.rotate_left(node.left)

32
 return node if node.left is None else self.rotate_right(node)

if key > node.key:

if node.right is None:

return node

if key < node.right.key:

node.right.left = self._splay(node.right.left, key)

if node.right.left is not None:

node.right = self.rotate_right(node.right)

elif key > node.right.key:

node.right.right = self._splay(node.right.right, key)

node = self.rotate_left(node)

return node if node.right is None else self.rotate_left(node)

def rotate_right(self, node):

new_root = node.left

node.left = new_root.right

new_root.right = node

return new_root

def rotate_left(self, node):

new_root = node.right

node.right = new_root.left

new_root.left = node

return new_root

def insert(self, key):

if self.root is None:

self.root = SplayTreeNode(key)

33
 else:

self.root = self._insert(self.root, key)

def _insert(self, node, key):

if node is None:

return SplayTreeNode(key)

self.splay(key)

if key < self.root.key:

new_node = SplayTreeNode(key)

new_node.left = self.root.left

new_node.right = self.root

self.root.left = None

self.root = new_node

elif key > self.root.key:

new_node = SplayTreeNode(key)

new_node.right = self.root.right

new_node.left = self.root

self.root.right = None

self.root = new_node

return self.root

def in_order_traversal(self):

return self._in_order_traversal(self.root)

def _in_order_traversal(self, node):

if node is None:

return []

34
 return self._in_order_traversal(node.left) + [node.key] +
self._in_order_traversal(node.right)

if __name__ == "__main__":

splay_tree = SplayTree()

keys = [50, 30, 70, 20, 40, 60, 80]

for key in keys:

splay_tree.insert(key)

print("In-order Traversal of the Splay Tree:")

result = splay_tree.in_order_traversal()

print(result)

OUTPUT:

In-order Traversal of the Splay Tree:

[20, 30, 40, 50, 60, 70, 80]

RESULT:

Thus the above python program is executed successfully.

35
Exp. No. 11 Creating a B-Tree of integers

Date:

Aim:

To create a program to perform the following: i) Creating a B-Tree of integers ii)

insertion iii)deletion

Algorithm:

STEP 1:Import the FastRBTree class from the bintrees library

[pip install bintrees]
STEP 2:Create an empty B-Tree by initializing an instance of FastRBTree.

STEP 3:Define a function insert_element for inserting key-value pairs into the
B-Tree.

STEP 4: Define a function delete_element for deleting elements from the B-

Tree.

STEP 5: Insert three elements into the B-Tree using the insert_element
Function.

STEP 6: Print the contents of the B-Tree after insertions.

STEP 7: Delete an element with a key of 3 from the B-Tree using the
delete_element function.

STEP 8: Print the contents of the B-Tree after deletion.

36
PROGRAM:

from bintrees import FastRBTree

b_tree = FastRBTree()

def insert_element(b_tree, key, value):

b_tree[key] = value

def delete_element(b_tree, key):

if key in b_tree:

del b_tree[key]

else:

print(f"Key {key} not found in the B-Tree.")

insert_element(b_tree, 5, "Value for 5")

insert_element(b_tree, 3, "Value for 3")

insert_element(b_tree, 7, "Value for 7")

print("B-Tree contents after insertions:")

for key, value in b_tree.items():

print(f"Key: {key}, Value: {value}")

delete_element(b_tree, 3)

print("\nB-Tree contents after deletion:")

for key, value in b_tree.items():

print(f"Key: {key}, Value: {value}")

37
OUTPUT:

B-Tree contents after insertions:

Key: 3, Value: Value for 3

Key: 5, Value: Value for 5

Key: 7, Value: Value for 7

B-Tree contents after deletion:

Key: 5, Value: Value for 5

Key: 7, Value: Value for 7

RESULT:

Thus the above python program is executed successfully.

38
Exp. No. 12 Kruskal’s algorithm

Date:

Aim:

To create a python program that implements Kruskal’s algorithm using a

disjoint set datastructure. The program takes as input a file (data.txt), in which
each line either represents a vertex or an edge. For the edge lines, the first
integer on that line representing the starting vertex, the second the ending
vertex, and the third the weight of the edge. Use this file to construct, line by
line, the graph upon which Kruskal’s algorithm will be run (doNOT hardcode
this graph!).

ALGORITHM:

STEP 1: Read the graph information from a text file named "data.txt".

STEP 2: Each line in the file should represent either a vertex or an edge.

STEP 3: Lines representing edges should contain three integers: the starting
vertex, the ending vertex, and the weight of the edge.

STEP 4: Lines representing vertices should contain a single integer.

STEP 5: Extract and parse the data from the file to build the graph's edge list.

STEP 6: After running Kruskal's algorithm, the program prints the edges of the
minimum spanning tree along with their weights.

39
PROGRAM:
class DisjointSet:
def __init__(self, vertices):
self.parent = {vertex: vertex for vertex in vertices}
self.rank = {vertex: 0 for vertex in vertices}
def find(self, vertex):
if self.parent[vertex] != vertex:
self.parent[vertex] = self.find(self.parent[vertex])
return self.parent[vertex]
def union(self, vertex1, vertex2):
root1 = self.find(vertex1)
root2 = self.find(vertex2)
if root1 != root2:
if self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
elif self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
else:
self.parent[root2] = root1
self.rank[root1] += 1
def kruskal(graph):
edges = sorted(graph, key=lambda x: x[2])
minimum_spanning_tree = []
disjoint_set = DisjointSet(set(v for edge in edges for v in edge[:2]))

for edge in edges:

start_vertex, end_vertex, weight = edge
if disjoint_set.find(start_vertex) != disjoint_set.find(end_vertex):
minimum_spanning_tree.append(edge)
disjoint_set.union(start_vertex, end_vertex)
return minimum_spanning_tree
graph = []
with open("data.txt", "r") as file:
for line in file:
tokens = line.split()
if len(tokens) == 3:
start_vertex, end_vertex, weight = map(int, tokens)
graph.append((start_vertex, end_vertex, weight))
minimum_spanning_tree = kruskal(graph)
for edge in minimum_spanning_tree:
print(f"{edge[0]} -- {edge[1]} : {edge[2]}")

40
OUTPUT:

3 -- 4 : 5

2 -- 4 : 7

1 -- 2 : 10

RESULT:

Thus the above python program is executed successfully.

41
Exp. No. 13 Traversing algorithms

Date:

Aim:

To create a python program to simulate various graph traversing algorithms

ALGORITHM:

STEP 1: The Graph class is initialized as an empty graph using a defaultdict to

store the adjacency list representation of the graph.

STEP 2: The add_edge method is used to add edges to the graph.

STEP 3: It takes two vertices u and v and an optional weight w (default is 1)

and adds these edges to the graph's adjacency list.

STEP 4:The dfs method performs a Depth-First Search starting from a given
vertex (start).

STEP 5: The bfs method performs a Breadth-First Search starting from a given
vertex (start).

STEP 6: The dijkstra method finds the shortest distances from a given starting
vertex (start) to all other vertices using Dijkstra's Algorithm.

STEP 7: Create a Graph object (g).

STEP 8: Add edges to the graph using the add_edge method.

STEP 9: Use the dfs, bfs, and dijkstra methods to perform the respective graph
traversals.

42
PROGRAM:

from collections import defaultdict

import heapq

class Graph:

def __init__(self):

self.graph = defaultdict(list)

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

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

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

def dfs(self, start):

visited = set()

stack = [start]

while stack:

vertex = stack.pop()

if vertex not in visited:

print(vertex, end=' ')

visited.add(vertex)

stack.extend(v for v, _ in self.graph[vertex] if v not in visited)

def bfs(self, start):

visited = set()

queue = [start]

while queue:

vertex = queue.pop(0)

43
 if vertex not in visited:

print(vertex, end=' ')

visited.add(vertex)

queue.extend(v for v, _ in self.graph[vertex] if v not in visited)

def dijkstra(self, start):

visited = set()

dist = {node: float('inf') for node in self.graph}

dist[start] = 0

heap = [(0, start)]

while heap:

(current_dist, current_node) = heapq.heappop(heap)

if current_node in visited:

continue

visited.add(current_node)

for neighbor, weight in self.graph[current_node]:

distance = current_dist + weight

if distance < dist[neighbor]:

dist[neighbor] = distance

heapq.heappush(heap, (distance, neighbor))

print("Shortest distances from", start)

for node, distance in dist.items():

print(node, ":", distance)

g = Graph()

g.add_edge(1, 2, 1)

g.add_edge(1, 3, 3)

44
g.add_edge(2, 4, 2)

g.add_edge(2, 5, 4)

g.add_edge(3, 6, 2)

print("DFS:")

g.dfs(1)

print("\nBFS:")

g.bfs(1)

print("\nDijkstra's Algorithm:")

g.dijkstra(1)

OUTPUT:

DFS:

136254

BFS:

123456

Dijkstra's Algorithm:

Shortest distances from 1

1:0

2:1

3:3

4:3

5:5

6:5

RESULT:

Thus the above python program is executed successfully.

45
Exp. No. 14 Prim’s algorithm

Date.

Aim:

To write a python program to find the minimal spanning tree of a graph using
the Prim’s algorithm.

ALGORITHM:

STEP 1:Create a Graph instance (g) and specify the number of vertices.

STEP 2:Populate the graph by providing the adjacency matrix (in the g.graph
attribute).

STEP 3:Call the prim_mst method to find the Minimum Spanning Tree.

STEP 4:The program will print the MST's edges and their weights.

46
PROGRAM:

import sys

class Graph:

def __init__(self, vertices):

self.V = vertices

self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]

def min_key(self, key, mst_set):

min_value = sys.maxsize

min_index = None

for v in range(self.V):

if key[v] < min_value and not mst_set[v]:

min_value = key[v]

min_index = v

return min_index

def prim_mst(self):

parent = [None] * self.V

key = [sys.maxsize] * self.V

key[0] = 0

mst_set = [False] * self.V

parent[0] = -1

for _ in range(self.V - 1):

u = self.min_key(key, mst_set)

mst_set[u] = True

for v in range(self.V):

47
 if self.graph[u][v] and not mst_set[v] and key[v] > self.graph[u][v]:

key[v] = self.graph[u][v]

parent[v] = u

print("Edge Weight")

for i in range(1, self.V):

print(parent[i], "-", i, " ", self.graph[i][parent[i]])

g = Graph(5)

g.graph = [

[0, 2, 0, 6, 0],

[2, 0, 3, 8, 5],

[0, 3, 0, 0, 7],

[6, 8, 0, 0, 9],

[0, 5, 7, 9, 0]

g.prim_mst()

48
OUTPUT:

Edge Weight

0-1 2

1-2 3

0-3 6

1-4 5

RESULT:

Thus the above python program is executed successfully.

49
Exp. No. 15 Bellman Ford's Algorithm

Date:

Aim:

To create a program to find shortest path using Bellman Ford's Algorithm.

Algorithm:

STEP 1: Create a Graph instance (g) and specify the number of vertices.

STEP 2: Add edges to the graph using the add_edge method.

STEP 3: Call the bellman_ford method with the source vertex from which you
want to find the shortest paths.

STEP 4: The program will print the shortest distances from the source vertex
to all other vertices or indicate if there's a negative weight cycle in the graph.

50
PROGRAM:

class Graph:

def __init__(self, vertices):

self.V = vertices

self.edges = []

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

self.edges.append((u, v, w))

def bellman_ford(self, source):

dist = [float('inf')] * self.V

dist[source] = 0

for _ in range(self.V - 1):

for u, v, w in self.edges:

if dist[u] != float('inf') and dist[u] + w < dist[v]:

dist[v] = dist[u] + w

for u, v, w in self.edges:

if dist[u] != float('inf') and dist[u] + w < dist[v]:

print("Graph contains a negative weight cycle")

return

print("Vertex \t Shortest Distance from Source")

for i in range(self.V):

print(i, "\t", dist[i])

g = Graph(5)

g.add_edge(0, 1, -1)

g.add_edge(0, 2, 4)

g.add_edge(1, 2, 3)

51
g.add_edge(1, 3, 2)

g.add_edge(1, 4, 2)

g.add_edge(3, 2, 5)

g.add_edge(3, 1, 1)

g.add_edge(4, 3, -3)

source_vertex = 0

g.bellman_ford(source_vertex)

OUTPUT:

Vertex Shortest Distance from Source

0 0

1 -1

2 2

3 -2

4 1

RESULT:

Thus the above python program is executed successfully.

52
53
1
1