2.

Construct B-Tree an order of 5 with a set of 100 random elements stored in

array.Implement searching, insertion and deletion operations.

import random

class BTreeNode:

def __init__(self, t, leaf=False):

self.t = t

self.leaf = leaf

self.keys = []

self.children = []

class BTree:

def __init__(self, t):

self.t = t

self.root = BTreeNode(t, True)

def traverse(self, node, level=0):

if node is not None:

print("Level", level, ":", node.keys)

level += 1

if not node.leaf:

for child in node.children:

self.traverse(child, level)

def search(self, k, node=None):

if node is None:

node = self.root
 i=0

while i < len(node.keys) and k > node.keys[i]:

i += 1

if i < len(node.keys) and k == node.keys[i]:

return node

if node.leaf:

return None

return self.search(k, node.children[i])

def insert(self, k):

root = self.root

if len(root.keys) == 2 * self.t - 1:

s = BTreeNode(self.t, False)

self.root = s

s.children.append(root)

self.split_child(s, 0)

self.insert_non_full(s, k)

else:

self.insert_non_full(root, k)

def insert_non_full(self, node, k):

i = len(node.keys) - 1

if node.leaf:

node.keys.append(None)

while i >= 0 and k < node.keys[i]:

node.keys[i + 1] = node.keys[i]

i -= 1

node.keys[i + 1] = k

else:
 while i >= 0 and k < node.keys[i]:

i -= 1

i += 1

if len(node.children[i].keys) == 2 * self.t - 1:

self.split_child(node, i)

if k > node.keys[i]:

i += 1

self.insert_non_full(node.children[i], k)

def split_child(self, parent, i):

t = self.t

y = parent.children[i]

z = BTreeNode(t, y.leaf)

parent.children.insert(i + 1, z)

parent.keys.insert(i, y.keys[t - 1])

z.keys = y.keys[t:(2 * t - 1)]

y.keys = y.keys[0:(t - 1)]

if not y.leaf:

z.children = y.children[t:(2 * t)]

y.children = y.children[0:t]

def delete(self, k):

self._delete(self.root, k)

if len(self.root.keys) == 0 and not self.root.leaf:

self.root = self.root.children[0]

def _delete(self, node, k):

t = self.t

idx = self._find_key(node, k)
 if idx < len(node.keys) and node.keys[idx] == k:

if node.leaf:

node.keys.pop(idx)

else:

self._delete_internal(node, idx)

else:

if node.leaf:

return

flag = (idx == len(node.keys))

if len(node.children[idx].keys) < t:

self._fill(node, idx)

if flag and idx > len(node.keys):

self._delete(node.children[idx - 1], k)

else:

self._delete(node.children[idx], k)

def _find_key(self, node, k):

idx = 0

while idx < len(node.keys) and node.keys[idx] < k:

idx += 1

return idx

def _delete_internal(self, node, idx):

t = self.t

k = node.keys[idx]

if len(node.children[idx].keys) >= t:

pred = self._get_predecessor(node, idx)

node.keys[idx] = pred

self._delete(node.children[idx], pred)
 elif len(node.children[idx + 1].keys) >= t:

succ = self._get_successor(node, idx)

node.keys[idx] = succ

self._delete(node.children[idx + 1], succ)

else:

self._merge(node, idx)

self._delete(node.children[idx], k)

def _get_predecessor(self, node, idx):

cur = node.children[idx]

while not cur.leaf:

cur = cur.children[-1]

return cur.keys[-1]

def _get_successor(self, node, idx):

cur = node.children[idx + 1]

while not cur.leaf:

cur = cur.children[0]

return cur.keys[0]

def _fill(self, node, idx):

t = self.t

if idx != 0 and len(node.children[idx - 1].keys) >= t:

self._borrow_from_prev(node, idx)

elif idx != len(node.keys) and len(node.children[idx + 1].keys) >= t:

self._borrow_from_next(node, idx)

else:

if idx != len(node.keys):

self._merge(node, idx)
 else:

self._merge(node, idx - 1)

def _borrow_from_prev(self, node, idx):

child = node.children[idx]

sibling = node.children[idx - 1]

child.keys.insert(0, node.keys[idx - 1])

if not child.leaf:

child.children.insert(0, sibling.children.pop())

node.keys[idx - 1] = sibling.keys.pop()

def _borrow_from_next(self, node, idx):

child = node.children[idx]

sibling = node.children[idx + 1]

child.keys.append(node.keys[idx])

if not sibling.leaf:

child.children.append(sibling.children.pop(0))

node.keys[idx] = sibling.keys.pop(0)

