Prim算法

1.最小生成树算法

1.1定义：边权重和最小的生成树

连通图中的生成树必须满足以下 2 个条件：

  1. 包含连通图中所有的顶点；
  2. 任意两顶点之间有且仅有一条通路；

边的数量 = 顶点数 - 1
image.png

2.算法本质:贪心算法

又贪又好：

  1. "贪" 每一步是最好的
  2. "好" 权重最小的

保证约束：不能有回路，全部边都用上（v-1条）

Prim 算法是通过加点，加上离当前最小树最短距离的点

dist[S] = 0
for(int i = 1;i<=n;i++)
{
  int t = -1;
  for(int j = 1;j<=n;j++)
  {
     if(!vis[j] && (t == -1 || dist[t] > dist[j])) // 找最小距离点
     {
        t = j;
     }
  }
  vis[t] = true; // 加入最小树
  for(int j = 1;j<=n;j++) // 更新临近点距离
  {
     if(w[t][j] != 0 && !vis[j])
      dist[j] = min(dist[j],w[t][j]);
  }
}