13.
Write a program to find the minimum spanning tree of a given graph
using Prim's algorithm.
import sys
def min_key(key, mst_set, n):
min_value = sys.maxsize
min_index = -1
for v in range(n):
if not mst_set[v] and key[v] < min_value:
min_value = key[v]
min_index = v
return min_index
def print_mst(parent, c, n):
total_weight = 0
print("\nEdge Weight")
for i in range(1, n):
print(f"{parent[i] + 1} - {i + 1} {c[i][parent[i]]}")
total_weight += c[i][parent[i]]
print(f"\nTotal cost of the minimum spanning tree: {total_weight}")
def prim_mst(c, n):
parent = [-1] * n
key = [sys.maxsize] * n
mst_set = [False] * n
key[0] = 0
for _ in range(n):
u = min_key(key, mst_set, n)
mst_set[u] = True
for v in range(n):
if 0 < c[u][v] < key[v] and not mst_set[v]:
key[v] = c[u][v]
parent[v] = u
print_mst(parent, c, n)
n = int(input("Enter the number of vertices: "))
print("Enter the cost adjacency matrix:")
c = []
for i in range(n):
c.append(list(map(int, input().split())))
prim_mst(c, n)
14. (a)Write a program to obtain the topological ordering of vertices in a
given diagraph.
from collections import deque
def topological_sort(n, adj_matrix):
indegree = [0] * n
queue = deque()
topo_order = []
for i in range(n):
for j in range(n):
if adj_matrix[i][j] == 1:
indegree[j] += 1
for i in range(n):
if indegree[i] == 0:
queue.append(i)
print("\nThe topological order is:", end=" ")
while queue:
node = queue.popleft()
topo_order.append(node + 1)
print(f"{node + 1}", end=" ")
for i in range(n):
if adj_matrix[node][i] == 1:
indegree[i] -= 1
if indegree[i] == 0:
queue.append(i)
print()
def main():
n = int(input("Enter the number of vertices: "))
print("Enter the adjacency matrix (row by row):")
adj_matrix = []
for i in range(n):
row = list(map(int, input().split()))
adj_matrix.append(row)
topological_sort(n, adj_matrix)
if __name__ == "__main__":
main()
14) (b) Write a program to compute closure of a given directed graph using
Warshall's algorithm.
def warshalls(adj_matrix, n):
for k in range(n):
for i in range(n):
for j in range(n):
adj_matrix[i][j] = adj_matrix[i][j] or (adj_matrix[i][k] and
adj_matrix[k][j])
print("\nThe transitive closure of the graph is:")
for row in adj_matrix:
print(" ".join(map(str, row))) # Printing in a structured format
def main():
n = int(input("Enter the number of vertices: "))
print("Enter the adjacency matrix (row by row, space-separated):")
adj_matrix = []
for _ in range(n):
row = list(map(int, input().split()))
adj_matrix.append(row)
warshalls(adj_matrix, n)
if __name__ == "__main__":
main()
15.Write a program to find a subset of a given set S =(s1,s2,....,sn) of n positive
integers whose sum is equal to a given positive integer d.
def sum_of_subsets(s, k, r):
global count, x, w, d
x[k] = 1
if s + w[k] == d: # If a valid subset is found
count += 1
print(f"\nSubset {count} = ", end="")
for i in range(k + 1):
if x[i]:
print(w[i], end=" ")
print()
elif s + w[k] + w[k + 1] <= d:
sum_of_subsets(s + w[k], k + 1, r - w[k])
if (s + r - w[k] >= d) and (s + w[k + 1] <= d):
x[k] = 0
sum_of_subsets(s, k + 1, r - w[k])
def main():
global w, x, d, count
w = []
x = [0] * 100
count = 0
n = int(input("Enter the number of elements: "))
print("Enter the elements in ascending order:")
for _ in range(n):
w.append(int(input()))
d = int(input("Enter the target sum: "))
total_sum = sum(w)
if total_sum < d or w[0] > d:
print("\nNo subset possible\n")
else:
sum_of_subsets(0, 0, total_sum)
if __name__ == "__main__":
main()
