思想简单但实现复杂的算法
1.0k
等9人参与

在这一章,我们学习了 Kruskal 算法。实际上,如果我们总结 Kruskal 的算法思路,非常简单:

把所有边按照权值排序。然后从小到大访问所有的边。如果当前访问的边和已经选择的边构成了环,则扔掉;否则,则属于最小树的边。

这个算法思想其实很早就已经出现了,但是,一个真正实用的 Kruskal 算法的实现,却很久以后才出现,这是因为关于如何快速判断“当前的边是否构成了环”,人们一直没有高效的解法,直到人们意识到实用并查集可以快速解决这个问题。

这实际上就是计算机科学的一大重点:思想不等于工程。很多时候,一个问题有了具体的解决思路,但是实际执行起来,就会发现还存在很多实现上的问题。

你有没有遇到过这样的情况?一个计算机问题,或者算法问题,说起来很简单,但具体实现起来,就会发现,其实并没有那么简单?


我的作业
去发布

登录后即可发布作业,立即

全部作业

数据加载中...

意见反馈 帮助中心 APP下载
官方微信