贪心算法4-最小生成树(Kruskal算法)
2020-01-12
阅读 8 分钟
7.3k构造最小生成树除了Prim算法,还有Kruskal算法。设G=(V,E)是无向连通带权图，设最小生成树T=(V, TE), TE表示已经加入最小生成树的边的集合。
贪心算法4-最小生成树(Prim算法）
2020-01-11
阅读 7 分钟
13.3k在一个有n个节点的无向连通图G = (V, E)中，V表示顶点集，E表示边集。只需n-1条边就可以使这个图连通，n-1条边要想保证图连通，就必须不含回路，所以我们只需要找出n-1条权值最小且无回路的边即可。需要明确几个概念：
贪心算法3-哈夫曼编码
2020-01-10
阅读 8 分钟
12.1k通常的编码方式有固定长度编码和不定长度编码两种。哈夫曼编码是不定长度编码的一种，它利用字符的使用频率来编码，经常使用的字符编码较短，不常使用的字符编码较长。目的是为了总的编码长度最短，空间效率最高，它是由数学家Huffman在1952年提出的。
贪心算法2-单源最短路径
2020-01-09
阅读 9 分钟
6.4k给定有向带权图G = (V, E),其中每条边的权是非负实数。此外，给定V中的一个顶点u,称为源点。现在要计算从源到所有其它各顶点的最短路径，这里的路径指的是路径上各边的权值之和。
贪心算法1--会议安排
2020-01-08
阅读 5 分钟
8.1k“良禽择木而栖，贤臣则主而事”，“窈窕淑女，君子好逑”，我们似乎永远在追求美而优的东西。仔细去想，你会发现“人之初，性本贪”。小孩子吃糖果，总想要最多的；吃水果，总想吃最大的；买玩具，总想要最好的，这种“贪”不是大人教的，是与生俱来的。然而现实中的很多事情，正是因为这种趋优性使我们的生活一步步走向美好。