Simple ADT as Python Classes Program:

class ListADT:
def __init__(self):
self.l = []

def insert_at_end(self, a):

[Link](a)

def insert_at_beginning(self, a):

[Link](0, a)

def insert_at_middle(self, ind, a):

if 0 <= ind <= len(self.l): # check valid index
[Link](ind, a)
else:
print("Invalid index!")

def remove(self, b):

if b in self.l:
[Link](b)
else:
print("Element not found!")

def display(self):
return self.l

print("Implementation of List using Python Class")

obj = ListADT()

while True:
print("\nMENU")
print("1. INSERT AT BEGINNING")
print("2. INSERT AT MIDDLE")
print("3. INSERT AT END")
 print("4. DELETE AN ELEMENT")
print("5. DISPLAY THE LIST")
print("6. EXIT")

try:
choice = int(input("Enter choice: "))
except ValueError:
print("Invalid input! Please enter a number.")
continue

if choice == 1:
n = int(input("Enter element to insert: "))
obj.insert_at_beginning(n)

elif choice == 2:
n = int(input("Enter element to insert: "))
pos = int(input("Enter index position: "))
obj.insert_at_middle(pos, n)

elif choice == 3:
n = int(input("Enter element to append: "))
obj.insert_at_end(n)

elif choice == 4:
n = int(input("Enter element to remove: "))
[Link](n)

elif choice == 5:
print("List is:", [Link]())

elif choice == 6:
print("PROGRAM EXIT")
break
else:
print("Invalid choice! Try again.")
OUTPUT:

Implementation of List using Python Class

MENU
1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 1
Enter element to insert: 20

MENU
1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 1
Enter element to insert: 50

MENU
1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 5
List is: [50, 20]
MENU

1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 5
List is: [50, 20]

MENU

1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 2
Enter element to insert: 45
Enter index position: 2

MENU

1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 5
List is: [50, 20, 45]
MENU

1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 3
Enter element to append: 70

MENU

1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 4
Enter element to remove: 20

MENU

1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 5
List is: [50, 45, 70]
MENU
1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 5
List is: [50, 45, 70]

MENU
1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 5
List is: [50, 45, 70]

MENU
1. INSERT AT BEGINNING
2. INSERT AT MIDDLE
3. INSERT AT END
4. DELETE AN ELEMENT
5. DISPLAY THE LIST
6. EXIT
Enter choice: 6
PROGRAM EXIT
Traversal of a Linked List

PROGRAM:

class Node:

def __init__(self, data):

[Link] = data

[Link] = None

def traverseAndPrint(head):

currentNode = head

while currentNode:

print([Link], end=" -> ")

currentNode = [Link]

print("null")

# Create nodes

node1 = Node(7)

node2 = Node(11)

node3 = Node(3)

node4 = Node(2)

node5 = Node(9)
# Link nodes

[Link] = node2

[Link] = node3

[Link] = node4

[Link] = node5

# Traverse and print the linked list

traverseAndPrint(node1)

OUTPUT:

7 -> 11 -> 3 -> 2 -> 9 -> null

Find The Lowest Value in a Linked List

PROGRAM:

class Node:

def __init__(self, data):

[Link] = data

[Link] = None

def findLowestValue(head):

minValue = [Link]

currentNode = [Link]

while currentNode:

if [Link] < minValue:

minValue = [Link]

currentNode = [Link]

return minValue

# Create nodes

node1 = Node(7)

node2 = Node(11)

node3 = Node(3)
node4 = Node(2)

node5 = Node(9)

# Link nodes

[Link] = node2

[Link] = node3

[Link] = node4

[Link] = node5

# Find and print lowest value

print("The lowest value in the linked list is:", findLowestValue(node1))

OUTPUT:

The lowest value in the linked list is: 2

Delete a Node in a Linked List

PROGRAM

class Node:

def __init__(self, data):

[Link] = data

[Link] = None

def traverseAndPrint(head):

currentNode = head

while currentNode:

print([Link], end=" -> ")

currentNode = [Link]

print("null")

