Prim's minimum spanning tree

Given a connected, weighted, undirected graph represented by an adjacency matrix, find a minimum spanning tree starting from vertex 0 and return its selected edges.

Hint

Maintain a key value for each vertex, its parent in the tree, and a flag indicating whether it is already in the tree. Start vertex 0 with key 0. Repeatedly choose the unused vertex with the smallest key, add it to the tree, and update the key and parent of each unused neighbor when a lighter edge is found. Return the parent edge for every vertex after vertex 0.

• Determine the arbitrary starting vertex.
• Select an edge connecting the tree vertex and fringe vertex having the minimum weight.
• Add the chosen edge to MST if it doesn’t form any closed cycle.
• Repeating steps 2 and 3 until the fringe vertices (vertices not included in MST) remain.

• Python
• Javascript
•  Run

def minKey(graph, key, mst):
  mn = float("inf")
  for v in range(len(graph)):
    if key[v] < mn and mst[v] == False:
      mn = key[v]
      mn_index = v

  return mn_index

def prim(graph):
  result = []

  V = len(graph)
  parent = [None] * V
  key = [float("inf")] * V
  mst = [False] * V
  
  key[0] = 0
  parent[0] = -1

  for cout in range(V):
    u = minKey(graph, key, mst)
    mst[u] = True
    for v in range(V):
      if graph[u][v] > 0 and mst[v] == False and key[v] > graph[u][v]:
        key[v] = graph[u][v]
        parent[v] = u

  for i in range(1, len(graph)):
    result.append([parent[i], i, graph[parent[i]][i]])
  
  return result

graph = [
  [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]
]

print(prim(graph))

//=include prim.js