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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1545 最简单排序

个人博客:double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

28360
来自专栏闻道于事

Java基础类库

52660
来自专栏从流域到海域

Python基本数据类型

其实之前有一篇博客:C\C#\Java\Python 基本数据类型比较 https://cloud.tencent.com/developer/article...

27460
来自专栏前端吧啦吧啦

涨薪必备Javascript,快点放进小口袋!

15220
来自专栏数据结构与算法

1102 A-B数对

题目描述 出题是一件痛苦的事情! 题目看多了也有审美疲劳,于是我舍弃了大家所熟悉的A+B Problem,改用A-B了哈哈! 好吧,题目是这样的:给出一串数以及...

404130
来自专栏用户2442861的专栏

C++ string中的几个小陷阱,你掉进过吗?

http://blog.csdn.net/lanxuezaipiao/article/details/24885811

15620
来自专栏函数式编程语言及工具

Scalaz(18)- Monad: ReaderWriterState-可以是一种简单的编程语言

  说道FP,我们马上会联想到Monad。我们说过Monad的代表函数flatMap可以把两个运算F[A],F[B]连续起来,这样就可以从程序的意义上形成一种串...

20870
来自专栏数据结构与算法

P2142 高精度减法

题目描述 高精度减法 输入输出格式 输入格式: 两个整数a,b(第二个可能比第一个大) 输出格式: 结果(是负数要输出负号) 输入输出样例 输入...

41960
来自专栏aCloudDeveloper

LeetCode:1_Two_Sum | 两个元素相加等于目标元素 | Medium

题目: Given an array of integers, find two numbers such that they add up to a spec...

216100
来自专栏恰童鞋骚年

你必须知道的指针基础-5.指针的几个小应用案例

  实现一个方法“多个返回值”的效果:返回一个三位数数字的个位、十位、百位。这里,我们借助指针来”返回“分解后的结果。这种应用也是最常见的指针应用。

11030

扫码关注云+社区

领取腾讯云代金券