最小生成树又称最小权重生成树是连接的，边缘加权的无向图的边缘的子集。
该子集将所有顶点连接在一起，没有任何循环并且具有最小可能的总边权重。

一个图可以有多个以上的最小生成树。
但是，对于同一棵树的不同MST，总成本将是相同的。

Prim算法

Prim的算法是一种贪婪算法，可以找到加权无向图的MST。

该算法通过从任意起始顶点一次建立一个MST来进行。
在每个步骤中，它都是最经济高效的选择。
即，它局部优化以实现全局最优。

Prim算法的工作方式如下：

• 使用随机顶点(初始顶点)初始化最小生成树。

• 找到将树连接到新顶点的所有边，找到最小值，然后将其添加到树中(贪婪的选择)。

• 继续重复步骤2，直到得到最小的生成树(直到所有顶点都达到为止)。

我们可以看一个例子来了解Prim算法的工作原理。

令加权无向图如下：

我们选择0作为初始顶点。

下一步，我们从与MST连接的所有节点中选择最小值。

在随后的每个阶段，我们都找到将树连接到新顶点的最小成本边。

• 边缘：0-1
• 边缘：1-4
• 边缘：4-2
• 边缘：1-3

使用4条边线，我们已经连接了所有5个节点。
最小生成树的代价是所有边缘权重的总和。

在此示例中，它是：

4+1+6+2 = 13

Prim的算法Java代码

Java实现如下。

Graph类的代码：

package com.theitroad;
import java.util.*;
public class Graph
{
  
    //Representation of the graph 
    
  private static int infinite = 9999999;

  int[][]  LinkCost; //graph matrix
  int      num_nodes; //number of nodes 
  
  //constructor takes in a matrix as its input 
  Graph(int[][] mat)
  {
      int i, j;

      num_nodes = mat.length;

      LinkCost = new int[num_nodes][num_nodes];

      //copying the weights to LinkCost matrix
      for ( i=0; i < num_nodes; i++)
      {
          for ( j=0; j < num_nodes; j++)
          {
              LinkCost[i][j] = mat[i][j];

              if ( LinkCost[i][j] == 0 )
                  LinkCost[i][j] = infinite;
          }
      }
  }

  //function to get the nodes that are unreached
  public int unReached(boolean[] r)
  {
      boolean done = true;

      for ( int i = 0; i < r.length; i++ )
          if ( r[i] == false )
              return i;

      return -1;
  }

  public void Prim( )
  {
      int i, j, k, x, y;

      boolean[] Reached = new boolean[num_nodes];	//array to keep track of the reached nodes
      int[] predNode = new int[num_nodes];		//array to maintain min cost edge

//starting vertex
      Reached[0] = true;
      //setting other vertices as unreached
      for ( k = 1; k < num_nodes; k++ )
      {
          Reached[k] = false;
      }

      predNode[0] = 0;      //No edge for node 0

      printCoveredNodes( Reached );

   //we iterate for n-1 nodes that haven't been reached yet
      for (k = 1; k < num_nodes; k++)
      {
          x = y = 0;

          for ( i = 0; i < num_nodes; i++ )
              for ( j = 0; j < num_nodes; j++ )
              {
//update the MST with the minimum cost Link
                  if ( Reached[i] && !Reached[j] &&
                          LinkCost[i][j] < LinkCost[x][y] )
                  {
                      x = i;
                      y = j;
                  }
              }

          System.out.println("Next selected edge: (" +
                  + x + "," +
                  + y + ")" +
                  " cost = " + LinkCost[x][y]);

          predNode[y] = x;          //add the min cost link to predNode
          Reached[y] = true;

          printCoveredNodes( Reached );
          System.out.println();
      }

      printMinCostEdges( predNode );
  }
  //function to print the edges of spanning tree
  void printMinCostEdges( int[] a )
  {
 System.out.println("Edges in MST: ");
      for ( int i = 0; i < num_nodes; i++ )
          System.out.println( a[i] + " --> " + i );
  }

 
 void printCoveredNodes(boolean[] Reached )
  {
      System.out.print("Covered Nodes = ");
      for (int i = 0; i < Reached.length; i++ )
          if ( Reached[i] )
              System.out.print( i + " ");
      System.out.println();
  }

}

主类：

package com.theitroad;

public class Main {

  public static void main(String[] args) {
      int[][] conn = {{0, 4, 0, 0, 5},
              {4, 0, 3, 6, 1},
              {0, 3, 0, 6, 2},
              {0, 6, 6, 0, 7},
              {5, 1, 2, 7, 0},
      };

      Graph G = new Graph(conn);

      G.Prim();
  }
}