ADSA Lab Programs

1. Construct an AVL tree for a given set of elements which are stored in a
file. And implement insert and delete operation on the constructed tree.
Write contents of tree into a new file using in-order.
Source code:
class Node:
def __init__(self, key):
[Link] = key
[Link] = [Link] = None
[Link] = 1

class AVLTree:
def get_height(self, root):
return [Link] if root else 0

def get_balance(self, root):

return self.get_height([Link]) - self.get_height([Link]) if root else 0

def right_rotate(self, y):

x = [Link]
T2 = [Link]
[Link] = y
[Link] = T2
[Link] = 1 + max(self.get_height([Link]), self.get_height([Link]))
[Link] = 1 + max(self.get_height([Link]), self.get_height([Link]))
return x

def left_rotate(self, x):

y = [Link]
T2 = [Link]
[Link] = x
[Link] = T2
[Link] = 1 + max(self.get_height([Link]), self.get_height([Link]))
[Link] = 1 + max(self.get_height([Link]), self.get_height([Link]))
 return y

def insert(self, root, key):

if not root:
return Node(key)
elif key < [Link]:
[Link] = [Link]([Link], key)
elif key > [Link]:
[Link] = [Link]([Link], key)
else:
return root # Duplicate keys not allowed

[Link] = 1 + max(self.get_height([Link]), self.get_height([Link]))

balance = self.get_balance(root)

# Balance the tree

if balance > 1 and key < [Link]:
return self.right_rotate(root)
if balance < -1 and key > [Link]:
return self.left_rotate(root)
if balance > 1 and key > [Link]:
[Link] = self.left_rotate([Link])
return self.right_rotate(root)
if balance < -1 and key < [Link]:
[Link] = self.right_rotate([Link])
return self.left_rotate(root)

return root

def min_value_node(self, node):

current = node
while [Link]:
current = [Link]
return current
def delete(self, root, key):
if not root:
return root
elif key < [Link]:
[Link] = [Link]([Link], key)
elif key > [Link]:
[Link] = [Link]([Link], key)
else:
if not [Link]:
return [Link]
elif not [Link]:
return [Link]
temp = self.min_value_node([Link])
[Link] = [Link]
[Link] = [Link]([Link], [Link])

if not root:
return root

[Link] = 1 + max(self.get_height([Link]), self.get_height([Link]))

balance = self.get_balance(root)

# Balance the tree

if balance > 1 and self.get_balance([Link]) >= 0:
return self.right_rotate(root)
if balance > 1 and self.get_balance([Link]) < 0:
[Link] = self.left_rotate([Link])
return self.right_rotate(root)
if balance < -1 and self.get_balance([Link]) <= 0:
return self.left_rotate(root)
if balance < -1 and self.get_balance([Link]) > 0:
[Link] = self.right_rotate([Link])
return self.left_rotate(root)

return root
 def inorder(self, root, result):
if root:
[Link]([Link], result)
[Link]([Link])
[Link]([Link], result)

# Main program
if __name__ == "__main__":
avl = AVLTree()
root = None

# Read from input file

try:
with open("[Link]", "r") as f:
numbers = list(map(int, [Link]().split()))
for num in numbers:
root = [Link](root, num)
except FileNotFoundError:
print("[Link] not found.")
exit()

# Insert and Delete example

root = [Link](root, 25) # example insert
root = [Link](root, 10) # example delete

# Write in-order traversal to output file

result = []
[Link](root, result)

with open("[Link]", "w") as f:

[Link](" ".join(map(str, result)))

print("AVL tree created and in-order written to [Link].")

Output:
[Link]:
30 10 20 34 50 60 8 4
[Link]
4 8 20 25 30 34 50 60
2. Construct B-Tree an order of 5 with a set of 100 random elements stored
in array. Implement searching, insertion and deletion operations.
Source code:
class BTreeNode:
def __init__(self, t, leaf=False):
self.t, [Link] = t, leaf
[Link], [Link] = [], []