def _merge(self, node, idx):

child = node.children[idx]

sibling = node.children[idx + 1]

child.keys.append(node.keys[idx])

child.keys.extend(sibling.keys)

if not child.leaf:

child.children.extend(sibling.children)

node.keys.pop(idx)

node.children.pop(idx + 1)
# Helper function to create random elements and test B-Tree

def test_btree():

t = 5 # Order of B-Tree

btree = BTree(t)

# Generate 100 random elements

elements = random.sample(range(1, 1000), 100)

print("Inserting elements:")

for el in elements:

btree.insert(el)

print(f"Inserted {el}")

print("\nTraversing B-Tree:")

btree.traverse(btree.root)

search_value = random.choice(elements)

print(f"\nSearching for {search_value}:")

result = btree.search(search_value)

if result:

print(f"Element {search_value} found.")

else:

print(f"Element {search_value} not found.")

delete_value = random.choice(elements)

print(f"\nDeleting {delete_value}:")

btree.delete(delete_value)

print(f"Deleted {delete_value}.")
 print("\nTraversing B-Tree after deletion:")

btree.traverse(btree.root)

if __name__ == "__main__":

test_btree()

OUTPUT:

Inserting elements:

Inserted 940

Inserted 620

Inserted 2

Inserted 175

Inserted 365

Inserted 367

Inserted 380

Inserted 315

Inserted 674

Inserted 833

Inserted 855

Inserted 188

Inserted 437

Inserted 245

Inserted 484

Inserted 482

Inserted 941

Inserted 737

Inserted 130

Inserted 336

Inserted 578

Inserted 707
Traversing B-Tree:

Level 0 : [484]

Level 1 : [130, 164, 188, 279, 367, 424]

Level 2 : [2, 11, 32, 40, 54, 67, 73, 84, 102]

Level 2 : [136, 148, 152, 160, 163]

Searching for 367:

Element 367 found.

Deleting 279:

Deleted 279.

Traversing B-Tree after deletion:

Level 0 : [484]

Level 1 : [130, 164, 188, 271, 367, 424]

Level 2 : [2, 11, 32, 40, 54, 67, 73, 84, 102]

Level 2 : [136, 148, 152, 160, 163]

Level 2 : [836, 848, 855, 859, 865, 868, 889, 908, 922]

Level 2 : [940, 941, 943, 963, 964, 973]

3.Construct Min and Max Heap using arrays, delete any element and display the
content of the Heap.

MIN HEAP

To implement a Min Heap using arrays in Python, you need to manage heap operations such as
insertion, deletion, and displaying the heap. The Min Heap is a binary heap where the smallest
element is at the root, and each parent node is less than or equal to its child nodes.

Here’s a detailed Python program that includes:

 1. Inserting elements into the Min Heap.
2. Deleting the minimum element (root).
3. Deleting any arbitrary element.
4. Displaying the content of the heap.

class MinHeap:
def __init__(self):
self.heap = []

def parent(self, index):

return (index - 1) // 2

def left_child(self, index):

return 2 * index + 1

def right_child(self, index):

return 2 * index + 2

def insert(self, key):

self.heap.append(key)
self._heapify_up(len(self.heap) - 1)

def _heapify_up(self, index):

parent = self.parent(index)
if index > 0 and self.heap[index] < self.heap[parent]:
self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
self._heapify_up(parent)

def extract_min(self):
if len(self.heap) == 0:
raise IndexError("Heap is empty")
min_value = self.heap[0]
last_value = self.heap.pop()
if len(self.heap) > 0:
self.heap[0] = last_value
self._heapify_down(0)
return min_value

def _heapify_down(self, index):

smallest = index
left = self.left_child(index)
right = self.right_child(index)
 if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
smallest = left

if right < len(self.heap) and self.heap[right] < self.heap[smallest]:

smallest = right

if smallest != index:
self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
self._heapify_down(smallest)

def delete(self, key):

if len(self.heap) == 0:
raise IndexError("Heap is empty")

# Find the index of the element to be deleted

try:
index = self.heap.index(key)
except ValueError:
raise ValueError("Element not found in the heap")

# Replace it with the last element and remove the last element
self.heap[index] = self.heap.pop()

# Restore the heap property

if index < len(self.heap):
self._heapify_down(index)
self._heapify_up(index)

def display(self):
print("Min Heap:", self.heap)

def main():
min_heap = MinHeap()

# Insert elements into the Min Heap

min_heap.insert(10)
min_heap.insert(5)
min_heap.insert(15)
min_heap.insert(2)
min_heap.insert(8)
 print("Min Heap after inserts:")
