prim最小生成树

佚名 6年前 (2019-04-22) 随笔 883人围观抢沙发百度已收录

prim和DIjkstra相似，都使用了贪心策略，加一些限制条件。

prim每次会找出尽量小的那个边，将其加入到树中，最终使得生成树长大。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

树中有n-1个节点时或者剩下的所有边都是INF，算法结束。

（如果剩下的所有边都是INF，那么最小生成树不存在）。

我们这里使用邻接矩阵来实现prim算法。

初始化：

　　定义dist[]数组，保存每个节点到树的最小距离，当节点在树中时更新为0。

　　先找到一个根节点A，将其加入树中， dist[A] = 0

（1）从还没加入到树中的节点中选择一条到树距离最短的i，将其加入树中：

　　　　dist[i] = 0

（2）节点 i 加入树可能导致其他节点到树的最短距离改变，所以我们对与 i 节点相连的并且不在树中的节点最短距离进行更新

　　　　如果G[i][j] < dist[j]

　　　　　　dist[j] = G[i][j]

（3）循环直到找出了n-1条边或者剩下的边中都是INF，算法结束。

typedef int Vertex;

typedef int Weight;

typedef struct MyGraph
{
    int v, e;
    Weight g[MaxVertexNum][MaxVertexNum];
}MyGraph;

void Prim(MyGraph& G, Vertex u)
{
    int dist[G.v];
    
    //初始化 
    for(int i = 0; i < G.v; i++)
    {
        if(G.g[u][i] == -1)
            dist[i] = INF;
        else
            dist[i] = G.g[u][i];
    }
    
    int count = 1;
    for(; count < G.v; count++)
    {
        int mmin = INF;
        int k = -1;
        //找到最小距离 
        for(int i = 0; i < G.v; i++)
        {
            if(dist[i] != 0 && mmin > dist[i])
            {
                mmin = dist[i];
                k = i;
            }
        }
        //若找不到则代表不能得到生成树 
        if(k == -1)
            return false;
            
        //将最小节点加入
        dist[k] = 0; 
        count++;
        //更新dist数组
        for(int i = 0; i < G.v; i++)
        {
            if(dist[i] != 0 && dist[i] > G.g[k][i])
                dist[i] = G.g[k][i];
        }
    }
    
}