def insert_non_full(self, k):

i = len([Link]) - 1
if [Link]:
[Link](k)
while i >= 0 and [Link][i] > k:
[Link][i + 1] = [Link][i]; i -= 1
[Link][i + 1] = k
else:
while i >= 0 and [Link][i] > k: i -= 1
i += 1
if len([Link][i].keys) == 2 * self.t - 1:
[Link](i)
if k > [Link][i]: i += 1
[Link][i].insert_non_full(k)

def split(self, i):

t, y = self.t, [Link][i]
z = BTreeNode(t, [Link])
promoted_key = [Link][t - 1]
[Link], [Link] = [Link][t:], [Link][:t - 1]
if not [Link]:
[Link], [Link] = [Link][t:], [Link][:t]
[Link](i + 1, z)
[Link](i, promoted_key)

def traverse(self):
for i in range(len([Link])):
 if not [Link]:
[Link][i].traverse()
print([Link][i], end=' ')
if not [Link]:
[Link][-1].traverse()

class BTree:
def __init__(self, t):
self.t, [Link] = t, None

def insert(self, k):

if not [Link]:
[Link] = BTreeNode(self.t, True)
[Link](k)
elif len([Link]) == 2 * self.t -1:
s = BTreeNode(self.t)
[Link]([Link])
[Link](0)
[Link][0 if k < [Link][0] else 1].insert_non_full(k)
[Link] = s
else: [Link].insert_non_full(k)
def traverse(self): [Link]() if [Link] else print("Empty")

# MAIN DRIVER
btree = BTree(t=3) # Order 5 → t = ceil(5/2) = 3
with open("[Link]") as f:
for x in f: [Link](int([Link]()))

print("Initial B-Tree:")
[Link]()

while True:
op = input("\n\n[I]nsert [T]raverse [Q]uit: ").lower()
if op == 'i': [Link](int(input("Insert key: ")))
 elif op == 't': [Link]()
elif op == 'q': break

Output:
[I]nsert [T]raverse [Q]uit: i
Insert key: 89

[I]nsert [T]raverse [Q]uit: t

7 8 10 12 15 16 20 30 40 42 50 54 66 89

[I] nsert [T]raverse [Q]uit: q

3. Construct Min using arrays, delete any element and display the content
of the Heap.
Source code:
# Min Heap class
class MinHeap:
def __init__(self):
[Link] = []

def parent(self, i):

return (i - 1) // 2

def left(self, i):

return 2 * i + 1

def right(self, i):

return 2 * i + 2

def swap(self, i, j):

[Link][i], [Link][j] = [Link][j], [Link][i]

def insert(self, val):

[Link](val)
i = len([Link]) - 1
# Bubble-up to maintain heap property
while i != 0 and [Link][[Link](i)] > [Link][i]:
[Link](i, [Link](i))
i = [Link](i)
def heapify(self, i):
n = len([Link])
smallest = i
l = [Link](i)
r = [Link](i)
if l < n and [Link][l] < [Link][smallest]:
smallest = l
if r < n and [Link][r] < [Link][smallest]:
 smallest = r
if smallest != i:
[Link](i, smallest)
[Link](smallest)
def delete_root(self):
n = len([Link])
if n == 0:
print("Heap is empty")
return
# Replace root with last element
[Link][0] = [Link][-1]
[Link]()
# Heapify from root to fix heap structure
if len([Link]) > 0:
[Link](0)
def display(self):
print("Min Heap:", [Link])
# main
arr = [int(x) for x in input("Enter at least 10 numbers separated by spaces: ").split()]
print("----- Min Heap Demo -----")
min_heap = MinHeap()
for v in arr:
min_heap.insert(v)
min_heap.display()
print("Deleting root...")
min_heap.delete_root()
min_heap.display()

