Prim's algorithm for finding the minimum spanning tree relies on a greedy approach. A greedy approach is defined as an algorithm paradigm where we try to find the global optimal solution by considering the local optimal solution at each stage. We will explore greedy algorithms in Chapter 11, Solve Problems with Advanced Techniques. In a greedy approach, the algorithm creates subsets of edges and finds out the least costly one from the subset of edges. This subset of edges will include all vertices. It starts from an arbitrary position and grows the tree one vertex at a time by choosing the cheapest possible connection between the vertices. Let's consider the following graph:

Now, we will apply a very basic version of Prim's algorithm to get the minimum spanning tree as well as the minimum cost or weight of the edges. The graph will look like this as an adjacency matrix:

$G = [ 
    [0, 3, 1, 6, 0, 0], 
    [3, 0, 5, 0, 3, 0], 
    [1, 5, 0, 5, 6, 4], 
    [6, 0, 5, 0, 0, 2], 
    [0, 3, 6, 0, 0, 6], 
    [0, 0, 4, 2, 6, 0] 
]; 

Now, we will implement the algorithm for Prim's minimum spanning tree. We are assuming that we are going to start from vertex 0 to find out the whole spanning tree, so we will just pass the graph adjacency matrix in the function, and it will display the connecting edges for the spanning tree along with the minimum cost:

function primMST(array $graph) { 
    $parent = [];   // Array to store the MST 
    $key = [];     // used to pick minimum weight edge         
    $visited = [];   // set of vertices not yet included in MST 
    $len = count($graph); 

    // Initialize all keys as MAX 
    for ($i = 0; $i < $len; $i++) { 
      $key[$i] = PHP_INT_MAX; 
      $visited[$i] = false; 
    } 

    $key[0] = 0; 
    $parent[0] = -1; 

    // The MST will have V vertices 
    for ($count = 0; $count < $len - 1; $count++) { 
  // Pick the minimum key vertex 
  $minValue = PHP_INT_MAX; 
  $minIndex = -1; 

  foreach (array_keys($graph) as $v) { 
      if ($visited[$v] == false && $key[$v] < $minValue) { 
        $minValue = $key[$v]; 
        $minIndex = $v; 
      } 
  } 

  $u = $minIndex; 

  // Add the picked vertex to the MST Set 
  $visited[$u] = true; 

  for ($v = 0; $v < $len; $v++) { 
      if ($graph[$u][$v] != 0 && $visited[$v] == false && 
        $graph[$u][$v] < $key[$v]) { 
          $parent[$v] = $u; 
          $key[$v] = $graph[$u][$v]; 
      } 
  } 
    } 

    // Print MST 
    echo "Edge	Weight
"; 
    $minimumCost = 0; 
    for ($i = 1; $i < $len; $i++) { 
      echo $parent[$i] . " - " . $i . "	" . $graph[$i][$parent[$i]] 
         "
"; 
      $minimumCost += $graph[$i][$parent[$i]]; 
    } 
    echo "Minimum cost: $minimumCost 
"; 
} 

Now, if we call the function primMST with our graph $G, the following will be the output and the MST constructed by the algorithm:

Edge    Weight
0 - 1   3
0 - 2   1
5 - 3   2
1 - 4   3
2 - 5   4
Minimum cost: 13

There are other ways to implement Prim's algorithm with the help of a Fibonacci heap, a priority queue, and so on. It is quite similar to Dijkstra's algorithm to find the shortest path. Our implementation has a time complexity of O (V²). Using the binary heap and the Fibonacci heap, we can reduce the complexity significantly.