# Function to find the Minimum Spanning Tree using Kruskal's algorithm
kruskal_mst <- function(graph) {
  num_vertices <- nrow(graph)
  
  # Create a list to store the MST edges
  mst_edges <- list()
  
  # Create a vector to track the parent of each vertex in a forest
  parent <- 1:num_vertices
  
  # Helper function to find the root of a set (connected component)
  find_root <- function(x) {
    if (x != parent[x]) {
      parent[x] <- find_root(parent[x])
    }
    return(parent[x])
  }
  
  # Sort the edges by weight
  edges <- data.frame(
    from = rep(1:num_vertices, each = num_vertices),
    to = rep(1:num_vertices, times = num_vertices),
    weight = as.vector(graph)
  )
  edges <- edges[order(edges$weight), ]
  
  # Iterate through sorted edges
  for (i in 1:(num_vertices - 1)) {
    edge <- edges[i, ]
    root_from <- find_root(edge$from)
    root_to <- find_root(edge$to)
    
    # If adding the edge doesn't create a cycle, include it in the MST
    if (root_from != root_to) {
      mst_edges <- c(mst_edges, list(edge))
      parent[root_from] <- root_to
    }
  }
  
  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 <- kruskal_mst(graph)

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