Output:
Enter at least 10 numbers separated by spaces: 5 2 79 34 27 4 6 9 1 7
----- Min Heap Demo -----
Min Heap: [1, 2, 4, 5, 7, 79, 6, 34, 9, 27]
Deleting root...
Min Heap: [2, 5, 4, 9, 7, 79, 6, 34, 27]
4. Construct Max Heap using arrays, delete any element and display the
content of the Heap.
Source code:

# Max Heap class using similar logic

class MaxHeap:
def __init__(self):
[Link] = []
def parent(self, i):
return (i - 1) // 2
def left(self, i):
return 2 * i + 1
def right(self, i):
return 2 * i + 2
def swap(self, i, j):
[Link][i], [Link][j] = [Link][j], [Link][i]
def insert(self, val):
[Link](val)
i = len([Link]) - 1
# Bubble-up to maintain max heap property
while i != 0 and [Link][[Link](i)] < [Link][i]:
[Link](i, [Link](i))
i = [Link](i)
def heapify(self, i):
n = len([Link])
largest = i
l = [Link](i)
r = [Link](i)
if l < n and [Link][l] > [Link][largest]:
largest = l
if r < n and [Link][r] > [Link][largest]:
largest = r
if largest != i:
[Link](i, largest)
[Link](largest)
 def delete_root(self):
n = len([Link])
if n == 0:
print("Heap is empty")
return
[Link][0] = [Link][-1]
[Link]()
if len([Link]) > 0:
[Link](0)
def display(self):
print("Max Heap:", [Link])
# main
arr = [int(x) for x in input("Enter at least 10 numbers separated by spaces: ").split()]
print("\n----- Max Heap Demo -----")
max_heap = MaxHeap()
for v in arr:
max_heap.insert(v)
max_heap.display()
print("Deleting root...")
max_heap.delete_root()
max_heap.display()

Output:
Enter at least 10 numbers separated by spaces: 5 2 79 34 27 4 6 9 1 7

----- Max Heap Demo -----

Max Heap: [79, 34, 6, 9, 27, 4, 5, 2, 1, 7]
Deleting root...
Max Heap: [34, 27, 6, 9, 7, 4, 5, 2, 1]
5. Implement BFT and DFT for given graph, when graph is represented by
a) Adjacency Matrix

Source code:
from collections import deque
def bfs(adj_matrix, start_vertex):
visited = [False] * len(adj_matrix)
queue = deque()

print("BFT (BFS Traversal):", end=" ")

[Link](start_vertex)
visited[start_vertex] = True

while queue:
vertex = [Link]()
print(vertex, end=" ")

for i in range(len(adj_matrix)):
if adj_matrix[vertex][i] == 1 and not visited[i]:
[Link](i)
visited[i] = True
print()

# Function to perform Depth First Traversal

def dfs(adj_matrix, start_vertex, visited=None):
if visited is None:
visited = [False] * len(adj_matrix)
print("DFT (DFS Traversal):", end="--> ")

visited[start_vertex] = True
print(start_vertex, end=" ")

for i in range(len(adj_matrix)):
if adj_matrix[start_vertex][i] == 1 and not visited[i]:
dfs(adj_matrix, i, visited)
# Main function
def main():
# Input number of vertices
n = int(input("Enter number of vertices: "))

# Input adjacency matrix

print("Enter the adjacency matrix (row-wise):")
adj_matrix = []
for i in range(n):
row = list(map(int, input(f"Row {i}: ").split()))
adj_matrix.append(row)

# Input starting vertex

start_vertex = int(input("Enter the starting vertex (0 to {}): ".format(n - 1)))

# Perform BFS and DFS

bfs(adj_matrix, start_vertex)
dfs(adj_matrix, start_vertex)
print() # Newline for clean output

if __name__ == "__main__":
main()
Output:

Enter number of vertices: 7

Enter the adjacency matrix (row-wise):

Row 0: 0 1 0 1 1 0 0

Row 1: 1 0 1 0 1 0 0

Row 2: 0 1 0 0 1 1 1