min_heap.display()

# Extract the minimum element

print("Extracted Min:", min_heap.extract_min())
print("Min Heap after extracting min:")
min_heap.display()

# Delete a specific element

min_heap.delete(15)
print("Min Heap after deleting element 15:")
min_heap.display()

if __name__ == "__main__":
main()

OUTPUT

Min Heap after inserts:

Min Heap: [2, 5, 15, 10, 8]
Extracted Min: 2
Min Heap after extracting min:
Min Heap: [5, 8, 15, 10]
Min Heap after deleting element 15:
Min Heap: [5, 8, 10]

MAX HEAP

To implement a Max Heap using arrays in Python, you need to handle operations such as
insertion, deletion of arbitrary elements, and displaying the heap contents. A Max Heap is a
binary heap where each parent node is greater than or equal to its child nodes, and the largest
element is at the root.

Here's a Python program that covers:

1. Inserting elements into the Max Heap.

2. Deleting any arbitrary element.
3. Displaying the content of the heap.

class MaxHeap:
def __init__(self):

self.heap = []

def parent(self, index):

return (index - 1) // 2

def left_child(self, index):

return 2 * index + 1

def right_child(self, index):

return 2 * index + 2

def insert(self, key):

self.heap.append(key)

self._heapify_up(len(self.heap) - 1)

def _heapify_up(self, index):

parent = self.parent(index)

if index > 0 and self.heap[index] > self.heap[parent]:

self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]

self._heapify_up(parent)

def extract_max(self):

if len(self.heap) == 0:

raise IndexError("Heap is empty")

max_value = self.heap[0]

last_value = self.heap.pop()

if len(self.heap) > 0:

self.heap[0] = last_value
 self._heapify_down(0)

return max_value

def _heapify_down(self, index):

largest = index

left = self.left_child(index)

right = self.right_child(index)

if left < len(self.heap) and self.heap[left] > self.heap[largest]:

largest = left

if right < len(self.heap) and self.heap[right] > self.heap[largest]:

largest = right

if largest != index:

self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]

self._heapify_down(largest)

def delete(self, key):

if len(self.heap) == 0:

raise IndexError("Heap is empty")

# Find the index of the element to be deleted

try:

index = self.heap.index(key)

except ValueError:

raise ValueError("Element not found in the heap")

# Replace it with the last element and remove the last element
 self.heap[index] = self.heap.pop()

# Restore the heap property

if index < len(self.heap):

self._heapify_down(index)

self._heapify_up(index)

def display(self):

print("Max Heap:", self.heap)

def main():

max_heap = MaxHeap()

# Insert elements into the Max Heap

max_heap.insert(10)

max_heap.insert(5)

max_heap.insert(15)

max_heap.insert(20)

max_heap.insert(8)

print("Max Heap after inserts:")

max_heap.display()

# Extract the maximum element

print("Extracted Max:", max_heap.extract_max())

print("Max Heap after extracting max:")

max_heap.display()

# Delete a specific element

 max_heap.delete(15)

print("Max Heap after deleting element 15:")

max_heap.display()

if __name__ == "__main__":

main()

OUTPUT

Max Heap after inserts:

Max Heap: [20, 15, 10, 5, 8]

Extracted Max: 20

Max Heap after extracting max:

Max Heap: [15, 8, 10, 5]

Max Heap after deleting element 15:

Max Heap: [10, 8, 5]

4. Implement BFT and DFT for given graph, when graph is represented by
Adjacency Matrix

Adjacency Lists

Adjacency Matrix

To implement Breadth-First Traversal (BFT) and Depth-First Traversal (DFT) for a graph
represented by an adjacency matrix, we'll create a Python program that includes the following
steps:

1. Represent the Graph: Use an adjacency matrix to represent the graph.

2. Implement Breadth-First Traversal (BFT): Traverse the graph level by level using a
queue.
3. Implement Depth-First Traversal (DFT): Traverse the graph deeply using a stack (or
recursive approach).
from collections import deque

class Graph:

def __init__(self, adjacency_matrix):

self.adj_matrix = adjacency_matrix

self.num_vertices = len(adjacency_matrix)

def bfs(self, start_vertex):

visited = [False] * self.num_vertices

queue = deque([start_vertex])

visited[start_vertex] = True

result = []

while queue:

vertex = queue.popleft()

result.append(vertex)

for i in range(self.num_vertices):

if self.adj_matrix[vertex][i] == 1 and not visited[i]:

queue.append(i)

visited[i] = True

return result

def dfs(self, start_vertex):

visited = [False] * self.num_vertices

