00:00
各位同学,我们把刚才讲的克鲁斯卡尔算法呢给大家做一个小结,我们看看我们这块讲了哪些内容,以及是怎样进行讲解的,来先定位到这里,把幻灯片打到我们最先前的位置。我们怎么引出这个克鲁斯卡尔算法的呢?首先我们先提出了一个应用场景,就是公交站问题,对吧?我们捋捋思路。呃,首先呢,我们说,诶这有个应用场景,这个应用场景呢,就是去。对,我们这个公交站。公交站进行一个进行一个相应要求的处理,就是说我们怎么样。把这几个站连接起来,并且呢,它的总公路的总里程数最短,这是我们的这个需求。有这个需求呢,就引出我们对克鲁斯卡尔算法的一个介绍,对吧?具体要求也给同学们拿过来,一共是三个要求。
01:01
诶,就是什么。引出来的。好的,当我们把克鲁斯卡尔算法引出来过后呢,我们就给大家简单说一下克鲁斯卡尔的基本思路和具体的做法,但是这个呢是基于文字的,所以说同学们理解起来是理解起来有一定难度。所所以说我们紧接着。就在这个文字的基础上,我们又给同学们说,用图解的方式来理解克鲁斯卡尔算法的原理和步骤,那具体来说是怎么玩的呢?各位朋友?具体来说是这样写的,我们就把一个文档打开,这里边儿就把克鲁斯卡尔的一步一步的算法整出来了。好,我们把这个算法。图解也给大家拿到笔记里面来,便于同学们以后的整体复习。因为你搞不定搞,搞不齐,什么时候别人就问你。克鲁斯卡尔的一个算法,而且他是很经典的求最小生成数的算法,所以一定要去掌握。
02:03
然后我把。格式带过来就可以了,好,那么当我们把克鲁斯卡尔算法图解讲完了过后,是不是我们就来完成了这道题?说白了就是把原先提出的这个问题用代码进行一个实现,是这样子吧,同学们。对,是这样子的。这是对代码的一个完成,其实又回到我们提出这个问题了。那提出的问题还是刚才的这三点,那现在呢,我们就直接把代码给各位朋友放到这就可以了,好吧,代码实现。代码实现和和注释注解都有。都有。就是我们刚才写的克鲁斯卡尔的这个文件,一共这么多行号,还是有一点难度的,同学们还可以去这样试一下,说老师,那你用克鲁斯卡尔算法得到的最小生成数。然后呢,你换一个,换原先我们选,原先不是还有这个题吗。
03:04
是不是原先我们用普里,呃,普里姆算法也也去得到一个最小生成数,是不是你你把这个前面用的这个普里姆算法的案例,就是那个临界矩阵,你把它放到克鲁斯卡尔来算也是一样的,就是最后他的那个全值总和,就是跟你用普里姆算法算出来是一样的,就是不管你是用克鲁斯克鲁斯卡尔算法还是普里姆算法,最后得到这个结果都是相同的,明白这个我就不去试了,同学们可以再去试一个别的,我这写个注释啊,呃,同学们。大家。诶,大家可以再去。去测试。测试其他的这个题,其他的临街。对,临街矩阵矩阵。取证,那么结结果都是一样啊,结果都是最结果,结果都可以。
04:05
都。都可以得到。得到最小。最小生成数好的,这个呢,同学们自己去玩一玩,加深对它的一个理解,那代码呢,我就给各位朋友放到笔记里面就完事了,好吧。放这就可以了。那各位同学关于我们讲的。克鲁斯卡尔算法呢,就给同学们聊到这里,一定要去好好理解,下一个呢,我们就准备讲狄杰斯特拉算法。截取一段视频。
我来说两句