Row 3: 1 0 0 0 1 0 0

Row 4: 1 1 1 1 0 1 0
Row 5: 0 0 1 0 1 0 1

Row 6: 0 0 1 0 0 1 0

Enter the starting vertex (0 to 6): 0

BFT (BFS Traversal): 0 1 3 4 2 5 6

DFT (DFS Traversal): 0 1 2 4 3 5 6

b) Adjacency Lists
Source code:
from collections import deque

# Function to perform Breadth-First Traversal

def bfs(adj_list, start_vertex):
visited = [False] * len(adj_list)
queue = deque()

print("BFT (BFS Traversal):", end=" ")

[Link](start_vertex)
visited[start_vertex] = True

while queue:
vertex = [Link]()
print(vertex, end=" ")

for neighbor in adj_list[vertex]:

if not visited[neighbor]:
[Link](neighbor)
visited[neighbor] = True
print()

# Function to perform Depth-First Traversal

def dfs(adj_list, start_vertex, visited=None):
 if visited is None:
visited = [False] * len(adj_list)
print("DFT (DFS Traversal):", end=" ")

visited[start_vertex] = True
print(start_vertex, end=" ")

for neighbor in adj_list[start_vertex]:

if not visited[neighbor]:
dfs(adj_list, neighbor, visited)

# Main function
def main():
# Input number of vertices
n = int(input("Enter number of vertices: "))

# Create adjacency list

adj_list = [[] for _ in range(n)]

# Input edges
e = int(input("Enter number of edges: "))
print("Enter each edge as two vertices (u v):")
for _ in range(e):
u, v = map(int, input().split())
adj_list[u].append(v)
adj_list[v].append(u) # Remove this line for directed graph

# Input starting vertex

start_vertex = int(input(f"Enter the starting vertex (0 to {n - 1}): "))

# Perform BFS and DFS

bfs(adj_list, start_vertex)
dfs(adj_list, start_vertex)
print()
if __name__ == "__main__":
 main()

Output:

Enter number of vertices: 5

Enter number of edges: 6

Enter each edge as two vertices (u v):

01

03

04

12

14

24

Enter the starting vertex (0 to 4): 0

BFT (BFS Traversal): 0 1 3 4 2

DFT (DFS Traversal): 0 1 2 4 3

6. Write a program for finding the bi-connected components in a given
graph.
Source code:
def is_biconnected(adj_matrix):
n = len(adj_matrix)
disc = [0] * n
low = [0] * n
parent = [-1] * n
time = [1] # start discovery time from 1
articulation_points = [False] * n

def dfs(u):
children = 0
disc[u] = low[u] = time[0]
time[0] += 1

for v in range(n):
if adj_matrix[u][v] == 1:
if disc[v] == 0: # unvisited
parent[v] = u
children += 1
dfs(v)
low[u] = min(low[u], low[v])

if parent[u] == -1 and children > 1:

articulation_points[u] = True
if parent[u] != -1 and low[v] >= disc[u]:
articulation_points[u] = True
elif v != parent[u]:
low[u] = min(low[u], disc[v])

dfs(0)

if any(d == 0 for d in disc):

return False, disc, low
 if any(articulation_points):
return False, disc, low
return True, disc, low

# Given adjacency matrix from your example

adj_matrix = [
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]
]

result, disc, low = is_biconnected(adj_matrix)

print("Is graph biconnected? ", result)
print("Discovery times:", disc)
print("Lowest reachable:", low)

Output:
Is graph biconnected? True
Discovery times: [1, 2, 3, 4]
Lowest reachable: [1, 1, 1, 2]
7. Implement Quick sort and observe the execution time for various input
sizes (Average, Worst and Best cases).
Source code:
def swap(a,b,arr):
if a!=b:
temp=arr[a]
arr[a]=arr[b]
arr[b]=temp
def partition(elements,start,end):
pivot_index=start
pivot=elements[pivot_index]
while start<end:
while start<len(elements) and elements[start]<=pivot:
start+=1
while elements[end]>pivot:
end-=1
if start<end:
swap(start,end,elements)
swap(pivot_index,end,elements)
return end

