#.11 Write a program that implements Prim’s algorithm to generate minimum costs panning Tree

import sys

class Graph:
    def __init__(self, vertices):
        self.V = vertices  
        self.graph = []   
    
    def add_edge(self, u, v, weight):
       
        self.graph.append((u, v, weight))
    
    def prim_mst(self):
       
        mst_edges = []
        
       
        adj_matrix = [[0] * self.V for _ in range(self.V)]
        for u, v, weight in self.graph:
            adj_matrix[u][v] = weight
            adj_matrix[v][u] = weight 
        
        key = [sys.maxsize] * self.V
              
        parent = [-1] * self.V
             
        mst_set = [False] * self.V
               
        key[0] = 0
        parent[0] = -1 
        
        for _ in range(self.V):
          
            min_key = sys.maxsize
            min_index = -1
            for v in range(self.V):
                if key[v] < min_key and not mst_set[v]:
                    min_key = key[v]
                    min_index = v
            
        
            mst_set[min_index] = True
            
           
            for v in range(self.V):
                if (adj_matrix[min_index][v] > 0 and not mst_set[v] and
                        adj_matrix[min_index][v] < key[v]):
                    key[v] = adj_matrix[min_index][v]
                    parent[v] = min_index
        
        # Collect the edges in the MST
        for i in range(1, self.V):
            mst_edges.append((parent[i], i, adj_matrix[parent[i]][i]))
        
        return mst_edges

# Example usage
if __name__ == "__main__":
    g = Graph(5)
    g.add_edge(0, 1, 2)
    g.add_edge(0, 3, 6)
    g.add_edge(1, 2, 3)
    g.add_edge(1, 3, 8)
    g.add_edge(1, 4, 5)
    g.add_edge(2, 4, 7)
    g.add_edge(3, 4, 9)

    mst = g.prim_mst()
    print("Edges in the Minimum Spanning Tree:")
    for u, v, weight in mst:
        print(f"{u} -- {v} == {weight}")