专栏首页图灵技术域最小生成树之Prim贪心算法

最小生成树之Prim贪心算法

设图G顶点集合为U,首先任意选择图G中的一点作为起始点a,将该点加入集合V,再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小,此时将b点也加入集合V;以此类推,现在的集合V={a,b},再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小,此时将c点加入集合V,直至所有顶点全部被加入V,此时就构建出了一颗MST。因为有N个顶点,所以该MST就有N-1条边,每一次向集合V中加入一个点,就意味着找到一条MST的边。

代码:

C++

#include<iostream>  
#include<fstream>  
using  namespace std;  
  
#define MAX 100  
#define MAXCOST 0x7fffffff  
  
int graph[MAX][MAX];  
  
int prim(int graph[][MAX], int n)  
{  
    int lowcost[MAX];  
    int mst[MAX];  
    int i, j, min, minid, sum = 0;  
    for (i = 2; i <= n; i++)  
    {  
        lowcost[i] = graph[1][i];  
        mst[i] = 1;  
    }  
    mst[1] = 0;  
    for (i = 2; i <= n; i++)  
    {  
        min = MAXCOST;  
        minid = 0;  
        for (j = 2; j <= n; j++)  
        {  
            if (lowcost[j] < min && lowcost[j] != 0)  
            {  
                min = lowcost[j];  
                minid = j;  
            }  
        }  
        cout << "V" << mst[minid] << "-V" << minid << "=" << min << endl;  
        sum += min;  
        lowcost[minid] = 0;  
        for (j = 2; j <= n; j++)  
        {  
            if (graph[minid][j] < lowcost[j])  
            {  
                lowcost[j] = graph[minid][j];  
                mst[j] = minid;  
            }  
        }  
    }  
    return sum;  
}  
  
int main()  
{  
    int i, j, k, m, n;  
    int x, y, cost;  
    ifstream in("input.txt");  
    in >> m >> n;//m=顶点的个数,n=边的个数  
    //初始化图G  
    for (i = 1; i <= m; i++)  
    {  
        for (j = 1; j <= m; j++)  
        {  
            graph[i][j] = MAXCOST;  
        }  
    }  
    //构建图G  
    for (k = 1; k <= n; k++)  
    {  
        in >> i >> j >> cost;  
        graph[i][j] = cost;  
        graph[j][i] = cost;  
    }  
    //求解最小生成树  
    cost = prim(graph, m);  
    //输出最小权值和  
    cout << "最小权值和=" << cost << endl;  
    system("pause");  
    return 0;  
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Prim算法-最小生成树

    基本思想: 1 置S={1} 2 只要S是V的真子集就做如下的贪心选择:   选取满足条件的i ,i属于S,j输入V-S,且c[i][j]最小的边,并将定点j加...

    用户1154259
  • 最小生成树之Prim算法和Kruskal算法

    一个连通图可能有多棵生成树,而最小生成树是一副连通加权无向图中一颗权值最小的生成树,它可以根据Prim算法和Kruskal算法得出,这两个算法分别从点和边的角度...

    业余草
  • 最小生成树-Prim算法和Kruskal算法

    Prim算法 1.概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里...

    用户1215536
  • 图算法|Prim算法求最小生成树

    01 — 一个实际问题 要在n个城市之间铺设光缆,要求有2个: 这 n 个城市的任意两个之间都可以通信; 铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,...

    double
  • 最小生成树(Kruskal算法和Prim算法)

    上一篇文章,我们讲了图的创建和遍历,其中遍历的算法主要有BFS(广度优先算法)和DFS(深度优先算法)两种,并且DFS算法对很多问题都有很好的启示!而今天我们要...

    算法工程师之路
  • 贪心算法(四)——最小代价生成树

    问题描述 n个村庄间架设通信线路,每个村庄间的距离不同,如何架设最节省开销? 这个问题中,村庄可以抽象成节点,村庄之间的距离抽象成带权值的边,要求最节约...

    大闲人柴毛毛
  • 最小生成树----prim算法----普利姆算法

    大忽悠爱学习
  • 算法:图解最小生成树之普里姆(Prim)算法

    我们在图的定义中说过,带有权值的图就是网结构。一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。所谓的最小成本,就...

    s1mba
  • 最小生成树的本质是什么?Prim算法道破天机

    在上一篇文章当中,我们主要学习了最小生成树的Kruskal算法。今天我们来学习一下Prim算法,来从另一个角度来理解一下这个问题。

    TechFlow-承志
  • 使用贪心算法解决最小生成树

    生成树的定义:对于一个图G,获取G的边使得所有的顶点都连接到。最小生成树(MST Minimun spanning tree):给定图G(V,E),以及对应的边...

    爬蜥
  • 最小生成树算法(上)——Prim(普里姆)算法

    最小生成树:一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。根据定义可知对于一个有V个顶点的...

    AI那点小事
  • 数据结构(十八)——常用的算法(二)

      我们从上篇文章开始给大家介绍日常生活中经典的算法,上篇文章给大家介绍了二分查找法、分治法以及其典型应用汉诺塔问题,文章最后介绍了动态规划算法以及背包问题。本...

    一计之长
  • 最小生产树Prim和Kruskal

    温安适
  • Python Algorithms - C7 Greedy

    Python算法设计篇(7) Chapter 7: Greed is good? Prove it!

    宅男潇涧
  • 最小生成树(Prim算法和Kruskal算法算法详解)

    通俗易懂的讲就是最小生成树包含原图的所有节点而只用最少的边和最小的权值距离。因为n个节点最少需要n-1个边联通,而距离就需要采取某种策略选择恰当的边。

    bigsai
  • 数据结构01-最小生成树-Prim算法

    给定一个带权的无向连通图,能够连通该图的全部顶点且不产生回路的子图即为该图的生成树;

    yangjiao
  • 2021-04-20:手写代码:最小生成树算法之Prim。

    福大大架构师每日一题
  • 面试常见的四种算法思想,全在这里了

    我是架构精进之路,点击上方“关注”,坚持每天为你分享技术干货,私信我回复“01”,送你一份程序员成长进阶大礼包。

    架构精进之路
  • 最小生成树算法实现与分析:Prim 算法,Kruskal 算法;

    连通图:无向图G中,若从顶点i到顶点j有路径相连,则称i,j是连通的;如果G是有向图,那么连接i和j的路径中所有的边都必须同向;如果图中任意两点之间都是连通的,...

    xuyaowen

扫码关注云+社区

领取腾讯云代金券