def quick_sort(elements,start,end):
if start<end:
pi=partition(elements,start,end)
quick_sort(elements,start,pi-1)#left partiton
quick_sort(elements,pi+1,end)#right partiton

if __name__=="__main__":
elements = []
num_elements = int(input("Enter the number of elements: "))
for i in range(num_elements):
element = int(input(f"Enter element {i+1}: "))
[Link](element)
quick_sort(elements, 0, len(elements) - 1)
 print("Sorted array:", elements)
Output:
Enter the number of elements: 5
Enter element 1: 56
Enter element 2: 12
Enter element 3: 56
Enter element 4: 67
Enter element 5: 89
Sorted array: [12, 56, 56, 67, 89]
8. Implement Merge sort and observe the execution time for various input
sizes (Average, Worst and Best cases).
Source code:
def merge_sort(arr):
# Base case: A list of 0 or 1 elements is already sorted
if len(arr) <= 1:
return arr

# Split array into two halves

mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])

# Merge the sorted halves

return merge(left, right)

def merge(left, right):

merged = []
i=j=0

# Compare elements and merge

while i < len(left) and j < len(right):
if left[i] < right[j]:
[Link](left[i])
i += 1
else:
[Link](right[j])
j += 1

# Add remaining elements

[Link](left[i:])
[Link](right[j:])

return merged
# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
print("Original:", arr)
sorted_arr = merge_sort(arr)
print("Sorted:", sorted_arr)

Output:
Original: [38, 27, 43, 3, 9, 82, 10]
Sorted: [3, 9, 10, 27, 38, 43, 82]
9. Single Source Shortest Paths using Greedy method when the graph is
represented by adjacency matrix.
Source code:
import heapq, time
# -------------------------------
# Dijkstra using Adjacency Matrix
# -------------------------------
def dijkstra_matrix(graph, src):
n = len(graph)
dist = [float("inf")] * n
visited = [False] * n
dist[src] = 0

for _ in range(n):
# Greedy choice: pick nearest unvisited node
u = -1
min_dist = float("inf")
for i in range(n):
if not visited[i] and dist[i] < min_dist:
u=i
min_dist = dist[i]

visited[u] = True

# Relaxation step
for v in range(n):
if graph[u][v] != 0 and not visited[v]:
if dist[u] + graph[u][v] < dist[v]:
dist[v] = dist[u] + graph[u][v]
return dist

# -------------------------------
# Example Graph
# -------------------------------
matrix = [
 [0, 10, 0, 5, 0],
[10, 0, 1, 2, 0],
[0, 1, 0, 9, 4],
[5, 2, 9, 0, 2],
[0, 0, 4, 2, 0]
]

src = 0

start = time.perf_counter()
dist_matrix = dijkstra_matrix(matrix, src)
end = time.perf_counter()
print("Matrix Distances:", dist_matrix)
print("Time with Adjacency Matrix: {:.6f} seconds".format(end - start))
Output:
List Distances : [0, 7, 8, 5, 7]
Time with Adjacency List : 0.000036 seconds
10. Single Source Shortest Paths using Greedy method when the graph is
represented by adjacency lists.
Source code:
import heapq, time
# -------------------------------
# Dijkstra using Adjacency List
# -------------------------------
def dijkstra_list(graph, src):
n = len(graph)
dist = [float("inf")] * n
dist[src] = 0
pq = [(0, src)] # (distance, vertex)

