Prim

1.dist[n]并不是记录该最小生成树的最小权值

2.两个for(j)循环的意义不一样,第一个是寻找与k点相邻的最小边,第二个是更新与k点相邻的边,当然dist依旧会存储着以前点k‘响铃的边,比如说第一个初始化的循环,第一个dist存储这与起点相邻的边,而这些边一次性用不完。

 http://sjjg.js.zwu.edu.cn/SFXX/sf1/prim.html

const int MAXN=110;
const int INF=0x7fffffff;

int n;//几个城市
int dist[MAXN];//dist[i]表示i向外延伸的最短边长
int map[MAXN][MAXN];//储存a->b之间的边权值
int pre[MAXN];//pre[i]记录i的父节点
int ans;

void Prim()
{
    int i,j,k;
    int min;
    bool p[MAXN];//区分Va集合和Vb集合
    for(i=2;i<=n;i++)
    {
        p[i]=false;
        dist[i]=map[1][i];
        pre[i]=1;
    }
    dist[1]=0;
    p[1]=true;
    for(i=1;i<=n-1;i++)//循环n-1次,每次加入一个点
    {
        min=INF;
        k=0;
        for(j=1;j<=n;j++)
        {//若j还在Vb集合中,并且j的路径可以再小点(找当前i点所对应的最短权值)
            if(!p[j] && dist[j]<min)
            {
                min=dist[j];
                k=j;
            }
        }
        if(k==0) return ;//如果没有点可以扩展,即图G不连通,返回
        p[k]=true;//将点k移到Va集合
        ans+=dist[k];//记录最小树的权值
        for(j=1;j<=n;j++)//更新相邻k相邻的点(有些dist依旧记录着以前Va结点中相邻的点)
        {
            //对于每个与k相邻的Vb中的点j,更新j距离最近的点及其距离
            if(!p[j] && map[k][j]!=INF && dist[j]>map[k][j])
            {
                dist[j]=map[k][j];
                pre[j]=k;
            }
        }
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Constructing Roads(最小生成树)

    #include<stdio.h> const int MAXN=110; const int INF=0x7fffffff; int n;//几个城市 i...

    用户1624346
  • ACdream 孟竹要减肥?(prim)

    刚开始题目看错了,一直wa,输入的坐标是浮点型。。。。。。。 听了队友的,才知道prim算法只需要枚举到sqrt(n)就完全足够了,发现sqrt(n)好多地方用...

    用户1624346
  • 畅通工程再续(最小生成树)

    这道题被坑的难受,很基础的题目,但是还是wa的郁闷,主要的错误是不懂的分析,导致变量的定义出错,记录k点的最短边要double的却依旧写int导致wa的找不出错...

    用户1624346
  • 一文了解GaussDB 200的产品架构、数据流程、组网方案、服务部署原则、企业级增强特性...

    墨墨导读:本文是对GaussDB 200产品的整体描述,包含产品架构、数据流程、组网方案、服务部署原则、企业级增强特性等。

    数据和云
  • Vivado下不可不知的快捷键

    快捷键,ctrl+C, ctrl+V, win+D, win+L等等,顾名思义,使用它们可以脱离鼠标快速执行目标任务。同样地,Vivado也提供了很多快捷键。

    Lauren的FPGA
  • 安装PHP7

    PHP 7 安装 : 其实安装PHP7的步骤和安装php5完全一样。 下载安装 cd /usr/local/src/ wget http://cn2.php....

    老七Linux
  • LAMP(3)安装PHP5、安装PHP7

    2.下载包: wget http://cn2.php.net/distributions/php-5.6.30.tar.gz

    py3study
  • poj----Ubiquitous Religions

    Ubiquitous Religions Time Limit: 5000MS Memory Limit: 65536K Total Submi...

    Gxjun
  • 经典面试题-CORBA 是什么用途是什么

    CORBA 标准是公共对象请求代理结构(Common Object Request BrokerArchitecture),由对象管理组织(Object Man...

    cwl_java
  • 软件测试基本概念

    根据用户需求行业规范,采用一些测试方法或一些工具对被测系统(程序数据文档)进行相应的测试(审核,运行,评估),尽早尽快的发现软件问题,提升软件的质量。

    测试小兵

扫码关注云+社区

领取腾讯云代金券