《算法导论》学习总结 — XX.第24章 单源最短路径

建议先看看前言:http://www.wutianqi.com/?p=2298

更多单源最短路径算法见我的算法专题:http://www.wutianqi.com/sfzt.html

这里我补充一些里面未写到的。

继续阅读《算法导论》学习总结 — XX.第24章 单源最短路径

《算法导论》学习总结 — XX.第23章 最小生成树

建议先看看前言:http://www.wutianqi.com/?p=2298

以前写过一篇最小生成树的文章,见:http://www.wutianqi.com/?p=1284

最小生成树(Minimum Spanning Tree),全称“最小权值生成树”

有两种具体的实现算法

1.Kruskal算法

2.Prim算法

两者都用到了贪心算法。

继续阅读《算法导论》学习总结 — XX.第23章 最小生成树

《算法导论》学习总结 — 第21章 用于不相交集合的数据结构

并查集(Disjoint Set)

起因:在某些应用中,要将n个不同的元素分成一组不相交的集合。

 

第21.1节 不相交集合的链表表示有些不太明白,有达人讲解或贡献出自己的学习笔记????

启发式策略是什么?—>我对这个概念一直很好奇???但是一直找不到好的文章和解释,看到我文章的朋友,求推荐,谢谢。

 

21.3节 不相交集合森林

这个曾经写过一个模板,书看了后,基本都可以写出来吧,依葫芦画瓢,代码模板链接:

http://www.wutianqi.com/?p=1066

至于两种启发式策略,来分别说下其作用:

①.按秩合并(union by rank),把较少结点的树的根合并到较多结点的树的跟,这样是为了尽量使树的高度减小,因此,可以优化Find_Set(x)。(看Find_Set()函数的代码~~)

②.路径压缩(path compression),使查找路径上的每个结点都指向根节点,路径压缩并不改变结点的秩,而且这样也同样优化了Find_Set(x)。

 

完毕!

关于算法导论笔记的更新|以及面试题求资源

因为前段时间各种原因,导致博客没时间更新,中间停了有3个月了吧,汗颜啊。。。

现在开始准备继续更新算法导论的笔记总结了,估计一周可以更新2次,大概在周三和周六晚上,把笔记更新完后,我应该就开始算法导论书后的那些题目了(当然,这个还不确定)。

另外,我也开始要关注历年各大公司的面试题了,希望大家给我一些来源,可以传给我的邮箱:

wtq1990#(自己换成@)gmail.com

感谢大家的支持!