while pq:
d, u = [Link](pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
[Link](pq, (dist[v], v))
return dist

# -------------------------------
# Example Graph
# -------------------------------
adj_list = [
[(1, 10), (3, 5)],
[(0, 10), (2, 1), (3, 2)],
[(1, 1), (3, 9), (4, 4)],
[(0, 5), (1, 2), (2, 9), (4, 2)],
[(2, 4), (3, 2)]
]
src = 0
start = time.perf_counter()
dist_list = dijkstra_list(adj_list, src)
end = time.perf_counter()
print("List Distances :", dist_list)
print("Time with Adjacency List : {:.6f} seconds".format(end - start))

Output:
List Distances : [0, 7, 8, 5, 7]
Time with Adjacency List : 0.000018 seconds
11. Implement Job sequencing with deadlines using Greedy strategy.
Source code:
class Job:
def __init__(self, job_id, deadline, profit):
self.job_id = job_id
[Link] = deadline
[Link] = profit

def job_sequencing(jobs, n):

# Sort all jobs according to profit in descending order
[Link](key=lambda x: [Link], reverse=True)

# To keep track of free time slots

result = [False] * n

# To store result (sequence of jobs)

job_sequence = ['-1'] * n
# To store total profit
total_profit = 0

# Iterate through all jobs

for i in range(len(jobs)):
# Find a free slot for this job (from its deadline - 1 to 0)
for j in range(min(n, jobs[i].deadline) - 1, -1, -1):
if not result[j]:
result[j] = True
job_sequence[j] = jobs[i].job_id
total_profit+=jobs[i].profit
break

# Print the job sequence for maximum profit

print("Job Sequence:", job_sequence)
print("total profit:", total_profit)

if __name__ == "__main__": # Example usage

 jobs = [
Job('J1', 2, 100),
Job('J2', 1, 19),
Job('J3', 2, 27),
Job('J4', 1, 25),
Job('J5', 3, 15)
]
n = 3 # Number of available slots (can also be max deadline)
job_sequencing(jobs, n)

Output:
Job Sequence: ['J3', 'J1', 'J5']
total profit: 142
12. Write a program to solve 0/1 Knapsack problem Using Dynamic
Programming.
Source code:
#0/1 Knapsack problem Using Dynamic Programming.

def knapsack(W, wt, val, n):

# Create DP table
K = [[0 for x in range(W + 1)] for x in range(n + 1)]

# Build table K[][] in bottom-up manner

for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i - 1] <= w:
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]],
K[i - 1][w])
else:
K[i][w] = K[i - 1][w]

return K[n][W]

if __name__ == "__main__": # Example usage

profit = [60, 100, 120] # values
weight = [10, 20, 30] # weights
W = 50 # capacity of knapsack
n = len(profit)

max_profit = knapsack(W, weight, profit, n)

print("Maximum profit in Knapsack =", max_profit)

Output:
Maximum profit in Knapsack = 220
13. Implement N-Queens Problem Using Backtracking.
Source code:
def solve_nqueens(N):
board = [[0] * N for _ in range(N)]

def is_safe(row, col):

# Check column
for i in range(row):
if board[i][col] == 1:
return False
# Check upper-left diagonal
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 1:
return False
i -= 1
j -= 1
# Check upper-right diagonal
i, j = row - 1, col + 1
while i >= 0 and j < N:
if board[i][j] == 1:
return False
i -= 1
j += 1
return True

def place_queen(row):
if row == N:
for r in range(N):
for c in range(N):
print("Q" if board[r][c] else ".", end=" ")
print()
print()
return True
 found = False
for col in range(N):
if is_safe(row, col):
board[row][col] = 1
found = place_queen(row + 1) or found
board[row][col] = 0 # backtrack
return found

if not place_queen(0):
print("No solution exists for N =", N)

# Example usage
if __name__ == "__main__":
N=4
solve_nqueens(N)

Output:
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..
14. Use Backtracking strategy to solve 0/1 Knapsack problem.
Source code:
def knapsack_backtrack(wt, val, W, n, idx=0, curr_profit=0, curr_weight=0,
best=[0]):
# Base case: all items considered
if idx == n:
best[0] = max(best[0], curr_profit)
return