def deleteSpecificNode(head, nodeToDelete):

# Case 1: node to delete is the head

if head == nodeToDelete:

return [Link]

currentNode = head
 # Traverse until the node before the one to delete

while [Link] and [Link] != nodeToDelete:

currentNode = [Link]

# Case 2: node not found

if [Link] is None:

return head

# Case 3: node found, skip it

[Link] = [Link]

return head

# Create nodes

node1 = Node(7)

node2 = Node(11)

node3 = Node(3)

node4 = Node(2)

node5 = Node(9)

# Link nodes
[Link] = node2

[Link] = node3

[Link] = node4

[Link] = node5

print("Before deletion:")

traverseAndPrint(node1)

# Delete node4 (which holds 2)

node1 = deleteSpecificNode(node1, node4)

print("\nAfter deletion:")

traverseAndPrint(node1)

OUTPUT:

Before deletion:
7 -> 11 -> 3 -> 2 -> 9 -> null

After deletion:
7 -> 11 -> 3 -> 9 -> null
Insert a Node in a Linked List.

PROGRAM:

class Node:

def __init__(self, data):

[Link] = data

[Link] = None

def traverseAndPrint(head):

currentNode = head

while currentNode:

print([Link], end=" -> ")

currentNode = [Link]

print("null")

def insertNodeAtPosition(head, newNode, position):

# Case 1: Insert at the head

if position == 1:

[Link] = head

return newNode
 currentNode = head

# Move to the node just before the desired position

for _ in range(position - 2):

if currentNode is None:

break

currentNode = [Link]

# Case 2: If position is beyond length, insert at end

if currentNode is None:

return head

# Insert new node

[Link] = [Link]

[Link] = newNode

return head

# Create nodes

node1 = Node(7)

node2 = Node(3)

node3 = Node(2)
node4 = Node(9)

# Link nodes

[Link] = node2

[Link] = node3

[Link] = node4

print("Original list:")

traverseAndPrint(node1)

# Insert a new node with value 97 at position 2

newNode = Node(97)

node1 = insertNodeAtPosition(node1, newNode, 2)

print("\nAfter insertion:")

traverseAndPrint(node1)

OUTPUT:

Original list:
7 -> 3 -> 2 -> 9 -> null

After insertion:
7 -> 97 -> 3 -> 2 -> 9 -> null
DOUBLY LINKED LIST:

Insertion at beginning:

PROGRAM:

class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

class DoublyLinkedList:
def __init__(self):
[Link] = None

# Insertion at the beginning

def insert_at_beginning(self, data):
new_node = Node(data)
if [Link] is None:
[Link] = new_node
else:
new_node.next = [Link]
[Link] = new_node
[Link] = new_node

# Display the list

def display(self):
temp = [Link]
while temp:
print([Link], end=" <-> ")
temp = [Link]
print("None")

# Example usage
dll = DoublyLinkedList()
dll.insert_at_beginning(6)
dll.insert_at_beginning(8)
dll.insert_at_beginning(7)

print("Doubly Linked List after insertions at beginning:")

[Link]()

OUTPUT:

Doubly Linked List after insertions at beginning:

7 <-> 8 <-> 6 <-> None
Python Code(Insertion at Nth Position)

class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

class DoublyLinkedList:
def __init__(self):
[Link] = None

def insert_at_position(self, data, position):

new_node = Node(data)

# Case 1: Insert at beginning

if position == 1:
if [Link]:
new_node.next = [Link]
[Link] = new_node
[Link] = new_node
return

temp = [Link]
# Move to the node just before the desired position
for _ in range(position - 2):
if temp is None:
print("Position out of range")
return
temp = [Link]

if temp is None:
print("Position out of range")
return
 # Insert in middle or at end
new_node.next = [Link]
new_node.prev = temp
if [Link]:
[Link] = new_node
[Link] = new_node

def display(self):
temp = [Link]
while temp:
print([Link], end=" <-> ")
temp = [Link]
print("None")

