Prim算法

$$Prim算法$$

功能

$Prim$算法一般就是用来求一个图的$最小生成树$的。

$最小生成树：$在一个图中，①.连通所有的点，②.并且让所有边的权值总和最小。

算法流程

$集合内和集合外$：
所谓的集合内是指已经完成了更新放入到最后最小生成树中的节点，集合外是还在等待加入最小生成树的节点。

$整体流程：$

dist[i] <-- +∞
for(int i = 0 ; i < n ; i++)
{
    找到集合外距离集合最近的点m;
    t = m;
    st[t] = true;   //翻转一下标记变量，意为t已经加入到集合中
    使用t去更新其他点到集合的距离
}

细节解析

1. $dist[N]$：这里的$dist[N]$数组，含义是$集合外的点到集合最近的距离$。也就是说集合外一点，从所有到集合内部的边中选择一条权值最小的边作为该点的$dist[N]$。
2. 寻找集合外一点到集合最小距离的点的时候，因为图本身可能是不连通的，所以找出来的距离可能是$\infty$，需要一个特判：

if(dist[t] == 0x3f3f3f3f)
    return 0x3f3f3f3f;

3. $数据更新：$

for(int j = 1 ; j <= n ; j++)
    dist[j] = min(dist[j],g[t][j]);

遍历每一个点进行更新的时候，此时要注意$dist[N]$数组的含义了，是指到集合最小的距离，所以$dist[j]$的最终取值是在$dist[j]$和$g[t][j]$之间来抉择。

完整代码

#include 
#include 
#include 
#include 

using namespace std;

const int N = 510;

int n,m;
int g[N][N];
int dist[N];        //表示集合外面一个点到集合内部最短的距离
bool st[N];

int Prim()
{
    memset(dist,0x3f,sizeof(dist));     //初始化dist数组
    
    dist[1] = 0;
    
    int res = 0;
    
    for(int i = 0 ; i < n ; i++)        //n个点循环一次确定好一个点将其加入集合
    {
        int t = -1;         //用来存储集合外的到集合距离最短的点
        
        for(int j = 1 ; j <= n ; j++)       //寻找符合t条件的点
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
                
        
        if(dist[t] == 0x3f3f3f3f)   //很有可能图不是连通图，这样就算是最近的点距离也是无穷大
            return 0x3f3f3f3f;
            
        res += dist[t];     //计算路径综合
        
        st[t] = true;       //表示这个点加入到了集合中
        
        for(int j = 1 ; j <= n ; j++)
            dist[j] = min(dist[j],g[t][j]);     //最短距离更新
    }
    
    return res;
}

int main ()
{
    cin >> n >> m;
    
    memset(g,0x3f,sizeof(g));
    
    while(m--)
    {
        int a,b,c;
        
        cin >> a >> b >>c;
        
        g[a][b] = g[b][a] = min(g[a][b],c);     //可能有重边取最小值的边作为目标边
        
    }
    
    int t = Prim();
    
    
    if(t == 0x3f3f3f3f)
        puts("impossible");
    else 
        cout << t << endl;
        
    return 0;
}