# Choice 1: Exclude the current item

knapsack_backtrack(wt, val, W, n, idx + 1, curr_profit, curr_weight, best)

# Choice 2: Include the current item (if it fits)

if curr_weight + wt[idx] <= W:
knapsack_backtrack(
wt, val, W, n,
idx + 1,
curr_profit + val[idx],
curr_weight + wt[idx],
best )

def solve_knapsack(wt, val, W):

n = len(wt)
best = [0] # store maximum profit found
knapsack_backtrack(wt, val, W, n, 0, 0, 0, best)
return best[0]

if __name__ == "__main__": # Example usage

profit = [60, 100, 120] # values
weight = [10, 20, 30] # weights
W = 50 # capacity of knapsack
max_profit = solve_knapsack(weight, profit, W)
print("Maximum profit using Backtracking =", max_profit)

Output:
Maximum profit using Backtracking = 220
15. Implement Travelling Sales Person problem using Branch and Bound
approach.
Source code:
import math
class TSPSolver:
def __init__(self, graph):
[Link] = graph
self.n = len(graph)
self.final_res = float("inf")
self.final_path = []

# Copy temporary solution to final path

def copy_to_final(self, curr_path):
self.final_path = curr_path[:] + [curr_path[0]]

# Find minimum edge cost having an end at vertex i

def first_min(self, i):
min_val = float("inf")
for k in range(self.n):
if [Link][i][k] != 0 and [Link][i][k] < min_val:
min_val = [Link][i][k]
return min_val

# Find second minimum edge cost having an end at vertex i

def second_min(self, i):
first, second = float("inf"), float("inf")
for j in range(self.n):
if i == j:
continue
if [Link][i][j] <= first:
second = first
first = [Link][i][j]
elif [Link][i][j] <= second and [Link][i][j] != first:
second = [Link][i][j]
 return second

# Recursive function for Branch and Bound

def tsp_rec(self, curr_bound, curr_weight, level, curr_path, visited):
# Base case: all vertices visited
if level == self.n:
if [Link][curr_path[level - 1]][curr_path[0]] != 0:
curr_res = curr_weight + [Link][curr_path[level -1]][curr_path[0]]
if curr_res < self.final_res:
self.copy_to_final(curr_path)
self.final_res = curr_res
return

# For current vertex, explore all neighbors

for i in range(self.n):
if ([Link][curr_path[level - 1]][i] != 0 and not visited[i]):
temp = curr_bound
curr_weight += [Link][curr_path[level - 1]][i]

# Compute new lower bound

if level == 1:
curr_bound -= ((self.first_min(curr_path[level - 1]) + self.first_min(i)) / 2)
else:
curr_bound -= ((self.second_min(curr_path[level - 1]) + self.first_min(i)) /
2)

# If promising, recurse
if curr_bound + curr_weight < self.final_res:
curr_path[level] = i
visited[i] = True
self.tsp_rec(curr_bound, curr_weight, level + 1, curr_path, visited)

# Backtrack
curr_weight -= [Link][curr_path[level - 1]][i]
curr_bound = temp
 visited[i] = False

# Solve TSP
def solve(self):
curr_bound = 0
curr_path = [-1] * (self.n + 1)
visited = [False] * self.n

# Compute initial bound (sum of first and second min for each vertex)
for i in range(self.n):
curr_bound += (self.first_min(i) + self.second_min(i))

curr_bound = [Link](curr_bound / 2)

visited[0] = True
curr_path[0] = 0

self.tsp_rec(curr_bound, 0, 1, curr_path, visited)

print("Minimum cost:", self.final_res)

print("Path taken:", " -> ".join(map(str, self.final_path)))

if __name__ == "__main__": # Example usage

# Graph represented as adjacency matrix
graph = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]

solver = TSPSolver(graph)
[Link]()
Output:
Minimum cost: 80
Path taken: 0 -> 1 -> 3 -> 2 -> -1 -> 0