# Example usage
dll = DoublyLinkedList()
dll.insert_at_position(7, 1) # Insert at position 1
dll.insert_at_position(8, 2) # Insert at position 2
dll.insert_at_position(6, 2) # Insert at position 2
[Link]()

OUTPUT:

7 <-> 6 <-> 8 <-> None

Python Code(Insertion at End)

PROGRAM:

class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

class DoublyLinkedList:
def __init__(self):
[Link] = None

def insert_at_end(self, data):

new_node = Node(data)
if [Link] is None:
[Link] = new_node
else:
temp = [Link]
while [Link]:
temp = [Link]
[Link] = new_node
new_node.prev = temp

def display(self):
temp = [Link]
while temp:
print([Link], end=" <-> ")
temp = [Link]
print("None")

# Example usage
dll = DoublyLinkedList()
dll.insert_at_end(7)
dll.insert_at_end(8)
dll.insert_at_end(6)
dll.insert_at_end(9)

print("Doubly Linked List after insertions at end:")

[Link]()

OUTPUT:

7 <-> 8 <-> 6 <-> 9 <-> None

CIRCULAR LINKED LIST:

Program:

class Node:

def __init__(self, data):

[Link] = data

[Link] = None

[Link] = None

# Create nodes

node1 = Node(3)

node2 = Node(5)

node3 = Node(13)

node4 = Node(2)

# Link nodes

[Link] = node2

[Link] = node1

[Link] = node3

[Link] = node2

[Link] = node4
[Link] = node3

# Forward traversal

print("\nTraversing forward:")

currentNode = node1

while currentNode:

print([Link], end=" -> ")

currentNode = [Link]

print("null")

# Backward traversal

print("\nTraversing backward:")

currentNode = node4

while currentNode:

print([Link], end=" -> ")

currentNode = [Link]

print("null")

OUTPUT:

Traversing forward:
3 -> 5 -> 13 -> 2 -> null

Traversing backward:
2 -> 13 -> 5 -> 3 -> null
STACK AND QUEUE ADT
Coding :

# Stack (LIFO)

stack = []

[Link]('a')

[Link]('b')

[Link]('c')

print("Initial stack:")

print(stack)

print("\nElements popped from stack:")

print([Link]()) # c

print([Link]()) # b

print([Link]()) # a

print("\nStack after elements are popped:")

print(stack)

# Queue (FIFO)

queue = []

[Link]('a')
[Link]('b')

[Link]('c')

print("\nInitial queue:")

print(queue)

print("\nElements dequeued from queue:")

print([Link](0)) # a

print([Link](0)) # b

print([Link](0)) # c

print("\nQueue after removing elements:")

print(queue)

# List operations

List = [1, 2, 3, 4]

print("\nInitial List:")

print(List)

[Link]([8, 'Geeks', 'Always'])

print("\nList after performing Extend Operation:")

print(List)
Output:

Stack:

Initial stack ['a', 'b', 'c']

Elements poped from stack:

Stack after elements are poped:

[]

Queue: ['a', 'b', 'c']

Elements dequeued from queue

Queue after removing elements

[] List:

Initial List:

[1, 2, 3, 4]

List after performing Extend Operation:

[1, 2, 3, 4, 8, 'Geeks', 'Always']

Bubble sort:

def bubble_sort(alist):
for i in range(len(alist) - 1, 0, -1):
no_swap = True
for j in range(0, i):
if alist[j + 1] < alist[j]:
alist[j], alist[j + 1] = alist[j + 1], alist[j]
no_swap = False
if no_swap: # Optimization: stop early if no swaps
return

# Take input from user

alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist] # convert input to integers

bubble_sort(alist)
print('Sorted list:', alist)

OUTPUT:

Enter the list of numbers: 5 2 9 1 7

Sorted list: [1, 2, 5, 7, 9]
Selection sort:

PROGRAM:

def selection_sort(alist):
for i in range(0, len(alist) - 1):
smallest = i
for j in range(i + 1, len(alist)):
if alist[j] < alist[smallest]:
smallest = j
# swap
alist[i], alist[smallest] = alist[smallest], alist[i]

