图———最小生成树——普利姆算法

川长思鸟来 2023-05-29 15:26 17阅读 0赞

普利姆算法：  
GV表示图的点集， GW 表示图的边集。  
V表示最小生成树中的点集合， W表示最小生成树的边集合。

①从某个u点开始， 将u纳入V集合中。  
②选取最近没在V集合的点y， 将其纳入V集合中， 加上对应边的权值(对应边 e（x，y）， x∈V， y∈ 加入到 集合W中)。  
③然后重复②， 直到所有的点都被纳入V集合中。

##### 代码一： #####

#include<bits/stdc++.h>
    #define maxn 103
    #define inf 0x3f3f3f
    using namespace std;
    int mp[maxn][maxn];
    int n, m; // 点 边
    
    void init() // 初始化图
    { 
        memset(mp, inf, sizeof(mp));
    }
    
    void create() // 创建图
    { 
        int i, u, v, w;
        for(i = 0; i < m; i++)
        { 
            scanf("%d %d %d", &u, &v, &w);
            if(mp[u][v] > w)
            { 
                mp[u][v] = w;
                mp[v][u] = w;
            }
        }
    }
    struct Node
    { 
        int w; // lowcost 对应边的花费
        int v;//距离该点最近的点
    } close[maxn]; // closeEdge数组， 该数组用于寻找最近的没在V集合的点
    
    void Prim(int u)
    { 
        int sum = 0;
        int k = -1, low = inf;// k 最近的那个点 ， low 对应的全职
    
        close[u].w = -1 ; //表示该点已经被纳入 V集合中
        for(int i = 1; i <= n; i++) // 第一遍 更新一下close数组
        { 
            if(i!= u)
            { 
                close[i].v = u;
                close[i].w = mp[u][i];
                if(close[i].w < low)
                { 
                    low = close[i].w;
                    k = i;
                }
            }
        }
    
        if(k != -1)sum+=low;
        close[k].w = -1; // 将其纳入 V数组中
    
        int s = k;
        for(int j = 1; j < n-1; j++) // 将其他点纳入 V集合中
        { 
            low = inf;
            k = -1;
            for(int i = 1; i <= n; i++)
            { 
            // 每次维护数组
                if(close[i].w!= -1)
                { 
                    if(mp[s][i] != inf&& close[i].w > mp[s][i])// 如果相邻
                    { 
                        close[i].w = mp[s][i];
                        close[i].v = s;
                    }
                    if(close[i].w < low)
                    { 
                        low = close[i].w;
                        k = i;
                    }
                }
            }
            sum+=low;
    
            close[k].w = -1;
            s = k;
    
        }
        printf("%d\n", sum);
    
    }
    
    int main()
    { 
        while(~scanf("%d %d", &n, &m))
        { 
            init();
            create();
            Prim(1);
    
        }
    
    
        return 0;
    }

##### 代码二： #####

#include <stdio.h>
    #include <stdlib.h>
    #include<string.h>
    #define maxn 1005
    #define inf 0x3f3f3f
    int mp[maxn][maxn];// 邻接矩阵存图
    int n, m;
    void init()// 初始化函数
    { 
        memset(mp, inf, sizeof(mp));
    }
    void build()// 建图函数
    { 
        int i;
        for(i = 0;i < m;i++)
        { 
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            if(mp[u][v] > w)
            { 
                mp[u][v] = w;
                mp[v][u] = w;
            }
        }
    }
    struct node
    { 
        int flag;// 标记该点是否已经被纳入V集合中
        int d;// V集合中的点到达该点的最小距离
        int u;// V集合中到达该点的点
    }low[maxn];
    
    int Prim(int S)
    { 
        // 初始化
        int sum = 0;
        int i;
        for(i = 1;i <= n;i++)
        { 
            low[i].flag = 0;
            low[i].d = mp[S][i];
            low[i].u = S;
        }
        low[S].flag = 1;
    
        // 将其他点纳入V集合中
        int j;
        for(i = 0;i < n-1;i++)
        { 
            int u = -1;// u表示要纳入的点
            int min = inf;// min 表示 距离
            
            for(j = 1;j <= n;j++)// 找一个最近的点
            { 
                if(low[j].flag == 0&& low[j].d < min)
                { 
                    u = j;
                    min = low[j].d;
                }
    
            }
            if(u == -1)break;
            
            low[u].flag = 1;// 纳入
            sum+=min;// 加上数值
    
            for(j = 1;j <= n;j++)// 更新一下数组
            { 
                if(low[j].flag== 0 && low[j].d > mp[u][j])
                { 
                    low[j].d = mp[u][j];
                }
            }
    
        }
    
        for(i = 1;i <= n;i++)// 判断是否连通
        { 
            if(low[i].flag == 0)return -1;
        }
    
        return sum;
    }