# Function to find the Minimum Spanning Tree using Prim's algorithm
prim_mst <- function(graph) {
  num_vertices <- nrow(graph)
  
  # Initialize arrays to track which vertices are included in the MST
  included <- rep(FALSE, num_vertices)
  
  # Initialize an array to store the MST edges
  mst_edges <- list()
  
  # Mark the first vertex as included
  included[1] <- TRUE
  
  while (sum(included) < num_vertices) {
    min_edge <- list(weight = Inf)
    
    for (i in 1:num_vertices) {
      if (included[i]) {
        for (j in 1:num_vertices) {
          if (!included[j] && graph[i, j] < min_edge$weight) {
            min_edge$weight <- graph[i, j]
            min_edge$from <- i
            min_edge$to <- j
          }
        }
      }
    }
    
    included[min_edge$to] <- TRUE
    mst_edges <- c(mst_edges, list(min_edge))
  }
  
  return(mst_edges)
}

# Example usage
# Create an adjacency matrix representing a graph (replace this with your own graph)
graph <- matrix(c(
  0, 2, 0, 6, 0,
  2, 0, 3, 8, 5,
  0, 3, 0, 0, 7,
  6, 8, 0, 0, 9,
  0, 5, 7, 9, 0
), nrow = 5)

mst <- prim_mst(graph)

cat("Minimum Spanning Tree Edges:\n")
for (edge in mst) {
  cat("From: ", edge$from, " To: ", edge$to, " Weight: ", edge$weight, "\n")
}