# Take input from user

alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist] # convert input to integers

selection_sort(alist)
print('Sorted list:', alist)

output:

Enter the list of numbers: 29 10 14 37 13

Sorted list: [10, 13, 14, 29, 37]
Insertion Sort:

PROGRAM:

def insertion_sort(alist):

'''Sorts the list using insertion sort.'''

for i in range(1, len(alist)):

key = alist[i] # Element to be inserted into the sorted part

j=i-1

# Move elements of alist[0..i-1] that are greater than key

while j >= 0 and alist[j] > key:

alist[j + 1] = alist[j]

j -= 1

# Insert the key into the correct position

alist[j + 1] = key

# Example Usage:

alist = input("Enter a list of numbers (space-separated): ").split()

alist = [int(x) for x in alist] # Convert strings to integers

insertion_sort(alist)

print("Sorted list:", alist)

OUTPUT:

The unsorted list is: [7, 2, 1, 6]

The sorted new list is: [1, 2, 6, 7]
Shell Sort:

PROGRAM:

def shell_sort(alist):

'''Sorts the list using the Shell Sort algorithm.'''

n = len(alist)

# Start with a large gap, then reduce the gap

gap = n // 2

while gap > 0:

# Perform an insertion sort with the current gap

for i in range(gap, n):

key = alist[i]

j=i

while j >= gap and alist[j - gap] > key:

alist[j] = alist[j - gap]

j -= gap

alist[j] = key

# Reduce the gap

gap //= 2

# Example Usage:
alist = input("Enter a list of numbers (space-separated): ").split()

alist = [int(x) for x in alist] # Convert strings to integers

shell_sort(alist)

print("Sorted list:", alist)

OUTPUT:

Enter a list of numbers (space-separated): 12 11 20 30 25

Sorted list: [11, 12, 20, 25, 30]
Merge Sort:
PROGRAM:

def merge_sort(alist, start, end):

'''Sorts the list from indexes start to end - 1 inclusive.'''

if end - start > 1:

mid = (start + end) // 2

merge_sort(alist, start, mid)

merge_sort(alist, mid, end)

merge_list(alist, start, mid, end)

def merge_list(alist, start, mid, end):

left = alist[start:mid]

right = alist[mid:end]

k = start

i=0

j=0

# Merge the two halves

while (i < len(left) and j < len(right)):

if left[i] <= right[j]:

alist[k] = left[i]

i += 1

else:

alist[k] = right[j]
 j += 1

k += 1

# If there are any remaining elements in the left half

while i < len(left):

alist[k] = left[i]

i += 1

k += 1

# If there are any remaining elements in the right half

while j < len(right):

alist[k] = right[j]

j += 1

k += 1

# Taking input from the user

alist = input('Enter the list of numbers (space-separated): ').split()

alist = [int(x) for x in alist]

# Perform merge sort on the entire list

merge_sort(alist, 0, len(alist))
# Output the sorted list

print('Sorted list:', alist)

OUTPUT:

Enter the list of numbers (space-separated): 15 25 34 12 28

Sorted list: [12, 15, 25, 28, 34]
Quick Sort:

Program:

def quicksort(alist, start, end):

'''Sorts the list from indexes start to end - 1 inclusive.'''

if end - start > 1: # Only proceed if there are at least two elements

p = partition(alist, start, end) # Partition the list

quicksort(alist, start, p) # Recursively sort the left part

quicksort(alist, p + 1, end) # Recursively sort the right part

def partition(alist, start, end):

pivot = alist[start] # Choose the pivot element (first element)

i = start + 1 # Start pointer

j = end - 1 # End pointer

while True:

while i <= j and alist[i] <= pivot: # Move i to the right

i=i+1

while i <= j and alist[j] >= pivot: # Move j to the left

j=j-1

if i <= j:

alist[i], alist[j] = alist[j], alist[i] # Swap i and j

else:
 break

# Place pivot in correct position

alist[start], alist[j] = alist[j], alist[start]

return j # Return the position of the pivot

# Input and execution

alist = input('Enter the list of numbers: ').split()