result = []

self._dfs_util(start_vertex, visited, result)

return result
 def _dfs_util(self, vertex, visited, result):

visited[vertex] = True

result.append(vertex)

for i in range(self.num_vertices):

if self.adj_matrix[vertex][i] == 1 and not visited[i]:

self._dfs_util(i, visited, result)

def main():

# Example adjacency matrix for a graph

adj_matrix = [

[0, 1, 1, 0],

[1, 0, 1, 1],

[1, 1, 0, 1],

[0, 1, 1, 0]

graph = Graph(adj_matrix)

start_vertex = 0

# Breadth-First Traversal

print("Breadth-First Traversal (BFT) starting from vertex", start_vertex, ":")

print(graph.bfs(start_vertex))

# Depth-First Traversal

print("Depth-First Traversal (DFT) starting from vertex", start_vertex, ":")

print(graph.dfs(start_vertex))

if __name__ == "__main__":
 main()

OUTPUT

Breadth-First Traversal (BFT) starting from vertex 0 :

[0, 1, 2, 3]

Depth-First Traversal (DFT) starting from vertex 0 :

[0, 1, 2, 3]

ADJACENCY LIST

from collections import deque

class GraphList:

def __init__(self, adjacency_list):

self.adj_list = adjacency_list

self.num_vertices = len(adjacency_list)

def bfs(self, start_vertex):

visited = [False] * self.num_vertices

queue = deque([start_vertex])

visited[start_vertex] = True

result = []

while queue:

vertex = queue.popleft()

result.append(vertex)

for neighbor in self.adj_list[vertex]:

 if not visited[neighbor]:

queue.append(neighbor)

visited[neighbor] = True

return result

def dfs(self, start_vertex):

visited = [False] * self.num_vertices

result = []

self._dfs_util(start_vertex, visited, result)

return result

def _dfs_util(self, vertex, visited, result):

visited[vertex] = True

result.append(vertex)

for neighbor in self.adj_list[vertex]:

if not visited[neighbor]:

self._dfs_util(neighbor, visited, result)

def main_list():

# Example adjacency list for a graph

adj_list = {

0: [1, 2],

1: [0, 2, 3],

2: [0, 1, 3],

3: [1, 2]

graph = GraphList(adj_list)
 start_vertex = 0

# Breadth-First Traversal

print("Breadth-First Traversal (BFT) starting from vertex", start_vertex, ":")

print(graph.bfs(start_vertex))

# Depth-First Traversal

print("Depth-First Traversal (DFT) starting from vertex", start_vertex, ":")

print(graph.dfs(start_vertex))

if __name__ == "__main__":

main_list()

OUTPUT:

Breadth-First Traversal (BFT) starting from vertex 0 :

[0, 1, 2, 3]

Depth-First Traversal (DFT) starting from vertex 0 :

[0, 1, 2, 3]
5. Write a program for finding the biconnected components in a given graph

from collections import defaultdict, deque

class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_list = defaultdict(list)

def add_edge(self, u, v):

self.adj_list[u].append(v)
self.adj_list[v].append(u)

def biconnected_components(self):
# Initialize required variables
time = [0]
stack = []
bccs = []
visited = set()
disc = {}
low = {}
parent = {}

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

for v in self.adj_list[u]:
if v not in visited:
stack.append((u, v)) # Store the edge in stack
parent[v] = u
children += 1

dfs(v)

# Check if the subtree rooted at v has a connection back to one of ancestors of u

low[u] = min(low[u], low[v])

# If the lowest vertex reachable from subtree under v is below u in DFS tree, then u-v is a
bridge
if low[v] >= disc[u]:
bcc = []
while stack[-1] != (u, v):
bcc.append(stack.pop())
bcc.append(stack.pop())
bccs.append(bcc)

elif v != parent.get(u, None) and disc[v] < disc[u]:

 stack.append((u, v)) # Store the back edge in stack
low[u] = min(low[u], disc[v])

# Initialize DFS traversal

for i in range(self.vertices):
if i not in visited:
dfs(i)

# Check for remaining edges in stack

if stack:
bcc = []
while stack:
bcc.append(stack.pop())
bccs.append(bcc)

return bccs

def main():
# Example graph
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 4)

print("Biconnected Components:")
bccs = g.biconnected_components()
for i, bcc in enumerate(bccs):
print(f"Biconnected Component {i + 1}: {bcc}")

if __name__ == "__main__":
main()

OUTPUT

Biconnected Components:
Biconnected Component 1: [(3, 1), (4, 3), (2, 4), (2, 0), (1, 2), (0, 1)]