Prims

import sys

def prims_algorithm(graph):
n = len(graph)
selected = [False] * n
selected[0] = True
num_edges = 0

print("\nEdge : Weight")

while num_edges < n - 1:
    min_edge = sys.maxsize
    x = 0
    y = 0

    for i in range(n):
        if selected[i]:
            for j in range(n):
                if (not selected[j]) and graph[i][j] != 0:
                    if min_edge > graph[i][j]:
                        min_edge = graph[i][j]
                        x = i
                        y = j

    print(f"{x} - {y} : {graph[x][y]}")
    selected[y] = True
    num_edges += 1

n = int(input("Enter number of vertices: "))
print("Enter the adjacency matrix (use 0 for no connection):")
graph = []

for i in range(n):
row = list(map(int, input(f"Row {i+1}: ").split()))
if len(row) != n:
print("Invalid row length. Please enter", n, "values.")
exit()
graph.append(row)

prims_algorithm(graph)