alist = [int(x) for x in alist] # Convert input to list of integers

quicksort(alist, 0, len(alist)) # Perform quicksort

print('Sorted list:', alist)

OUTPUT:

Enter the list of numbers: 25 34 12 65 43 44

Sorted list: [12, 25, 34, 43, 44, 65]
BINARY SEARCH:

def binarySearch(target, arr):

left = 0
right = len(arr) - 1
iterations = 0 # local counter instead of global

while left <= right:

iterations += 1
mid = (left + right) // 2

if target == arr[mid]:
return mid, iterations
elif target < arr[mid]:
right = mid - 1
else:
left = mid + 1

return -1, iterations

if __name__ == '__main__':
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14]
target = 12
answer, iterations = binarySearch(target, arr)

if answer != -1:
print(f'Target {target} found at position {answer} in {iterations} iterations')
else:
print('Target not found')

OUTPUT:

Target 12 found at position 10 in 3 iterations

LINEAR SEARCH:

def linearSearch(target, arr):

position = 0
iterations = 0 # local counter

while position < len(arr):

iterations += 1
if target == arr[position]:
return position, iterations
position += 1

return -1, iterations

if __name__ == '__main__':
arr = [1, 2, 3, 4, 5, 6, 7, 8]
target = 3
answer, iterations = linearSearch(target, arr)

if answer != -1:
print(f'Target found at index: {answer} in {iterations} iterations')
else:
print('Target not found in the list')

OUTPUT:

Target found at index: 2 in 3 iterations

In-order Traversal:

Program:

class Node:

def __init__(self, data):

[Link] = None

[Link] = None

[Link] = data

# Insert Node

def insert(self, data):

if data < [Link]:

if [Link] is None:

[Link] = Node(data)

else:

[Link](data)

elif data > [Link]:

if [Link] is None:

[Link] = Node(data)

else:

[Link](data)

# Print the Tree (inorder)

def PrintTree(self):
 if [Link]:

[Link]()

print([Link], end=" ")

if [Link]:

[Link]()

# Inorder traversal (Left -> Root -> Right)

def inorderTraversal(self, root):

res = []

if root:

res = [Link]([Link])

[Link]([Link])

res = res + [Link]([Link])

return res

# Create the binary search tree and insert values

root = Node(27)

[Link](14)

[Link](35)

[Link](10)

[Link](19)

[Link](31)
[Link](42)

# Inorder traversal of the tree

print("Inorder Traversal of the tree:", [Link](root))

# Print the tree structure

print("Tree structure (inorder):", end=" ")

[Link]()

OUTPUT:

Inorder Traversal of the tree: [10, 14, 19, 27, 31, 35, 42]
Tree structure (inorder): 10 14 19 27 31 35 42
Preorder Traversal:

class Node:

def __init__(self, data):

[Link] = None

[Link] = None

[Link] = data

# Insert Node

def insert(self, data):

if data < [Link]: # Insert into left subtree

if [Link] is None:

[Link] = Node(data)

else:

[Link](data)

elif data > [Link]: # Insert into right subtree

if [Link] is None:

[Link] = Node(data)

else:

[Link](data)

# Ignore duplicates

# Preorder traversal (Root -> Left -> Right)

def PreorderTraversal(self, root):

 res = []

if root:

[Link]([Link]) # Visit root

res = res + [Link]([Link]) # Visit left

res = res + [Link]([Link]) # Visit right

return res

# Print tree (Preorder structure for clarity)

def PrintTree(self):

print([Link], end=" ")

if [Link]:

[Link]()

if [Link]:

[Link]()

# Create the binary search tree and insert values

root = Node(27)

[Link](14)

[Link](35)

[Link](10)

[Link](19)

[Link](31)
[Link](42)

# Preorder traversal of the tree

print("Preorder Traversal of the tree:", [Link](root))

# Print the tree structure

print("Tree structure (Preorder):", end=" ")

[Link]()

OUTPUT:

Preorder Traversal of the tree: [27, 14, 10, 19, 35, 31, 42]
Tree structure (Preorder): 10 14 19 27 31 35 42
Postorder Traversal:

class Node:

def __init__(self, data):

[Link] = None

[Link] = None

[Link] = data

# Insert Node

def insert(self, data):

if data < [Link]:

if [Link] is None:

[Link] = Node(data)

else:

[Link](data)

else: # data >= [Link] goes to right

if [Link] is None:

[Link] = Node(data)

else:

[Link](data)

# Print the tree (Inorder for reference)

def PrintTree(self):

if [Link]:
 [Link]()

print([Link], end=" ")

if [Link]:

[Link]()

# Postorder traversal (Left -> Right -> Root)

def PostorderTraversal(self, root):

res = []

if root:

res = [Link]([Link]) # Left

res = res + [Link]([Link]) # Right

[Link]([Link]) # Root

return res

# Example usage

root = Node(27)

[Link](14)

[Link](35)

[Link](10)

[Link](19)

[Link](31)

[Link](42)
# Postorder Traversal of the tree

print("Postorder Traversal:", [Link](root))

# Print the tree (inorder for reference)

print("Tree structure (Inorder):", end=" ")

[Link]()

OUTPUT:

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

Tree structure (Inorder): 10 14 19 27 31 35 42

Single Source Shortest Path:

Program:

class Graph:

def __init__(self, size):

self.adj_matrix = [[0] * size for _ in range(size)]

[Link] = size

self.vertex_data = [''] * size

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

if 0 <= u < [Link] and 0 <= v < [Link]:

self.adj_matrix[u][v] = weight

self.adj_matrix[v][u] = weight # Undirected graph

def add_vertex_data(self, vertex, data):

if 0 <= vertex < [Link]:

self.vertex_data[vertex] = data

def dijkstra(self, start_vertex_data):

start_vertex = self.vertex_data.index(start_vertex_data)

distances = [float('inf')] * [Link]

distances[start_vertex] = 0

visited = [False] * [Link]

 for _ in range([Link]):

min_distance = float('inf')

u = None

for i in range([Link]):

if not visited[i] and distances[i] < min_distance:

min_distance = distances[i]

u=i

if u is None:

break

visited[u] = True

for v in range([Link]):

if self.adj_matrix[u][v] != 0 and not visited[v]:

alt = distances[u] + self.adj_matrix[u][v]

if alt < distances[v]:

distances[v] = alt

return distances

# Dijkstra's Algorithm Test

g = Graph(7)

g.add_vertex_data(0, 'A')

g.add_vertex_data(1, 'B')

g.add_vertex_data(2, 'C')

g.add_vertex_data(3, 'D')

g.add_vertex_data(4, 'E')

g.add_vertex_data(5, 'F')

g.add_vertex_data(6, 'G')

g.add_edge(3, 0, 4) # D - A

g.add_edge(3, 4, 2) # D - E

g.add_edge(0, 2, 3) # A - C

g.add_edge(0, 4, 4) # A - E

g.add_edge(4, 2, 4) # E - C

g.add_edge(4, 6, 5) # E - G

g.add_edge(2, 5, 5) # C - F

g.add_edge(2, 1, 2) # C - B

g.add_edge(1, 5, 2) # B - F

g.add_edge(6, 5, 5) # G - F

print("\nDijkstra's Algorithm starting from vertex D:")

distances = [Link]('D')

for i, d in enumerate(distances):
 print(f"Distance from D to {g.vertex_data[i]}: {d}")

OUTPUT:

Dijkstra's Algorithm starting from vertex D:

Distance from D to A: 4
Distance from D to B: 8
Distance from D to C: 6
Distance from D to D: 0
Distance from D to E: 2
Distance from D to F: 10
Distance from D to G: 7
Prim's Algorithm:

Program:

class Graph:

def __init__(self, size):

self.adj_matrix = [[0] * size for _ in range(size)]

[Link] = size

self.vertex_data = [''] * size

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

if 0 <= u < [Link] and 0 <= v < [Link]:

self.adj_matrix[u][v] = weight

self.adj_matrix[v][u] = weight # For undirected graph

def add_vertex_data(self, vertex, data):

if 0 <= vertex < [Link]:

self.vertex_data[vertex] = data

def prims_algorithm(self):

in_mst = [False] * [Link]

key_values = [float('inf')] * [Link]

parents = [-1] * [Link]

key_values[0] = 0 # Start from vertex 0

 print("Edge \tWeight")

total_weight = 0

for _ in range([Link]):

# Pick the minimum key vertex not yet included in MST

u = -1

for v in range([Link]):

if not in_mst[v] and (u == -1 or key_values[v] < key_values[u]):

u=v

in_mst[u] = True

# Print the edge and weight (skip root since it has no parent)

if parents[u] != -1:

print(f"{self.vertex_data[parents[u]]}-{self.vertex_data[u]} \
t{self.adj_matrix[u][parents[u]]}")

total_weight += self.adj_matrix[u][parents[u]]

# Update the key values of the adjacent vertices

for v in range([Link]):

if 0 < self.adj_matrix[u][v] < key_values[v] and not in_mst[v]:

key_values[v] = self.adj_matrix[u][v]
 parents[v] = u

print(f"\nTotal weight of MST: {total_weight}")

# Minimum Spanning Tree (MST) Test with Prim's Algorithm

g2 = Graph(8)

g2.add_vertex_data(0, 'A')

g2.add_vertex_data(1, 'B')

g2.add_vertex_data(2, 'C')

g2.add_vertex_data(3, 'D')

g2.add_vertex_data(4, 'E')

g2.add_vertex_data(5, 'F')

g2.add_vertex_data(6, 'G')

g2.add_vertex_data(7, 'H')

g2.add_edge(0, 1, 4) # A - B

g2.add_edge(0, 3, 3) # A - D

g2.add_edge(1, 2, 3) # B - C

g2.add_edge(1, 3, 5) # B - D

g2.add_edge(1, 4, 6) # B - E

g2.add_edge(2, 4, 4) # C - E

g2.add_edge(2, 7, 2) # C - H
g2.add_edge(3, 4, 7) # D - E

g2.add_edge(3, 5, 4) # D - F

g2.add_edge(4, 5, 5) # E - F

g2.add_edge(4, 6, 3) # E - G

g2.add_edge(5, 6, 7) # F - G

g2.add_edge(6, 7, 5) # G - H

print("\nMinimum Spanning Tree (MST) using Prim's Algorithm:")

g2.prims_algorithm()

OUTPUT:

Minimum Spanning Tree (MST) using Prim's Algorithm:

Edge Weight
A-D 3
A-B 4
B-C 3
C-H 2
C-E 4
E-G 3
D-F 4

Total weight of MST: 23

N-Queen Problem:

Program:

N = 4 # Size of the board, N x N

def isSafe(board, row, col):

# Check this row on left side

for i in range(col):

if board[row][i] == 1:

return False

# Check upper diagonal on left side

for i, j in zip(range(row, -1, -1), range(col, -1, -1)):

if board[i][j] == 1:

return False

# Check lower diagonal on left side

for i, j in zip(range(row, N, 1), range(col, -1, -1)):

if board[i][j] == 1:

return False

return True
def solveNQUtil(board, col):

# Base case: If all queens are placed, then return true

if col >= N:

return True

# Try placing this queen in all rows one by one

for i in range(N):

if isSafe(board, i, col):

# Place this queen

board[i][col] = 1

# Recur to place the rest of the queens

if solveNQUtil(board, col + 1):

return True

# Backtrack (remove the queen)

board[i][col] = 0

return False

def printSolution(board):

for i in range(N):
 for j in range(N):

print(board[i][j], end=" ")

print()

print() # Blank line after solution

def solveNQ():

board = [[0 for _ in range(N)] for _ in range(N)]

if not solveNQUtil(board, 0):

print("Solution does not exist")

return False

print("One possible solution:")

printSolution(board)

return True

# Driver

solveNQ()

OUTPUT:

0010
1000
0001
0100
True