详情
本书按照算法策略分为9章内容，第1章主要讲小问题和概念，让读者体验算法的奥妙。第2~9章介绍经典的算法设计策略、实战演练、算法分析及优化拓展。每种算法都有4~10个实例，共45个大型实例，包括经典的构造实例和实际应用实例，按照问题分析、算法设计、完美图解、伪代码详解、实战演练、算法解析及优化拓展的流程，讲解清楚、通俗易懂。附录介绍常见的数据结构及算法改进用到的相关知识。
书名：趣学算法
ISBN：978-7-115-45957-2
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
• 著 陈小玉
责任编辑 张 爽
• 人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
• 读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书内容按照算法策略分为7章。第1章从算法之美、简单小问题、趣味故事引入算法概念、时间复杂度、空间复杂度的概念和计算方法，以及算法设计的爆炸性增量问题，使读者体验算法的奥妙。第2～7章介绍经典算法的设计策略、实战演练、算法分析及优化拓展，分别讲解贪心算法、分治算法、动态规划、回溯法、分支限界法、线性规划和网络流。每一种算法都有4～10个实例，共50个大型实例，包括经典的构造实例和实际应用实例，按照问题分析、算法设计、完美图解、伪代码详解、实战演练、算法解析及优化拓展的流程，讲解清楚且通俗易懂。附录介绍常见的数据结构及算法改进用到的相关知识，包括sort函数、优先队列、邻接表、并查集、四边不等式、排列树、贝尔曼规则、增广路复杂性计算、最大流最小割定理等内容。
本书可作为程序员的学习用书，也适合从未有过编程经验但又对算法有强烈兴趣的初学者使用，同时也可作为高等院校计算机、数学及相关专业的师生用书和培训学校的教材。
有一天，一个学生给我留言：“我看到一些资料介绍机器人具有情感，真是不可思议，我对这个特别感兴趣，但我该怎么做呢？”我告诉他：“先看算法。”过了一段时间，这个学生苦恼地说：“算法书上那些公式和大段的程序不能执行，太令人抓狂！我好像懂了一点儿，却又什么都不懂！”我向他推荐了一本简单一点儿的书，他仍然表示不太懂。
问题出在哪里？数据结构？C语言？还是算法表达枯燥、晦涩难懂？
这些问题一点也不意外，你不会想到，有同学拿着C语言书问我：“这么多英文怎么办？for、if这样的单词是不是要记住？”我的天！我从来没考虑过for、if这些是英文，而且是要记的单词！就像拿起筷子吃饭，端起杯子喝水，我从来没考虑我喝的是H2O。经过这件事情，彻底颠覆了我以前的教学理念，终于理解为什么看似简单的问题，那么多人就是看不懂。我们真正需要的是一本算法入门书，一本要简单、简单、再简单的算法入门书。
有学生告诉我：“大多数算法书上的代码都不能运行，或者运行时有各种错误，每每如此都迷茫至崩溃……”我说：“你要理解算法而不是运行代码。”可这个学生告诉我：“你知道吗，我运行代码成功后是多么喜悦和自信！已经远远超越了运行代码的本身。”好吧，相信这本书将会给你满满的喜悦和自信。
本书从算法之美娓娓道来，没有高深的原理，也没有枯燥的公式，通过趣味故事引出算法问题，结合大量的实例及绘图展示，分析算法本质，并给出代码实现的详细过程和运行结果。如果你读这本书，像躺在躺椅上悠闲地读《普罗旺斯的一年》，这就对了！这就是我的初衷。
本书适合那些对算法有强烈兴趣的初学者，以及觉得算法晦涩难懂、无所适从的人，也适合作为计算机相关专业教材。它能帮助你理解经典的算法设计与分析问题，并获得足够多的经验和实践技巧，以便更好地分析和解决问题，为学习更高深的算法奠定基础。
更重要的是——体会算法之美！
知识在于积累，学习需要耐力。学习就像挖金矿，或许一开始毫无头绪，但转个角度、换换工具，时间久了总会找到一个缝隙。成功就是你比别人多走了一段路，或许恰恰是那么一小步。
第一个建议：多角度，对比学习。
学习算法，可以先阅读一本简单的入门书，然后综合几本书横向多角度看，例如学习动态规划，拿几本算法书，把动态规划这章都找出来，比较学习，多角度对比分析更清晰，或许你会恍然大悟。或许有同学说我哪有那么多钱买那么多书，只要想学习，没有什么可以阻挡你！你可以联系你的老师，每学期上课前，我都会告诉学生，如果你想学习却没钱买书，我可以提供帮助。想一想，你真的没有办法吗？
第二个建议：大视野，不求甚解。
经常有学生为了一个公式推导或几行代码抛锚，甚至停滞数日，然后沉浸在无尽的挫败感中，把自己弄得垂头丧气。公式可以不懂，代码可以不会。你不必投入大量精力试图推导书上的每一个公式，也不必探究语法或技术细节。学算法就是学算法本身，首先是算法思想、解题思路，然后是算法实现。算法思想的背后可能有高深的数学模型、复杂的公式推导，你理解了当然更好，不懂也没关系。算法实现可以用任何语言，所以不必纠结是C、C++、Java、Python……更不必考虑严格的语法规则，除非你要上机调试。建议还是先领会算法，写伪代码，在大脑中调试吧！如果你没有良好的编程经验，一开始就上机或许会更加崩溃。遇到不懂的部分，浏览一下或干脆跳过去，读完了还不明白再翻翻别的书，总有一天，你会发现“蓦然回首，那人却在灯火阑珊处”。
第三个建议：多交流，见贤思齐。
与同学、朋友、老师或其他编程爱好者一起学习和讨论问题，是取得进步最有效的办法之一，也是分享知识和快乐的途径。加入论坛、交流群，会了解其他人在做什么、怎么做。遇到问题请教高手，会感受到醍醐灌顶的喜悦。论坛和群也会分享大量的学习资料和视频，还有不定期的培训讲座和读书交流会。记住，你不是一个人在战斗！
第四个建议：勤实战，越挫越勇。
实践是检验真理的唯一标准。古人云：“学以致用”“师夷长技以制夷”。请不要急切期盼实际应用的例子，更不要看不起小实例。“不积跬步，无以至千里”，大规模的成功商业案例不是我们目前要解决的问题。看清楚并走好脚下的路，比仰望天空更实际。多做一些实战练习，更好地体会算法的本质，在错误中不断成长，越挫越勇，相信你终究会有建树。
第五个建议：看电影，洞察未来。
不管是讲人工智能，还是算法分析，我都会建议同学们去看一看科幻电影，如《人工智能》《记忆裂痕》《绝密飞行》《未来战士》《她》等。奇妙的是，这些科幻的东西正在一步步地被实现，靠的是什么？人工智能。计算机的终极是人工智能，人工智能的核心是算法。未来的战争是科技的战争，先进的科技需要人工智能。我们的国家还有很多技术处于落后状态，未来需要你。
“一心两本”学习法：一颗好奇心，两个记录本。
怀着一颗好奇心去学习，才能不断地解决问题，获得满足感，体会算法的美。很多科学大家的秘诀就是永远保持一颗好奇心；一个记录本用来记录学习中的重点难点和随时突发的奇想；一个记录本做日记或周记，记录一天或一周来学了什么，有什么经验教训，需要注意什么，计划下一天或下一周做什么。不停地总结反思过去，计划未来，这样每天都有事做，心中会有满满的正能量。
记住没有人能一蹴而就，付出总有回报。
（1）实例丰富，通俗易懂。从有趣的故事引入算法，从简单到复杂，使读者从实例中体会算法设计思想。实例讲解通俗易懂，让读者获得最大程度的启发，锻炼分析问题和解决问题的能力。
（2）完美图解，简单有趣。结合大量完美绘图，对算法进行分解剖析，使复杂难懂的问题变得简单有趣，给读者带来巨大的阅读乐趣，使读者在阅读中不知不觉地学到算法知识，体会算法的本质。
（3）深入浅出，透析本质。采用伪代码描述算法，既简洁易懂，又能抓住本质，算法思想描述及注释使代码更加通俗易懂。对算法设计初衷和算法复杂性的分析全面细致，既有逐步得出结论的推导过程，又有直观的绘图展示。
（4）实战演练，循序渐进。每一个算法讲解清楚后，进行实战演练，使读者在实战中体会算法，增强自信，从而提高读者独立思考和动手实践的能力。丰富的练习题和思考题用于及时检验读者对所学知识掌的握情况，为读者从小问题出发到逐步解决大型复杂性问题奠定了基础。
（5）算法解析，优化拓展。每一个实例都进行了详细的算法解析，分析算法的时间复杂度和空间复杂度，并对其优化拓展进一步讨论，提出了改进算法，并进行伪码讲解和实战演练，最后分析优化算法的复杂度进行对比。使读者在学习算法的基础上更上一个阶梯，对算法优化有更清晰的认识。
（6）网络资源，技术支持。网络提供本书所有范例程序的源代码、练习题以及答案解析，这些源代码可以自由修改编译，以符合读者的需要。本书提供源代码执行、调试说明书，对读者存在的问题提供技术支持。
写一本书是一项极其琐碎、繁重的工作，尽管我已经竭力使本书和网络支持接近完美，但仍然可能存在很多漏洞和瑕疵。欢迎读者提供关于本书的反馈意见，有利于我们改进和提高，以帮助更多的读者。如果你对本书有任何评论和建议，或者遇到问题需要帮助，可以加入趣学算法交流QQ群（514626235）进行交流，也可以致信作者邮箱rainchxy@126.com或本书编辑邮箱zhangshuang@ptpress.com.cn，我将不胜感激。
感谢我的家人和朋友在本书编写过程中提供的大力支持！感谢提供宝贵意见的同事们，感谢提供技术支持的同学们！感恩我遇到的众多良师益友！
1.1 打开算法之门
1.2 妙不可言——算法复杂性
1.3 美不胜收——魔鬼序列
1.4 灵魂之交——马克思手稿中的数学题
1.5 算法学习瓶颈
1.6 你怕什么
如果说数学是皇冠上的一颗明珠，那么算法就是这颗明珠上的光芒，算法让这颗明珠更加熠熠生辉，为科技进步和社会发展照亮了前进的路。数学是美学，算法是艺术。走进算法的人，才能体会它的魅力。
多年来，我有一个梦想，希望每一位提到算法的人，不再立即紧皱眉头，脑海闪现枯燥的公式、冗长的代码；希望每一位阅读和使用算法的人，体会到算法之美，像躺在法国普罗旺斯小镇的长椅上，呷一口红酒，闭上眼睛，体会舌尖上的美味，感受鼻腔中满溢的薰衣草的芳香……
瑞士著名的科学家N.Wirth教授曾提出：数据结构+算法=程序。
数据结构是程序的骨架，算法是程序的灵魂。
在我们的生活中，算法无处不在。我们每天早上起来，刷牙、洗脸、吃早餐，都在算着时间，以免上班或上课迟到；去超市购物，在资金有限的情况下，考虑先买什么、后买什么，算算是否超额；在家中做饭，用什么食材、调料，做法、步骤，还要品尝一下咸淡，看看是否做熟。所以，不要说你不懂算法，其实你每天都在用！
但是对计算机专业算法，很多人都有困惑：“I can understand, but I can’tuse！”，我能看懂，但不会用！就像参观莫高窟的壁画，看到它、感受它，却无法走进。我们正需要一把打开算法之门的钥匙，就如陶渊明《桃花源记》中的“初极狭，才通人。复行数十步，豁然开朗。”
我们首先看一道某跨国公司的招聘试题。
写一个算法，求下面序列之和：
−1，1，−1，1，…，(−1)n
当你看到这个题目时，你会怎么想？for语句？while循环？
先看算法1-1：
//算法1-1
sum=0;
for(i=1; i<=n; i++)
{
sum=sum+(-1)^n;
}这段代码可以实现求和运算，但是为什么不这样算?！
再看算法1-2：
//算法1-2
if(n%2==0) //判断n是不是偶数，%表示求余数
sum =0;
else
sum=-1;有的人看到这个代码后恍然大悟，原来可以这样啊？这不就是数学家高斯使用的算法吗？
一共50对数，每对之和均为101，那么总和为：
（1+100）×50=5050
1787年，10岁的高斯用了很短的时间算出了结果，而其他孩子却要算很长时间。
可以看出，算法1-1需要运行n+1次，如果n=100 00，就要运行100 01次，而算法1-2仅仅需要运行1次！是不是有很大差别？
高斯的方法我也知道，但遇到类似的题还是……我用的笨办法也是算法吗？
答：是算法。
算法是指对特定问题求解步骤的一种描述。
算法只是对问题求解方法的一种描述，它不依赖于任何一种语言，既可以用自然语言、程序设计语言（C、C++、Java、Python等）描述，也可以用流程图、框图来表示。一般为了更清楚地说明算法的本质，我们去除了计算机语言的语法规则和细节，采用“伪代码”来描述算法。“伪代码”介于自然语言和程序设计语言之间，它更符合人们的表达方式，容易理解，但不是严格的程序设计语言，如果要上机调试，需要转换成标准的计算机程序设计语言才能运行。
算法具有以下特性。
（1）有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止。
（2）确定性：每条语句有确定的含义，无歧义。
（3）可行性：算法在当前环境条件下可以通过有限次运算实现。
（4）输入输出：有零个或多个输入，一个或多个输出。
算法1-2的确算得挺快的，但如何知道我写的算法好不好呢？
“好”算法的标准如下。
（1）正确性：正确性是指算法能够满足具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期的需求。
（2）易读性：算法遵循标识符命名规则，简洁易懂，注释语句恰当适量，方便自己和他人阅读，便于后期调试和修改。
（3）健壮性：算法对非法数据及操作有较好的反应和处理。例如，在学生信息管理系统中登记学生年龄时，若将21岁误输入为210岁，系统应该提示出错。
（4）高效性：高效性是指算法运行效率高，即算法运行所消耗的时间短。算法时间复杂度就是算法运行需要的时间。现代计算机一秒钟能计算数亿次，因此不能用秒来具体计算算法消耗的时间，由于相同配置的计算机进行一次基本运算的时间是一定的，我们可以用算法基本运算的执行次数来衡量算法的效率。因此，将算法基本运算的执行次数作为时间复杂度的衡量标准。
（5）低存储性：低存储性是指算法所需要的存储空间低。对于像手机、平板电脑这样的嵌入式设备，算法如果占用空间过大，则无法运行。算法占用的空间大小称为空间复杂度。
除了（1）～（3）中的基本标准外，我们对好的算法的评判标准就是高效率、低存储。
（1）～（3）中的标准都好办，但时间复杂度怎么算呢？
时间复杂度：算法运行需要的时间，一般将算法的执行次数作为时间复杂度的度量标准。
看算法1-3，并分析算法的时间复杂度。
//算法1-3
sum=0; //运行1次
total=0; //运行1次
for(i=1; i<=n; i++) //运行n次
{
sum=sum+i; //运行n次
for(j=1; j<=n; j++) //运行n*n次
total=total+i*j; //运行n*n次
}把算法的所有语句的运行次数加起来：1+1+n+n+n×n+n×n，可以用一个函数T(n)表达：
T(n)=2n2+2n+2
当n足够大时，例如n=105时，T(n)=2×1010+2×105+2，我们可以看到算法运行时间主要取决于第一项，后面的甚至可以忽略不计。
用极限表示为：
，C为不等于0的常数
如果用时间复杂度的渐近上界表示，如图1-1所示。
从图1-1中可以看出，当n
n0时，T(n)
Cf (n)，当n足够大时，T(n)和f (n)近似相等。因此，我们用О(f (n))来表示时间复杂度渐近上界，通常用这种表示法衡量算法时间复杂度。算法1-3的时间复杂度渐近上界为О(f (n))＝О(n2)，用极限表示为：
图1-1 渐近时间复杂度上界
还有渐近下界符号Ω(T(n)Cf (n))，如图1-2所示。
图1-2 渐近时间复杂度下界
从图1-2可以看出，当nn0时，T(n)Cf (n)，当n足够大时，T(n)和f (n)近似相等，因此，我们用Ω(f (n))来表示时间复杂度渐近下界。
渐近精确界符号Θ(C1f (n)T(n)C2f (n))，如图1-3所示。
从图1-3中可以看出，当nn0时，C1f (n)T(n)C2f (n)，当n足够大时，T(n)和f (n)近似相等。这种两边逼近的方式，更加精确近似，因此，用Θ (f (n))来表示时间复杂度渐近精确界。
图1-3 渐进时间复杂度精确界
我们通常使用时间复杂度渐近上界О(f (n))来表示时间复杂度。
看算法1-4，并分析算法的时间复杂度。
//算法1-4
i=1; //运行1次
while(i<=n) //可假设运行x次
{
i=i*2; //可假设运行x次
}观察算法1-4，无法立即确定while 及i=i*2运行了多少次。这时可假设运行了x次，每次运算后i值为2，22，23，…，2x，当i=n时结束，即2x＝n时结束，则x=log2n，那么算法1-4的运算次数为1+2log2n，时间复杂度渐近上界为О(f (n))＝О(log2n)。
在算法分析中，渐近复杂度是对算法运行次数的粗略估计，大致反映问题规模增长趋势，而不必精确计算算法的运行时间。在计算渐近时间复杂度时，可以只考虑对算法运行时间贡献大的语句，而忽略那些运算次数少的语句，循环语句中处在循环内层的语句往往运行次数最多，即为对运行时间贡献最大的语句。例如在算法1-3中，total=total+i*j是对算法贡献最大的语句，只计算该语句的运行次数即可。
注意：不是每个算法都能直接计算运行次数。
例如算法1-5，在a[n]数组中顺序查找x，返回其下标i，如果没找到，则返回−1。
//算法1-5
findx(int x) //在a[n]数组中顺序查找x
{
for(i=0; i<n; i++)
{
if (a[i]==x)
return i; //返回其下标i
｝
return -1;
}我们很难计算算法1-5中的程序到底执行了多少次，因为运行次数依赖于x在数组中的位置，如果第一个元素就是x，则执行1次（最好情况）；如果最后一个元素是x，则执行n次（最坏情况）；如果分布概率均等，则平均执行次数为（n+1）/2。
有些算法，如排序、查找、插入等算法，可以分为最好、最坏和平均情况分别求算法渐近复杂度，但我们考查一个算法通常考查最坏的情况，而不是考查最好的情况，最坏情况对衡量算法的好坏具有实际的意义。
我明白了，那空间复杂度应该就是算法占了多大存储空间了？
空间复杂度：算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。
空间复杂度的本意是指算法在运行过程中占用了多少存储空间。算法占用的存储空间包括：
（1）输入/输出数据；
（2）算法本身；
（3）额外需要的辅助空间。
输入/输出数据占用的空间是必需的，算法本身占用的空间可以通过精简算法来缩减，但这个压缩的量是很小的，可以忽略不计。而在运行时使用的辅助变量所占用的空间，即辅助空间是衡量空间复杂度的关键因素。
看算法1-6，将两个数交换，并分析其空间复杂度。
//算法1-6
swap(int x,int y) //x与y交换
{
int temp;
temp=x; //temp为辅助空间 ①
x=y; ②
y=temp; ③
}两数的交换过程如图1-4所示。
图1-4 两数交换过程
图1-4中的步骤标号与算法1-6中的语句标号一一对应，该算法使用了一个辅助空间temp，空间复杂度为О(1)。
注意：递归算法中，每一次递推需要一个栈空间来保存调用记录，因此，空间复杂度需要计算递归栈的辅助空间。
看算法1-7，计算n的阶乘，并分析其空间复杂度。
//算法1-7
fac(int n) //计算n的阶乘
{
if(n<0) //小于零的数无阶乘值
{
printf("n<0,data error!");
return -1;
}
else if(n= =0 || n= =1)
return 1;
else
return n*fac(n-1);
}阶乘是典型的递归调用问题，递归包括递推和回归。递推是将原问题不断分解成子问题，直到达到结束条件，返回最近子问题的解；然后逆向逐一回归，最终到达递推开始的原问题，返回原问题的解。
思考：试求5的阶乘，程序将怎样计算呢？
5的阶乘的递推和回归过程如图1-5和图1-6所示。
图1-5 5的阶乘递推过程
图1-6 5的阶乘回归过程
图1-5和图1-6的递推、回归过程是我们从逻辑思维上推理，用图的方式形象地表达出来的，但计算机内部是怎样处理的呢？计算机使用一种称为“栈”的数据结构，它类似于一个放一摞盘子的容器，每次从顶端放进去一个，拿出来的时候只能从顶端拿一个，不允许从中间插入或抽取，因此称为“后进先出”（last in first out）。
5的阶乘进栈过程如图1-7所示。
图1-7 5的阶乘进栈过程
5的阶乘出栈过程如图1-8所示。
图1-8 5的阶乘出栈过程
从图1-7和图1-8的进栈、出栈过程中，我们可以很清晰地看到，首先把子问题一步步地压进栈，直到得到返回值，再一步步地出栈，最终得到递归结果。在运算过程中，使用了n个栈空间作为辅助空间，因此阶乘递归算法的空间复杂度为О(n)。在算法1-7中，时间复杂度也为О(n)，因为n的阶乘仅比n−1的阶乘多了一次乘法运算，fac(n)=n*fac(n−1)。如果用T(n)表示fac(n)的时间复杂度，可表示为：
T(n)= T(n−1)+1
= T(n−2)+1+1
……
= T(1)+…+1+1
=n
有一个古老的传说，有一位国王的女儿不幸落水，水中有很多鳄鱼，国王情急之下下令：“谁能把公主救上来，就把女儿嫁给他。”很多人纷纷退让，一个勇敢的小伙子挺身而出，冒着生命危险把公主救了上来，国王一看是个穷小子，想要反悔，说：“除了女儿，你要什么都可以。”小伙子说：“好吧，我只要一棋盘的麦子。您在第1个格子里放1粒麦子，在第2个格子里放2粒，在第3个格子里放4粒，在第4个格子里放8粒，以此类推，每一格子里的麦子粒数都是前一格的两倍。把这64个格子都放好了就行，我就要这么多。”国王听后哈哈大笑，觉得小伙子的要求很容易满足，满口答应。结果发现，把全国的麦子都拿来，也填不完这64格……国王无奈，只好把女儿嫁给了这个小伙子。
解析
棋盘上的64个格子究竟要放多少粒麦子？
把每一个放的麦子数加起来，总和为S，则：
S=1+21+22+23+…+263 ①
我们把式①等号两边都乘以2，等式仍然成立：
2S=21+22+23+…+263+264 ②
式 ②减去式①，则：
S=264−1 ＝18 446 744 073 709 551 615
据专家统计，每个麦粒的平均重量约41.9毫克，那么这些麦粒的总重量是：
18 446 744 073 709 551 615×41.9＝772 918 576 688 430 212 668.5（毫克）
≈7729（亿吨）
全世界人口按60亿计算，每人可以分得128吨！
我们称这样的函数为爆炸增量函数，想一想，如果算法时间复杂度是О(2n) 会怎样？随着n的增长，这个算法会不会“爆掉”？经常见到有些算法调试没问题，运行一段也没问题，但关键的时候宕机（shutdown）。例如，在线考试系统，50个人考试没问题，100人考试也没问题，如果全校1万人考试就可能出现宕机。
注意：宕机就是死机，指电脑不能正常工作了，包括一切原因导致的死机。计算机主机出现意外故障而死机，一些服务器（如数据库）死锁，服务器的某些服务停止运行都可以称为宕机。
常见的算法时间复杂度有以下几类。
（1）常数阶。
常数阶算法运行的次数是一个常数，如5、20、100。常数阶算法时间复杂度通常用О(1)表示，例如算法1-6，它的运行次数为4，就是常数阶，用О(1)表示。
（2）多项式阶。
很多算法时间复杂度是多项式，通常用О(n)、О(n2)、О(n3)等表示。例如算法1-3就是多项式阶。
（3）指数阶。
指数阶时间复杂度运行效率极差，程序员往往像躲“恶魔”一样避开它。常见的有О(2n)、О(n！)、О(nn)等。使用这样的算法要慎重，例如趣味故事1-1。
（4）对数阶。
对数阶时间复杂度运行效率较高，常见的有О(logn)、О(nlogn)等，例如算法1-4。
常见时间复杂度函数曲线如图1-9所示。
图1-9 常见函数增量曲线
从图1-9中可以看出，指数阶增量随着x的增加而急剧增加，而对数阶增加缓慢。它们之间的关系为：
О(1)< О(logn)< О(n)< О(nlogn) < О(n2)< О(n3)< О(2n) < О(n!)< О(nn)
我们在设计算法时要注意算法复杂度增量的问题，尽量避免爆炸级增量。
假设第1个月有1对刚诞生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生兔子开始，12个月后会有多少对兔子呢？
兔子数列即斐波那契数列，它的发明者是意大利数学家列昂纳多•斐波那契（Leonardo Fibonacci，1170—1250）。1202年，他撰写了《算盘全书》（《Liber Abaci》）一书，该书是一部较全面的初等数学著作。书中系统地介绍了印度—阿拉伯数码及其演算法则，介绍了中国的“盈不足术”；引入了负数，并研究了一些简单的一次同余式组。
（1）问题分析
我们不妨拿新出生的1对小兔子分析：
第1个月，小兔子①没有繁殖能力，所以还是1对。
第2个月，小兔子①进入成熟期，仍然是1对。
第3个月，兔子①生了1对小兔子②，于是这个月共有2（1+1=2）对兔子。
第4个月，兔子①又生了1对小兔子③。因此共有3（1+2=3）对兔子。
第5个月，兔子①又生了1对小兔子④，而在第3个月出生的兔子②也生下了1对小兔子⑤。共有5（2+3=5）对兔子。
第6个月，兔子①②③各生下了1对小兔子。新生3对兔子加上原有的5对兔子这个月共有8（3+5=8）对兔子。
……
为了表达得更清楚，我们用图示来分别表示新生兔子、成熟期兔子和生育期兔子，兔子的繁殖过程如图1-10所示。
图1-10 兔子繁殖过程
这个数列有十分明显的特点，从第3个月开始，当月的兔子数=上月兔子数+当月新生兔子数，而当月新生的兔子正好是上上月的兔子数。因此，前面相邻两项之和，构成了后一项，即：
当月的兔子数=上月兔子数+上上月的兔子数
斐波那契数列如下：
1，1，2，3，5，8，13，21，34，…
递归式表达式：
那么我们该怎么设计算法呢？
哈哈，这太简单了，用递归算法很快就算出来了！
（2）算法设计
首先按照递归表达式设计一个递归算法，见算法1-8。
//算法1-8
Fib1(int n)
{
if(n<1)
return -1;
if(n==1||n==2)
return 1;
return Fib1(n-1)+Fib1(n-2);
}写得不错，那么算法设计完成后，我们有3个问题：
（3）算法验证分析
第一个问题毋庸置疑，因为算法1-8是完全按照递推公式写出来的，所以正确性没有问题。那么算法复杂度呢？假设T(n)表示计算Fib1(n)所需要的基本操作次数，那么：
n=1时，T(n)=1；
n=2时，T(n)=1；
n=3时，T(n)=3；//调用Fib1(2)、Fib1(1)和执行一次加法运算Fib1(2)+Fib1(1)因此，n>2时要分别调用Fib1(n−1)、Fib1(n−2)和执行一次加法运算，即：
n>2时，T(n)= T(n-1)+ T(n-2)+1；递归表达式和时间复杂度T(n)之间的关系如下：
由此可得：。
那么怎么计算F(n)呢？
有兴趣的读者可以看本书附录A中通项公式的求解方法，也可以看下文中的简略解释。
斐波那契数列通项为：
当n趋近于无穷时，
由于
，这是一个指数阶的算法！
如果我们今年计算出了F(100)，那么明年才能算出F(101)，多算一个斐波那契数需要一年的时间，爆炸增量函数是算法设计的噩梦！算法1-8的时间复杂度属于爆炸增量函数，这在算法设计时是应当避开的，那么我们能不能改进它呢？
（4）算法改进
既然斐波那契数列中的每一项是前两项之和，如果记录前两项的值，只需要一次加法运算就可以得到当前项，时间复杂度会不会更低一些？我们用数组试试看，见算法1-9。
//算法1-9
Fib2(int n)
{
if(n<1)
return -1;
int *a=new int[n];//定义一个数组
a[1]=1；
a[2]=1;
for(int i=3;i<=n;i++)
a[i]=a[i-1]+a[i-2];
return a[n];
}很明显，算法1-9的时间复杂度为О(n)。算法仍然是按照F(n)的定义，所以正确性没有问题，而时间复杂度却从算法1-8的指数阶降到了多项式阶，这是算法效率的一个巨大突破！
算法1-9使用了一个辅助数组记录中间结果，空间复杂度也为О(n)，其实我们只需要得到第n个斐波那契数，中间结果只是为了下一次使用，根本不需要记录。因此，我们可以采用迭代法进行算法设计，见算法1-10。
//算法1-10
Fib3(int n)
{
int i,s1,s2;
if(n<1)
return -1;
if(n==1||n==2)
return 1;
s1=1;
s2=1;
for(i=3; i<=n; i++)
{
s2=s1+s2; //辗转相加法
s1=s2-s1; //记录前一项
}
return s2;
}迭代过程如下。
初始值：s1=1；s2=1；
当前解 记录前一项
i=3时 s2= s1+s2=2 s1=s2−s1=1
i=4时 s2= s1+s2=3 s1= s2−s1=2
i=5时 s2= s1+s2=5 s1= s2−s1=3
i=6时 s2= s1+s2=8 s1= s2−s1=5
…… …… ……
算法1-10使用了若干个辅助变量，迭代辗转相加，每次记录前一项，时间复杂度为О(n)，但空间复杂度降到了О(1)。
问题的进一步讨论：我们能不能继续降阶，使算法时间复杂度更低呢？实质上，斐波那契数列时间复杂度还可以降到对数阶О(logn)，有兴趣的读者可以查阅相关资料。想想看，我们把一个算法从指数阶降到多项式阶，再降到对数阶，这是一件多么振奋人心的事！
（5）惊人大发现
科学家经研究在植物的叶、枝、茎等排列中发现了斐波那契数！例如，在树木的枝干上选一片叶子，记其为数1，然后依序点数叶子（假定没有折损），直到到达与那片叶子正对的位置，则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个循回中，叶子数与叶子旋转圈数的比称为叶序（源自希腊词，意即叶子的排列）比。多数植物的叶序比呈现为斐波那契数的比，例如，蓟的头部具有13条顺时针旋转和21条逆时针旋转的斐波那契螺旋，向日葵的种子的圈数与子数、菠萝的外部排列同样有着这样的特性，如图1-11所示。
图1-11 斐波那契螺旋（图片来自网络）
观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花的花瓣，可以发现它们的花瓣数目为斐波那契数：3，5，8，13，21，…。如图1-12所示。
图1-12 植物花瓣（图片来自网络）
树木在生长过程中往往需要一段“休息”时间，供自身生长，而后才能萌发新枝。所以，一株树苗在一段间隔（例如一年）以后长出一条新枝；第二年新枝“休息”，老枝依旧萌发；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则次年“休息”。这样，一株树木各个年份的枝桠数便构成斐波那契数列，这个规律就是生物学上著名的“鲁德维格定律”。
这些植物懂得斐波那契数列吗？应该并非如此，它们只是按照自然的规律才进化成这样的。这似乎是植物排列种子的“优化方式”，它能使所有种子具有相近的大小却又疏密得当，不至于在圆心处挤太多的种子而在圆周处却又很稀疏。叶子的生长方式也是如此，对于许多植物来说，每片叶子从中轴附近生长出来，为了在生长的过程中一直都能最佳地利用空间（要考虑到叶子是一片一片逐渐地生长出来，而不是一下子同时出现的），每片叶子和前一片叶子之间的角度应该是222.5°，这个角度称为“黄金角度”，因为它和整个圆周360°之比是黄金分割数0.618的倒数，而这种生长方式就导致了斐波那契螺旋的产生。向日葵的种子排列形成的斐波那契螺旋有时能达到89，甚至144。1992年，两位法国科学家通过对花瓣形成过程的计算机仿真实验，证实了在系统保持最低能量的状态下，花朵会以斐波那契数列的规律长出花瓣。
有趣的是：这样一个完全是自然数的数列，通项公式却是用无理数来表达的。而且当n趋向于无穷大时，斐波那契数列前一项与后一项的比值越来越逼近黄金分割比0.618：1÷1 = 1，1÷2 = 0.5，2÷3 = 0.666，…，3÷5 = 0.6，5÷8 = 0.625，…，55÷89 = 0.617977，…，144÷233 = 0.618025，…，46368÷75025 = 0.6180339886……
越到后面，这些比值越接近黄金分割比：
斐波那契数列起源于兔子数列，这个现实中的例子让我们真切地感到数学源于生活，生活中我们需要不断地通过现象发现数学问题，而不是为了学习而学习。学习的目的是满足对世界的好奇心，如果我们怀着这样一颗好奇心，或许世界会因你而不同！斐波那契通过兔子繁殖来告诉我们这种数学问题的本质，随着数列项的增加，前一项与后一项之比越来越逼近黄金分割的数值0.618时，我彻底被震惊到了，因为数学可以表达美，这是令我们叹为观止的地方。当数学创造了更多的奇迹时，我们会发现数学本质上是可以回归到自然的，这样的事例让我们感受到数学的美，就像黄金分割、斐波那契数列，如同大自然中的一朵朵小花，散发着智慧的芳香……
有人抱怨：算法太枯燥、乏味了，看到公式就头晕，无法学下去了。你肯定选择了一条充满荆棘的路。选对方法，你会发现这里是一条充满鸟语花香和欢声笑语的幽径，在这里，你可以和高德纳聊聊，同爱因斯坦喝杯咖啡，与歌德巴赫和角谷谈谈想法，Dijkstra也不错。与世界顶级的大师进行灵魂之交，不问结果，这一过程已足够美妙！
如果这本书能让多一个人爱上算法，这就足够了！
马克思手稿中有一道趣味数学问题：有30个人，其中有男人、女人和小孩，这些人在一家饭馆吃饭花了50先令；每个男人花3先令，每个女人花2先令，每个小孩花1先令；问男人、女人和小孩各有几人？
（1）问题分析
设x、y、z分别代表男人、女人和小孩。按题目的要求，可得到下面的方程：
x+y+z=30 ①
3x+2y+z=50 ②
两式相减，②−①得：
2x+y=20 ③
从式③可以看出，因为x、y为正整数，x最大只能取9，所以x变化范围是1～9。那么我们可以让x从1到9变化，再找满足①②两个条件y、z值，找到后输入即可，答案可能不止一个。
（2）算法设计
按照上面的分析进行算法设计，见算法1-11。
//算法1-11
#include<iostream>
int main()
{
int x,y,z,count=0; //记录可行解的个数
cout<<" Men，Women，Children"<<endl;
cout<<"........................................"<<endl;
for(x=1;x<=9;x++)
{
y=20-2*x; //固定x值然后根据式③求得y值
z=30-x-y; //由式①求得z值
if(3*x+2*y+z==50) //判断当前得到的一组解是否满足式②
cout<<++count<<" "<<x<<y<<z<<endl; //打印出第几个解和解值x，y，z
}
}
（3）算法分析
算法完全按照题中方程设计，因此正确性毋庸置疑。那么算法复杂度怎样呢？从算法1-11中可以看出，对算法时间复杂度贡献最大的语句是for(x=1;x<=9;x++)，该语句的执行次数是9，for循环中3条语句的执行次数也为9，其他语句执行次数为1，for语句一共执行36次基本运算，时间复杂度为О(1)。没有使用辅助空间，空间复杂度也为О(1)。
（4）问题的进一步讨论
为什么让x变化来确定y、z值？让y变化来确定x、z值会怎样呢？让z变化来确定x、y值行不行？有没有更好的算法降低时间复杂度？
爱因斯坦家里有一条长阶梯，若每步跨2阶，则最后剩1阶；若每步跨3阶，则最后剩2阶；若每步跨5阶，则最后剩4阶；若每步跨6阶，则最后剩5阶。只有每次跨7阶，最后才正好1阶不剩。请问这条阶梯共有多少阶？
（1）问题分析
根据题意，阶梯数n满足下面一组同余式：
n≡1(mod2)
n≡2(mod3)
n≡4(mod5)
n≡5(mod6)
n≡0(mod7)
注意：两个整数a、b，若它们除以整数m所得的余数相等，则称a、b对于模m同余，记作a≡b(mod m)，读作a同余于b模m，或读作a与b关于模m同余。那么只需要判断一个整数值是否满足这5个同余式即可。
（2）算法设计
按照上面的分析进行算法设计，见算法1-12。
//算法1-12
#include<iostream>
int main()
{
int n=1; //n为所设的阶梯数
while(!((n%2==1)&&(n%3==2)&&(n%5==4)&&(n%6==5)&&(n%7==0)))
n++; //判别是否满足一组同余式
cout<<"Count the stairs= "<<n<<endl; //输出阶梯数
}（3）算法分析
算法的运行结果：
Count the stairs =119因为n从1开始，找到第一个满足条件的数就停止，所以算法1-12中的while语句运行了119次。有的算法从算法本身无法看出算法的运行次数，例如算法1-12，我们很难知道while语句执行了多少次，因为它是满足条件时停止，那么多少次才能满足条件呢？每个问题具体的次数是不同的，所以不能看到程序中有n，就简单地说它的时间复杂度为n。
我们从1开始一个一个找结果的办法是不是太麻烦了？
（4）算法改进
因为从上面的5个同余式来看，这个数一定是7的倍数n≡0(mod 7)，除以6余5，除以5余4，除以3余2，除以2余1，我们为什么不从7的倍数开始判断呢？算法改进见算法1-13。
//算法1-13
#include<iostream>
int main()
{
int n=7; //n为所设的阶梯数
while(!((n%2==1)&&(n%3==2)&&(n%5==4)&&(n%6==5)&&(n%7==0)))
n=n+7; //判别是否满足一组同余式
cout<<"Count the stairs="<<n<<endl; //输出阶梯数
}算法的运行结果：
Count the stairs =119算法1-13中的while语句执行了119/7=17次，可见运行次数减少了不少呢！
（5）问题的进一步讨论
此题算法还可考虑求1、2、4、5的最小公倍数n，然后令t=n−1，判断t≡0(mod 7)是否成立，若不成立则t=t+n，再进行判别，直到选出满足条件的t为止。
1、2、4、5的最小公倍数n=20。
t=n-1=19，t≡0(mod 7)不成立；
t= t+n=39，t≡0(mod 7)不成立；
t= t+n=59，t≡0(mod 7)不成立；
t= t+n=79，t≡0(mod 7)不成立；
t= t+n=99，t≡0(mod 7)不成立；
t= t+n=119，t≡0(mod 7)成立。
我们可以看到这一算法判断6次即成功，但是，求多个数的最小公倍数需要多少时间复杂度，是不是比上面的算法更优呢？结果如何请大家动手试一试。
哥德巴赫猜想：任一大于2的偶数，都可表示成两个素数之和。
验证：2000以内大于2的偶数都能够分解为两个素数之和。
（1）问题分析
为了验证哥德巴赫猜想对2000以内大于2的偶数都是成立的，要将整数分解为两部分（两个整数之和），然后判断分解出的两个整数是否均为素数。若是，则满足题意；否则重新进行分解和判断。素数测试的算法可采用试除法，即用2，3，4，…，
去除n，如果能被整除则为合数，不能被整除则为素数。
（2）算法设计
按照上面的分析进行算法设计，见算法1-14。
//算法1-14
#include<iostream>
#include<math.h>
int prime(int n); //判断是否均为素数
int main()
{
int i,n;
for(i=4;i<=2000;i+=2) //对2000大于2的偶数分解判断，从4开始，每次增2
{
for(n=2;n<i;n++) //将偶数i分解为两个整数，一个整数是n，一个是i-n
if(prime(n)) //判断第一个整数是否均为素数
if(prime(i-n)) //判断第二个整数是否均为素数
{
cout<< i <<"=" << n <<"+"<<i-n<<endl; //若均是素数则输出
break;
}
if(n==i)
cout<<"error "<<endl;
}
}
int prime(int i) //判断是否为素数
{
int j;
if(i<=1) return 0;
if(i==2) return 1;
for(j=2;j<=(int)(sqrt((double)i);j++)
if(!(i%j)) return 0;
return 1;
}（3）算法分析
要验证哥德巴赫猜想对2000以内大于2的偶数都是成立的，我们首先要看看这个范围的偶数有多少个。1～2000中有1000个偶数，1000个奇数，那么大于2的偶数有999个，即i=4，6，8，…，2000。再看偶数分解和素数判断，这就要看最好情况和最坏情况了。最好的情况是一次分解，两次素数判断即可成功，最坏的情况要i−2次分解（即n=2，3，…，i−1的情况），每次分解分别执行2～sqrt(n)次、2～sqrt(i−n)次判断。
这个程序看似简单合理，但存在下面两个问题。
1）偶数分解存在重复。
除了最后一项外，每组分解都在i/2处对称分布。最后一组中有一个数为1，1既不是素数也不是合数，因此去掉最后一组，那么我们就可以从n=2，3，…，i/2进行分解，省掉了一半的多余判断。
2）素数判断存在重复。
每次判断素数都要调用prime函数，那么可以先判断分解有可能得到的数是否为素数，然后把结果存储下来，下次判断时只需要调用上次的结果，不需要再重新判断是否为素数。例如（2，2），第一次判断结果2是素数，那第二个2就不用判断，直接调用这个结果，后面所有的分解，只要遇到这个数就直接认定为这个结果。
（4）算法改进
先判断所有分解可能得到的数是否为素数，然后把结果存储下来，有以下两种方法。
1）用布尔型数组 flag[2..1998]记录分解可能得到的数（2～1998）所有数是不是素数，分解后的值作为下标，调用该数组即可。时间复杂度减少，但空间复杂度增加。
2）用数值型数组data[302]记录2～1998中所有的素数（302个）。
（5）问题的进一步讨论
上面的方法可以写出3个算法，大家可以尝试写一写，然后分析时间复杂度、空间复杂度如何？哪个算法更优一些？是不是还可以做到更好？
很多人感叹：算法为什么这么难！
一个原因是，算法本身具有一定的复杂性，还有一个原因：讲得不到位！
算法的教与学有两个困难。
（1）我们学习了那些经典的算法，在惊叹它们奇妙的同时，难免疑虑重重：这些算法是怎么被想到的？这可能是最费解的地方。高手讲，学算法要学它的来龙去脉，包括种种证明。但这对菜鸟来说，这简直比登天还难，很可能花费很多时间也无法搞清楚。对大多数人来说，这条路是行不通的，那怎么办呢？下功夫去记忆书上的算法？记住这些算法的效率？这样做看似学会了，其实两手空空，遇到一个新问题，仍然无从下手。可这偏偏又是极重要的，无论做研究还是实际工作，一个计算机专业人士最重要的能力就是解决问题——解决那些不断从实际应用中冒出来的新问题。
（2）算法作为一门学问，有两条几乎平行的线索。一个是数据结构（数据对象）：数、矩阵、集合、串、排列、图、表达式、分布等。另一个是算法策略：贪心、分治、动态规划、线性规划、搜索等。这两条线索是相互独立的：同一个数据对象（如图）上有不同的问题（如单源最短路径和多源最短路径），就可以用到不同的算法策略（例如贪婪和动态规划）；而完全不同的数据对象上的问题（如排序和整数乘法），也许就会用到相同的算法策略（如分治）。
两条线索交织在一起，该如何表述？我们早已习惯在一章中完全讲排序，而在另一章中完全讲图论算法。还没有哪一本算法书很好地解决这两个困难，传统的算法书大多注重内容的收录，但却忽视思维过程的展示，因此我们学习了经典的算法，却费解于算法设计的过程。
本书从问题出发，根据实际问题分析、设计合适的算法策略，然后在数据结构上操作实现，巧妙地将数据结构和算法策略拧成了一条线。通过大量实例，充分展现算法设计的思维过程，让读者充分体会求解问题的思路，如何分析？使用什么算法策略？采用什么数据结构？算法的复杂性如何？是否有优化的可能？
这里，我们培养的是让读者怀着一颗好奇心去思考问题、解决问题。更重要的是——体会学习的乐趣，发现算法的美！
本章主要说明以下问题。
（1）将程序执行次数作为时间复杂度衡量标准。
（2）时间复杂度通常用渐近上界符号f(n)表示。
（3）衡量算法的好坏通常考查算法的最坏情况。
（4）空间复杂度只计算辅助空间。
（5）递归算法的空间复杂度要计算递归使用的栈空间。
（6）设计算法时尽量避免爆炸级增量复杂度。
通过本章的学习，我们对算法有了初步的认识，算法就在我们的生活中。任何一个算法都不是凭空造出来的，而是来源于实际中的某一个问题，由此推及一类、一系列问题，所以算法的本质是高效地解决实际问题。本章部分内容或许你不是很清楚，不必灰心，还记得我在前言中说的“大视野，不求甚解”吗？例如斐波那契数列的通项公式推导，不懂没关系，只要知道斐波那契数列用递归算法，时间复杂度是指数阶，这就够了。就像一个面包师一边和面，一边详细讲做好面包要多少面粉、多少酵母、多大火候，如果你对如何做面包非常好奇，大可津津有味地听下去，如果你只是饿了，那么只管吃好了。
通过算法，你可以与世界顶级大师进行灵魂交流，体会算法的妙处。
Donald Ervin Knuth说：“程序就是蓝色的诗”。而这首诗的灵魂就是算法，走进算法，你会发现无与伦比的美！
持之以恒地学习，没有什么是学不会的。行动起来，没有什么不可以！
2.1 人之初，性本贪
2.2 加勒比海盗船——最优装载问题
2.3 阿里巴巴与四十大盗——背包问题
2.4 高级钟点秘书——会议安排
2.5 一场说走就走的旅行——最短路径
2.6 神秘电报密码——哈夫曼编码
2.7 沟通无限校园网——最小生成树
从前，有一个很穷的人救了一条蛇的命，蛇为了报答他的救命之恩，于是就让这个人提出要求，满足他的愿望。这个人一开始只要求简单的衣食，蛇都满足了他的愿望，后来慢慢的贪欲生起，要求做官，蛇也满足了他。这个人直到做了宰相还不满足，还要求做皇帝。蛇此时终于明白了，人的贪心是永无止境的，于是一口就把这个人吞掉了。
所以，蛇吞掉的是宰相，而不是大象。故此，留下了“人心不足蛇吞相”的典故。
我们小时候背诵《三字经》，“人之初，性本善，性相近，习相远。”其实我觉得很多时候“人之初，性本贪”。小孩子吃糖果，总是想要多多的；吃水果，想要最大的；买玩具，总是想要最好的，这些东西并不是大人教的，而是与生俱来的。对美好事物的趋优性，就像植物的趋光性，“良禽择木而栖，贤臣择主而事”“窈窕淑女，君子好逑”，我们似乎永远在追求美而优的东西。现实中的很多事情，正是因为趋优性使我们的生活一步一步走向美好。例如，我们竭尽所能买了一套房子，然后就想要添置一些新的家具，再就想着可能还需要一辆车子……
凡事都有两面性，一把刀可以做出美味佳肴，也可以变成杀人凶器。在这里，我们只谈好的“贪心”。
一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。
——《算法导论》
我们经常会听到这些话：“人要活在当下”“看清楚眼前”……贪心算法正是“活在当下，看清楚眼前”的办法，从问题的初始解开始，一步一歩地做出当前最好的选择，逐步逼近问题的目标，尽可能地得到最优解，即使达不到最优解，也可以得到最优解的近似解。
贪心算法在解决问题的策略上“目光短浅”，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。贪心算法能得到许多问题的整体最优解或整体最优解的近似解。因此，贪心算法在实际中得到大量的应用。
在贪心算法中，我们需要注意以下几个问题。
（1）没有后悔药。一旦做出选择，不可以反悔。
（2）有可能得到的不是最优解，而是最优解的近似解。
（3）选择什么样的贪心策略，直接决定算法的好坏。
那么，贪心算法需要遵循什么样的原则呢？
“君子爱财，取之有道”，我们在贪心算法中“贪亦有道”。通常我们在遇到具体问题时，往往分不清哪些问题该用贪心策略求解，哪些问题不能使用贪心策略。经过实践我们发现，利用贪心算法求解的问题往往具有两个重要的特性：贪心选择性质和最优子结构性质。如果满足这两个性质就可以使用贪心算法了。
（1）贪心选择
所谓贪心选择性质是指原问题的整体最优解可以通过一系列局部最优的选择得到。应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后续的贪心策略状态空间图中得到深刻的体会。
（2）最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题是否可用贪心算法求解的关键。例如原问题S={a1，a2，…，ai，…，an}，通过贪心选择选出一个当前最优解{ai}之后，转化为求解子问题S−{ai}，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质，如图2-1所示。
图2-1 原问题和子问题
武林中有武功秘籍，算法中也有贪心秘籍。上面我们已经知道了具有贪心选择和最优子结构性质就可以使用贪心算法，那么如何使用呢？下面介绍贪心算法秘籍。
（1）贪心策略
首先要确定贪心策略，选择当前看上去最好的一个方案。例如，挑选苹果，如果你认为个大的是最好的，那你每次都从苹果堆中拿一个最大的，作为局部最优解，贪心策略就是选择当前最大的苹果；如果你认为最红的苹果是最好的，那你每次都从苹果堆中拿一个最红的，贪心策略就是选择当前最红的苹果。因此根据求解目标不同，贪心策略也会不同。
（2）局部最优解
根据贪心策略，一步一步地得到局部最优解。例如，第一次选一个最大的苹果放起来，记为a1，第二次再从剩下的苹果堆中选择一个最大的苹果放起来，记为a2，以此类推。
（3）全局最优解
把所有的局部最优解合成为原来问题的一个最优解（a1，a2，…）。
怎么有点儿像冒泡排序啊？
“不是六郎似荷花，而是荷花似六郎”！不是贪心算法像冒泡排序，而是冒泡排序使用了贪心算法，它的贪心策略就是每一次从剩下的序列中选一个最大的数，把这些选出来的数放在一起，就得到了从大到小的排序结果，如图2-2所示。
图2-2 冒泡排序
在北美洲东南部，有一片神秘的海域，那里碧海蓝天、阳光明媚，这正是传说中海盗最活跃的加勒比海（Caribbean Sea）。17世纪时，这里更是欧洲大陆的商旅舰队到达美洲的必经之地，所以当时的海盗活动非常猖獗，海盗不仅攻击过往商人，甚至攻击英国皇家舰……
有一天，海盗们截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一旦打碎就失去了它的价值。虽然海盗船足够大，但载重量为C，每件古董的重量为wi，海盗们该如何把尽可能多数量的宝贝装上海盗船呢？
图2-3 加勒比海盗
根据问题描述可知这是一个可以用贪心算法求解的最优装载问题，要求装载的物品的数量尽可能多，而船的容量是固定的，那么优先把重量小的物品放进去，在容量固定的情况下，装的物品最多。采用重量最轻者先装的贪心选择策略，从局部最优达到全局最优，从而产生最优装载问题的最优解。
（1）当载重量为定值c时，wi越小时，可装载的古董数量n越大。只要依次选择最小重量古董，直到不能再装为止。
（2）把n个古董的重量从小到大（非递减）排序，然后根据贪心策略尽可能多地选出前i个古董，直到不能继续装为止，此时达到最优。
我们现在假设这批古董如图2-4所示。
图2-4 古董图片
每个古董的重量如表2-1所示，海盗船的载重量c为30，那么在不能打碎古董又不超过载重的情况下，怎么装入最多的古董？
表2-1 古董重量清单
| 重量w[i] | 4 | 10 | 7 | 11 | 3 | 5 | 14 | 2 |
|---|
（1）因为贪心策略是每次选择重量最小的古董装入海盗船，因此可以按照古董重量非递减排序，排序后如表2-2所示。
表2-2 按重量排序后古董清单
| 重量w[i] | 2 | 3 | 4 | 5 | 7 | 10 | 11 | 14 |
|---|
（2）按照贪心策略，每次选择重量最小的古董放入（tmp 代表古董的重量，ans 代表已装裁的古董个数）。
i=0，选择排序后的第1个，装入重量tmp=2，不超过载重量30，ans =1。
i=1，选择排序后的第2个，装入重量tmp=2+3=5，不超过载重量30，ans =2。
i=2，选择排序后的第3个，装入重量tmp=5+4=9，不超过载重量30，ans =3。
i=3，选择排序后的第4个，装入重量tmp=9+5=14，不超过载重量30，ans =4。
i=4，选择排序后的第5个，装入重量tmp=14+7=21，不超过载重量30，ans =5。
i=5，选择排序后的第6个，装入重量tmp=21+10=31，超过载重量30，算法结束。
即放入古董的个数为ans=5个。
（1）数据结构定义
根据算法设计描述，我们用一维数组存储古董的重量：
double w[N]; //一维数组存储古董的重量（2）按重量排序
可以利用C++中的排序函数sort（见附录B），对古董的重量进行从小到大（非递减）排序。要使用此函数需引入头文件：
#include <algorithm>语法描述为：
sort(begin, end)//参数begin和end表示一个范围，分别为待排序数组的首地址和尾地址
//sort函数默认为升序在本例中只需要调用sort函数对古董的重量进行从小到大排序：
sort(w, w+n); //按古董重量升序排序（3）按照贪心策略找最优解
首先用变量ans记录已经装载的古董个数，tmp代表装载到船上的古董的重量，两个变量都初始化为0。然后按照重量从小到大排序，依次检查每个古董，tmp加上该古董的重量，如果小于等于载重量c，则令ans ++；否则，退出。
int tmp = 0,ans = 0; //tmp代表装载到船上的古董的重量，ans记录已经装载的古董个数
for(int i=0;i<n;i++)
{
tmp += w[i];
if(tmp<=c)
ans ++;
else
break;
}//program 2-1
#include <iostream>
#include <algorithm>
const int N = 1000005;
using namespace std;
double w[N]; //古董的重量数组
int main()
{
double c;
int n;
cout<<"请输入载重量c及古董个数n："<<endl;
cin>>c>>n;
cout<<"请输入每个古董的重量，用空格分开： "<<endl;
for(int i=0;i<n;i++)
{
cin>>w[i]; //输入每个物品重量
}
sort(w,w+n); //按古董重量升序排序
double temp=0.0;
int ans=0; // tmp为已装载到船上的古董重量，ans为已装载的古董个数
for(int i=0;i<n;i++)
{
tmp+=w[i];
if(tmp<=c)
ans ++;
else
break;
}
cout<<"能装入的古董最大数量为Ans=";
cout<<ans<<endl;
return 0;
}算法实现和测试
（1）运行环境
Code::Blocks
（2）输入
请输入载重量c及古董个数n：
30 8 //载重量c及古董的个数n
请输入每个古董的重量，用空格分开：
4 10 7 11 3 5 14 2 //每个古董的重量，用空格隔开（3）输出
能装入的古董最大数量为Ans=5（1）时间复杂度：首先需要按古董重量排序，调用sort函数，其平均时间复杂度为O(nlogn)，输入和贪心策略求解的两个for语句时间复杂度均为O(n)，因此时间复杂度为O(n + nlog(n))。
（2）空间复杂度：程序中变量tmp、ans等占用了一些辅助空间，这些辅助空间都是常数阶的，因此空间复杂度为O(1)。
（1）这一个问题为什么在没有装满的情况下，仍然是最优解？算法要求装入最多数量，假如c为5，4个物品重量分别为1、3、5、7。排序后，可以装入1和3，最多装入两个。分析发现是最优的，如果装大的物品，最多装一个或者装不下，所以选最小的先装才能装入最多的数量，得到解是最优的。
（2）在伪代码详解的第3步“按照贪心策略找最优解”，如果把代码替换成下面代码，有什么不同？
首先用变量ans记录已经装载的古董个数，初始化为n；tmp代表装载到船上的古董的重量，初始化为0。然后按照重量从小到大排序，依次检查每个古董，tmp加上该古董的重量，如果tmp大于等于载重量c，则判断是否正好等于载重量c，并令ans=i+1；否则ans = i，退出。如果tmp小于载重量c，i++，继续下一个循环。
int tmp = 0,ans = n; //ans记录已经装载的古董个数，tmp代表装载到船上的古董的重量
for(int i=0;i<n;i++)
{
tmp += w[i];
if(tmp>=c)
{
if(tmp==c) //假如刚好，最后一个可以放
ans = i+1;
else
ans = i; //如果满了，最后一个不能放
break;
}
}（3）如果想知道装入了哪些古董，需要添加什么程序来实现呢？请大家动手试一试吧！
那么，还有没有更好的算法来解决这个问题呢？
有一天，阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时，远处突然出现一股烟尘，弥漫着直向上空飞扬，朝他这儿卷过来，而且越来越近。靠近以后，他才看清原来是一支马队，他们共有四十人，一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋，从丛林中一直来到那个大石头跟前，喃喃地说道：“芝麻，开门吧！”随着那个头目的喊声，大石头前突然出现一道宽阔的门路，于是强盗们鱼贯而入。阿里巴巴待在树上观察他们，直到他们走得无影无踪之后，才从树上下来。他大声喊道：“芝麻，开门吧！”他的喊声刚落，洞门立刻打开了。他小心翼翼地走了进去，一下子惊呆了，洞中堆满了财物，还有多得无法计数的金银珠宝，有的散堆在地上，有的盛在皮袋中。突然看见这么多的金银财富，阿里巴巴深信这肯定是一个强盗们数代经营、掠夺所积累起来的宝窟。为了让乡亲们开开眼界，见识一下这些宝物，他想一种宝物只拿一个，如果太重就用锤子凿开，但毛驴的运载能力是有限的，怎么才能用驴子运走最大价值的财宝分给穷人呢？
阿里巴巴陷入沉思中……
图2-5 阿里巴巴与四十大盗
假设山洞中有n种宝物，每种宝物有一定重量w和相应的价值v，毛驴运载能力有限，只能运走m重量的宝物，一种宝物只能拿一样，宝物可以分割。那么怎么才能使毛驴运走宝物的价值最大呢？
我们可以尝试贪心策略：
（1）每次挑选价值最大的宝物装入背包，得到的结果是否最优？
（2）每次挑选重量最小的宝物装入，能否得到最优解？
（3）每次选取单位重量价值最大的宝物，能否使价值最高？
思考一下，如果选价值最大的宝物，但重量非常大，也是不行的，因为运载能力是有限的，所以第1种策略舍弃；如果选重量最小的物品装入，那么其价值不一定高，所以不能在总重限制的情况下保证价值最大，第2种策略舍弃；而第3种是每次选取单位重量价值最大的宝物，也就是说每次选择性价比（价值/重量）最高的宝物，如果可以达到运载重量m，那么一定能得到价值最大。
因此采用第3种贪心策略，每次从剩下的宝物中选择性价比最高的宝物。
（1）数据结构及初始化。将n种宝物的重量和价值存储在结构体three（包含重量、价值、性价比3个成员）中，同时求出每种宝物的性价比也存储在对应的结构体three中，将其按照性价比从高到低排序。采用sum来存储毛驴能够运走的最大价值，初始化为0。
（2）根据贪心策略，按照性价比从大到小选取宝物，直到达到毛驴的运载能力。每次选择性价比高的物品，判断是否小于m（毛驴运载能力），如果小于m，则放入，sum（已放入物品的价值）加上当前宝物的价值，m减去放入宝物的重量；如果不小于m，则取该宝物的一部分m * p[i]，m=0，程序结束。m减少到0，则sum得到最大值。
假设现在有一批宝物，价值和重量如表 2-3 所示，毛驴运载能力 m=30，那么怎么装入最大价值的物品？
表2-3 宝物清单
| 宝物i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 重量w[i] | 4 | 2 | 9 | 5 | 5 | 8 | 5 | 4 | 5 | 5 |
| 价值v[i] | 3 | 8 | 18 | 6 | 8 | 20 | 5 | 6 | 7 | 15 |
（1）因为贪心策略是每次选择性价比（价值/重量）高的宝物，可以按照性价比降序排序，排序后如表2-4所示。
表2-4 排序后宝物清单
| 宝物i | 2 | 10 | 6 | 3 | 5 | 8 | 9 | 4 | 7 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|
| 重量w[i] | 2 | 5 | 8 | 9 | 5 | 4 | 5 | 5 | 5 | 4 |
| 价值v[i] | 8 | 15 | 20 | 18 | 8 | 6 | 7 | 6 | 5 | 3 |
| 性价比p[i] | 4 | 3 | 2.5 | 2 | 1.6 | 1.5 | 1.4 | 1.2 | 1 | 0.75 |
（2）按照贪心策略，每次选择性价比高的宝物放入：
第1次选择宝物2，剩余容量30−2=28，目前装入最大价值为8。
第2次选择宝物10，剩余容量28−5=23，目前装入最大价值为8+15=23。
第3次选择宝物6，剩余容量23−8=15，目前装入最大价值为23+20=43。
第4次选择宝物3，剩余容量15−9=6，目前装入最大价值为43+18=61。
第5次选择宝物5，剩余容量6−5=1，目前装入最大价值为61+8=69。
第6次选择宝物8，发现上次处理完时剩余容量为1，而8号宝物重量为4，无法全部放入，那么可以采用部分装入的形式，装入1个重量单位，因为8号宝物的单位重量价值为1.5，因此放入价值1×1.5=1.5，你也可以认为装入了8号宝物的1/4，目前装入最大价值为69+1.5=70.5，剩余容量为0。
（3）构造最优解
把这些放入的宝物序号组合在一起，就得到了最优解（2，10，6，3，5，8），其中最后一个宝物为部分装入（装了8号财宝的1/4），能够装入宝物的最大价值为70.5。
（1）数据结构定义
根据算法设计中的数据结构，我们首先定义一个结构体three：
struct three{
double w; //每种宝物的重量
double v; //每种宝物的价值
double p; //每种宝物的性价比（价值/重量）
｝（2）性价比排序
我们可以利用C++中的排序函数sort（见附录B），对宝物的性价比从大到小（非递增）排序。要使用此函数需引入头文件：
#include <algorithm>语法描述为：
sort(begin, end)// 参数begin和end表示一个范围，分别为待排序数组的首地址和尾地址在本例中我们采用结构体形式存储，按结构体中的一个字段，即按性价比排序。如果不使用自定义比较函数，那么sort函数排序时不知道按哪一项的值排序，因此采用自定义比较函数的办法实现宝物性价比的降序排序：
bool cmp(three a,three b)//比较函数按照宝物性价比降序排列
{
return a.p > b.p; //指明按照宝物性价比降序排列
}
sort(s, s+n, cmp); //前两个参数分别为待排序数组的首地址和尾地址
//最后一个参数compare表示比较的类型（3）贪心算法求解
在性价比排序的基础上，进行贪心算法运算。如果剩余容量比当前宝物的重量大，则可以放入，剩余容量减去当前宝物的重量，已放入物品的价值加上当前宝物的价值。如果剩余容量比当前宝物的重量小，表示不可以全部放入，可以切割下来一部分（正好是剩余容量），然后令剩余容量乘以当前物品的单位重量价值，已放入物品的价值加上该价值，即为能放入宝物的最大价值。
for(int i = 0;i < n;i++)//按照排好的顺序，执行贪心策略
{
if( m > s[i].w )//如果宝物的重量小于毛驴剩下的运载能力，即剩余容量
{
m -= s[i].w;
sum += s[i].v;
}
else //如果宝物的重量大于毛驴剩下的承载能力
{
sum += m乘以s[i].p; //进行宝物切割，切割一部分(m重量)，正好达到驴子承重
break;
}
}//program 2-2
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1000005;
struct three{
double w;//每个宝物的重量
double v;//每个宝物的价值
double p;//性价比
}s[M];
bool cmp(three a,three b)
{
return a.p>b.p;//根据宝物的单位价值从大到小排序
}
int main()
{
int n;//n 表示有n个宝物
double m ;//m 表示毛驴的承载能力
cout<<"请输入宝物数量n及毛驴的承载能力m ："<<endl;
cin>>n>>m;
cout<<"请输入每个宝物的重量和价值，用空格分开： "<<endl;
for(int i=0;i<n;i++)
{
cin>>s[i].w>>s[i].v;
s[i].p=s[i].v/s[i].w;//每个宝物单位价值
}
sort(s,s+n,cmp);
double sum=0.0;// sum表示贪心记录运走宝物的价值之和
for(int i=0;i<n;i++)//按照排好的顺序贪心
{
if( m>s[i].w )//如果宝物的重量小于毛驴剩下的承载能力
{
m-=s[i].w;
sum+=s[i].v;
}
else//如果宝物的重量大于毛驴剩下的承载能力
{
sum+=m*s[i].p;//部分装入
break;
}
}
cout<<"装入宝物的最大价值Maximum value="<<sum<<endl;
return 0;
}算法实现和测试
（1）运行环境
Code::Blocks
（2）输入
6 19 //宝物数量，驴子的承载重量
2 8 //第1个宝物的重量和价值
6 1 //第2个宝物的重量和价值
7 9
4 3
10 2
3 4（3）输出
Maxinum value=24.6（1）时间复杂度：该算法的时间主要耗费在将宝物按照性价比排序上，采用的是快速排序，算法时间复杂度为O(nlogn)。
（2）空间复杂度：空间主要耗费在存储宝物的性价比，空间复杂度为O(n)。
为了使 m 重量里的所有物品的价值最大，利用贪心思想，每次取剩下物品里面性价比最高的物品，这样可以使得在相同重量条件下比选其他物品所得到的价值更大，因此采用贪心策略能得到最优解。
那么想一想，如果宝物不可分割，贪心算法是否能得到最优解？
下面我们看一个简单的例子。
假定物品的重量和价值已知，如表2-5所示，最大运载能力为10。采用贪心算法会得到怎样的结果？
表2-5 物品清单
| 物品i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 重量w[i] | 3 | 4 | 6 | 10 | 7 |
| 价值v[i] | 15 | 16 | 18 | 25 | 14 |
| 性价比p[i] | 5 | 4 | 3 | 2.5 | 2 |
如果我们采用贪心算法，先装性价比高的物品，且物品不能分割，剩余容量如果无法再装入剩余的物品，不管还有没有运载能力，算法都会结束。那么我们选择的物品为 1和2，总价值为 31，而实际上还有 3 个剩余容量，但不足以装下剩余其他物品，因此得到的最大价值为31。但实际上我们如果选择物品2和3，正好达到运载能力，得到的最大价值为34。也就是说，在物品不可分割、没法装满的情况下，贪心算法并不能得到最优解，仅仅是最优解的近似解。
想一想，为什么会这样呢？
物品可分割的装载问题我们称为背包问题，物品不可分割的装载问题我们称之为0-1背包问题。
在物品不可分割的情况下，即0-1背包问题，已经不具有贪心选择性质，原问题的整体最优解无法通过一系列局部最优的选择得到，因此这类问题得到的是近似解。如果一个问题不要求得到最优解，而只需要一个最优解的近似解，则不管该问题有没有贪心选择性质都可以使用贪心算法。
想一想，2.3节中加勒比海盗船问题为什么在没有装满的情况下，仍然是最优解，而0-1背包问题在没装满的情况下有可能只是最优解的近似解？
所谓“钟点秘书”，是指年轻白领女性利用工余时间为客户提供秘书服务，并按钟点收取酬金。
“钟点秘书”为客户提供有偿服务的方式一般是：采用电话、电传、上网等“遥控”式服务，或亲自到客户公司处理部分业务。其服务对象主要有三类：一是外地前来考察商务经营、项目投资的商人或政要人员，他们由于初来乍到，急需有经验和熟悉本地情况的秘书帮忙；二是前来开展短暂商务活动，或召开小型资讯发布会的国外客商；三是本地一些请不起长期秘书的企、事业单位。这些客户普遍认为：请“钟点秘书”，一则可免去专门租楼请人的大笔开销；二则可根据开展的商务活动请有某方面专长的可用人才；三则由于对方是临时雇用关系，工作效率往往比固定的秘书更高。据调查，在上海“钟点秘书”的行情日趋看好。对此，业内人士认为：为了便于管理，各大城市有必要组建若干家“钟点秘书服务公司”，通过会员制的形式，为众多客户提供规范、优良、全面的服务，这也是建设国际化大都市所必需的。
某跨国公司总裁正分身无术，为一大堆会议时间表焦头烂额，希望高级钟点秘书能做出合理的安排，能在有限的时间内召开更多的会议。
图2-6 高级钟点秘书
这是一个典型的会议安排问题，会议安排的目的是能在有限的时间内召开更多的会议（任何两个会议不能同时进行）。在会议安排中，每个会议i都有起始时间bi和结束时间ei，且bi<ei，即一个会议进行的时间为半开区间[bi，ei）。如果[bi，ei）与[bj，ej）均在“有限的时间内”，且不相交，则称会议i与会议j相容的。也就是说，当biej或bjei时，会议i与会议j相容。会议安排问题要求在所给的会议集合中选出最大的相容活动子集，即尽可能在有限的时间内召开更多的会议。
在这个问题中，“有限的时间内（这段时间应该是连续的）”是其中的一个限制条件，也应该是有一个起始时间和一个结束时间（简单化，起始时间可以是会议最早开始的时间，结束时间可以是会议最晚结束的时间），任务就是实现召开更多的满足在这个“有限的时间内”等待安排的会议，会议时间表如表2-6所示。
表2-6 会议时间表
| 会议i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 开始时间bi | 8 | 9 | 10 | 11 | 13 | 14 | 15 | 17 | 18 | 16 |
| 结束时间ei | 10 | 11 | 15 | 14 | 16 | 17 | 17 | 18 | 20 | 19 |
会议安排的时间段如图2-7所示。
图2-7 会议安排时间段
从图2-7中可以看出，{会议1，会议4，会议6，会议8，会议9}，{会议2，会议4，会议7，会议8，会议9}都是能安排最多的会议集合。
要让会议数最多，我们需要选择最多的不相交时间段。我们可以尝试贪心策略：
（1）每次从剩下未安排的会议中选择会议具有最早开始时间且与已安排的会议相容的会议安排，以增大时间资源的利用率。
（2）每次从剩下未安排的会议中选择持续时间最短且与已安排的会议相容的会议安排，这样可以安排更多一些的会议。
（3）每次从剩下未安排的会议中选择具有最早结束时间且与已安排的会议相容的会议安排，这样可以尽快安排下一个会议。
思考一下，如果选择最早开始时间，则如果会议持续时间很长，例如8点开始，却要持续12个小时，这样一天就只能安排一个会议；如果选择持续时间最短，则可能开始时间很晚，例如19点开始，20点结束，这样也只能安排一个会议，所以我们最好选择那些开始时间要早，而且持续时间短的会议，即最早开始时间+持续时间最短，就是最早结束时间。
因此采用第（3）种贪心策略，每次从剩下的会议中选择具有最早结束时间且与已安排的会议相容的会议安排。
（1）初始化：将n个会议的开始时间、结束时间存放在结构体数组中（想一想，为什么不用两个一维数组分别存储？），如果需要知道选中了哪些会议，还需要在结构体中增加会议编号，然后按结束时间从小到大排序（非递减），结束时间相等时，按开始时间从大到小排序（非递增）；
（2）根据贪心策略就是选择第一个具有最早结束时间的会议，用last记录刚选中会议的结束时间；
（3）选择第一个会议之后，依次从剩下未安排的会议中选择，如果会议i开始时间大于等于最后一个选中的会议的结束时间last，那么会议i与已选中的会议相容，可以安排，更新last为刚选中会议的结束时间；否则，舍弃会议i，检查下一个会议是否可以安排。
表2-7 原始会议时间表
| 会议num | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 开始时间beg | 3 | 1 | 5 | 2 | 5 | 3 | 8 | 6 | 8 | 12 |
| 结束时间end | 6 | 4 | 7 | 5 | 9 | 8 | 11 | 10 | 12 | 14 |
表2-8 排序后的会议时间表
| 会议num | 2 | 4 | 1 | 3 | 6 | 5 | 8 | 7 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 开始时间beg | 1 | 2 | 3 | 5 | 3 | 5 | 6 | 8 | 8 | 12 |
| 结束时间end | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 14 |
（1）首先选择排序后的第一个会议即最早结束的会议（编号为2），用last记录最后一个被选中会议的结束时间，last=4。
（2）检查余下的会议，找到第一个开始时间大于等于 last（last=4）的会议，子问题转化为从该会议开始，余下的所有会议。如表2-9所示。
表2-9 会议时间表
从子问题中，选择第一个会议即最早结束的会议（编号为3），更新last为刚选中会议的结束时间last=7。
（3）检查余下的会议，找到第一个开始时间大于等于last（last=7）的会议，子问题转化为从该会议开始，余下的所有会议。如表2-10所示。
表2-10 会议时间表
从子问题中，选择第一个会议即最早结束的会议（编号为 7），更新 last 为刚选中会议的结束时间last=11。
（4）检查余下的会议，找到第一个开始时间大于等于last（last=11）的会议，子问题转化为从该会议开始，余下的所有会议。如表2-11所示。
表2-11 会议时间表
从子问题中，选择第一个会议即最早结束的会议（编号为10），更新last为刚选中会议的结束时间last=14；所有会议检查完毕，算法结束。如表2-12所示。
从贪心选择的结果，可以看出，被选中的会议编号为{2，3，7，10}，可以安排的会议数量最多为4，如表2-12所示。
表2-12 会议时间表
（1）数据结构定义
以下C++程序代码中，结构体meet中定义了beg表示会议的开始时间，end表示会议的结束时间，会议meet的数据结构：
struct Meet
{
int beg; //会议的开始时间
int end; //会议的结束时间
} meet[1000]；（2）对会议按照结束时间非递减排序
我们采用C++中自带的sort函数，自定义比较函数的办法，实现会议排序，按结束时间从小到大排序（非递减），结束时间相等时，按开始时间从大到小排序（非递增）：
bool cmp(Meet x,Meet y)
{
if(x.end==y.end) //结束时间相等时
return x.beg>y.beg; //按开始时间从大到小排序
return x.end<y.end; //按结束时间从小到大排序
}
sort(meet,meet+n,cmp);（3）会议安排问题的贪心算法求解
在会议按结束时间非递减排序的基础上，首先选中第一个会议，用last变量记录刚刚被选中会议的结束时间。下一个会议的开始时间与last比较，如果大于等于last，则选中。每次选中一个会议，更新last为最后一个被选中会议的结束时间，被选中的会议数ans加1；如果会议的开始时间不大于等于last，继续考查下一个会议，直到所有会议考查完毕。
int ans=1; //用来记录可以安排会议的个数，初始时选中了第一个会议
int last = meet[0].end; //last记录第一个会议的结束时间
for( i = 1;i < n; i++) //依次检查每个会议
{
if(meet[i].beg > =last)
{ //如果会议i开始时间大于等于最后一个选中的会议的结束时间
ans++;
last = meet[i].end; //更新last为最后一个选中会议的结束时间
}
}
return ans; //返回可以安排的会议最大数上面介绍的程序中，只是返回了可以安排的会议最大数，而不知道安排了哪些会议，这显然是不满足需要的。我们可以改进一下，在会议结构体meet中添加会议编号num变量，选中会议时，显示选中了第几个会议。
//program 2-3
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct Meet
{
int beg; //会议的开始时间
int end; //会议的结束时间
int num; //记录会议的编号
}meet[1000]; //会议的最大个数为1000
class setMeet{
public:
void init();
void solve();
private:
int n,ans; // n:会议总数 ans: 最大的安排会议总数
};
//读入数据
void setMeet::init()
{
int s,e;
cout <<"输入会议总数："<<endl;
cin >> n;
int i;
cout <<"输入会议的开始时间和结束时间，以空格分开："<<endl;
for(i=0;i<n;++i)
{
cin>>s>>e;
meet[i].beg=s;
meet[i].end=e;
meet[i].num=i+1;
}
}
bool cmp(Meet x,Meet y)
{
if (x.end == y.end)
return x.beg > y.beg;
return x.end < y.end;
}
void setMeet::solve()
{
sort(meet,meet+n,cmp); //对会议按结束时间排序
cout <<"排完序的会议时间如下："<<endl;
int i;
cout <<"会议编号"<<" 开始时间 "<<" 结束时间"<<endl;
for(i=0; i<n;i++)
{
cout<< " " << meet[i].num<<"\t\t"<<meet[i].beg <<"\t"<< meet[i].end << endl;
}
cout <<"-------------------------------------------------"<<endl;
cout << "选择的会议的过程：" <<endl;
cout <<" 选择第"<< meet[0].num<<"个会议" << endl;//选中了第一个会议
ans=1;
int last = meet[0].end; //记录刚刚被选中会议的结束时间
for( i = 1;i < n;++i)
{
if(meet[i].beg>=last)
{ //如果会议i开始时间大于等于最后一个选中的会议的结束时间
ans++;
last = meet[i].end;
cout <<" 选择第"<<meet[i].num<<"个会议"<<endl;
}
}
cout <<"最多可以安排" <<ans << "个会议"<<endl;
}
int main()
{
setMeet sm;
sm.init();//读入数据
sm.solve();//贪心算法求解
return 0;
}算法实现和测试
（1）运行环境
Code::Blocks
（2）输入
输入会议总数：
10
输入会议的开始时间和结束时间，以空格分开：
3 6
1 4
5 7
2 5
5 9
3 8
8 11
6 10
8 12
12 14（3）输出
排完序的会议时间如下：
会议编号 开始时间 结束时间
2 1 4
4 2 5
1 3 6
3 5 7
6 3 8
5 5 9
8 6 10
7 8 11
9 8 12
10 12 14
-------------------------------------------------
选择的会议的过程：
选择第2个会议
选择第3个会议
选择第7个会议
选择第10个会议
最多可以安排4个会议使用上面贪心算法可得，选择的会议是第2、3、7、10个会议，输出最优值是4。
（1）时间复杂度：在该算法中，问题的规模就是会议总个数n。显然，执行次数随问题规模的增大而变化。首先在成员函数setMeet::init()中，输入n个结构体数据。输入作为基本语句，显然，共执行n次。而后在调用成员函数setMeet::solve()中进行排序，易知sort排序函数的平均时间复杂度为O(nlogn)。随后进行选择会议，贡献最大的为if(meet[i].beg>=last)语句，时间复杂度为O(n)，总时间复杂度为O(n +nlogn)= O(nlogn)。
（2）空间复杂度：在该算法中，meet[]结构体数组为输入数据，不计算在空间复杂度内。辅助空间有i、n、ans等变量，则该程序空间复杂度为常数阶，即O(1)。
想一想，你有没有更好的办法来处理此问题，比如有更小的算法时间复杂度？
有一天，孩子回来对我说：“妈妈，听说马尔代夫很不错，放假了我想去玩。”马尔代夫？我也想去！没有人不向往一场说走就走的旅行！“其实我想去的地方很多，呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”小孩子还说着他感兴趣的地方。于是我们拿出地图，标出想去的地点，然后计算最短路线，估算大约所需的时间，有了这张秘制地图，一场说走就走的旅行不是梦！
“哇，感觉我们像凡尔纳的《环游地球八十天》，好激动！可是老妈你也太out了，学计算机的最短路线你用手算？”
暴汗……，“小子你别牛，你知道怎么算？”
“呃，好像是叫什么迪科斯彻的人会算。”
哈哈，关键时刻还要老妈上场了！
图2-8 一场说走就走的旅行
根据题目描述可知，这是一个求单源最短路径的问题。给定有向带权图G =（V，Ｅ），其中每条边的权是非负实数。此外，给定V中的一个顶点，称为源点。现在要计算从源到所有其他各顶点的最短路径长度，这里路径长度指路上各边的权之和。
如何求源点到其他各点的最短路径呢？
如图2-9所示，艾兹格•W•迪科斯彻（Edsger Wybe Dijkstra），荷兰人，计算机科学家。他早年钻研物理及数学，后转而研究计算学。他曾在1972年获得过素有“计算机科学界的诺贝尔奖”之称的图灵奖，与Donald Ervin Knuth并称为我们这个时代最伟大的计算机科学家。
图2-9 艾兹格•W•迪科斯彻
Dijkstra 算法是解决单源最短路径问题的贪心算法，它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个顶点的最短路径。
Dijkstra算法的基本思想是首先假定源点为u，顶点集合V被划分为两部分：集合S和 V−S。初始时 S 中仅含有源点 u，其中 S 中的顶点到源点的最短路径已经确定。集合V−S中所包含的顶点到源点的最短路径的长度待定，称从源点出发只经过S中的点到达V−S中的点的路径为特殊路径，并用数组dist[]记录当前每个顶点所对应的最短特殊路径长度。
Dijkstra算法采用的贪心策略是选择特殊路径长度最短的路径，将其连接的V−S中的顶点加入到集合S中，同时更新数组dist[]。一旦S包含了所有顶点，dist[]就是从源到所有其他顶点之间的最短路径长度。
（1）数据结构。设置地图的带权邻接矩阵为map[][]，即如果从源点u到顶点i有边，就令 map[u][i]等于<u，i>的权值，否则 map[u][i]=∞（无穷大）；采用一维数组 dist[i]来记录从源点到i顶点的最短路径长度；采用一维数组p[i]来记录最短路径上i顶点的前驱。
（2）初始化。令集合S={u}，对于集合V−S中的所有顶点x，初始化dist[i]=map[u][i]，如果源点u到顶点i有边相连，初始化p[i]=u，否则p[i]= −1。
（3）找最小。在集合V−S中依照贪心策略来寻找使得dist[j]具有最小值的顶点t，即dist[t]=min（dist[j]|j属于V−S集合），则顶点t就是集合V−S中距离源点u最近的顶点。
（4）加入S战队。将顶点t加入集合S中，同时更新V−S。
（5）判结束。如果集合V−S为空，算法结束，否则转（6）。
（6）借东风。在（3）中已经找到了源点到t的最短路径，那么对集合V−S中所有与顶点t相邻的顶点j，都可以借助t走捷径。如果dis[j]>dist[t]+map[t][j]，则dist[j]=dist[t]+map[t][j]，记录顶点j的前驱为t，有p[j]= t，转（3）。
由此，可求得从源点u到图G的其余各个顶点的最短路径及长度，也可通过数组p[]逆向找到最短路径上经过的城市。
现在我们有一个景点地图，如图2-10所示，假设从1号结点出发，求到其他各个结点的最短路径。
图2-10 景点地图
算法步骤如下。
（1）数据结构
设置地图的带权邻接矩阵为map[][]，即如果从顶点i到顶点j有边，则map[i][j]等于<i，j>的权值，否则map[i][j]=∞（无穷大），如图2-11所示。
图2-11 邻接矩阵map[][]
（2）初始化
令集合S={1}，V−S={2，3，4，5}，对于集合V−S中的所有顶点x，初始化最短距离数组dist[i]=map[1][i]，dist[u]=0，如图2-12所示。如果源点1到顶点i有边相连，初始化前驱数组p[i]=1，否则p[i]= −1，如图2-13所示。
图2-12 最短距离数组dist[]
图2-13 前驱数组p[]
（3）找最小
在集合V−S={2，3，4，5}中，依照贪心策略来寻找V−S集合中dist[]最小的顶点t，如图2-14所示。
图2-14 最短距离数组dist[]
找到最小值为2，对应的结点t=2。
（4）加入S战队
将顶点t=2加入集合S中S={1，2}，同时更新V−S={3，4，5}，如图2-15所示。
图2-15 景点地图
（5）借东风
刚刚找到了源点到t=2的最短路径，那么对集合V−S中所有t的邻接点j，都可以借助t走捷径。我们从图或邻接矩阵都可以看出，2号结点的邻接点是3和4号结点，如图2-16所示。
图2-16 邻接矩阵map[][]
先看3号结点能否借助2号走捷径：dist[2]+map[2][3]=2+2=4，而当前dist[3]=5>4，因此可以走捷径即2—3，更新dist[3]=4，记录顶点3的前驱为2，即p[3]= 2。
再看4号结点能否借助2号走捷径：如果dist[2]+map[2][4]=2+6=8，而当前dist[4]=∞>8，因此可以走捷径即2—4，更新dist[4]=8，记录顶点4的前驱为2，即p[4]= 2。
更新后如图2-17和图2-18所示。
图2-17 最短距离数组dist[]
图2-18 前驱数组p[]
（6）找最小
在集合V−S={3，4，5}中，依照贪心策略来寻找dist[]具有最小值的顶点t，依照贪心策略来寻找V−S集合中dist[]最小的顶点t，如图2-19所示。
图2-19 最短距离数组dist[]
找到最小值为4，对应的结点t=3。
（7）加入S战队
将顶点t=3加入集合S中S={1，2，3}，同时更新V−S={4，5}，如图2-20所示。
图2-20 景点地图
（8）借东风
刚刚找到了源点到t =3的最短路径，那么对集合V−S中所有t的邻接点j，都可以借助t走捷径。我们从图或邻接矩阵可以看出，3号结点的邻接点是4和5号结点。
先看4号结点能否借助3号走捷径：dist[3]+map[3][4]=4+7=11，而当前dist[4]=8<11，比当前路径还长，因此不更新。
再看5号结点能否借助3号走捷径：dist[3]+map[3][5]=4+1=5，而当前dist[5]=∞>5，因此可以走捷径即3—5，更新dist[5]=5，记录顶点5的前驱为3，即p[5]=3。
更新后如图2-21和图2-22所示。
图2-21 最短距离数组dist[]
图2-22 前驱数组p[]
（9）找最小
在集合V−S={4，5}中，依照贪心策略来寻找V−S集合中dist[]最小的顶点t，如图2-23所示。
图2-23 最短距离数组dist[]
找到最小值为5，对应的结点t=5。
（10）加入S战队
将顶点t=5加入集合S中S={1，2，3，5}，同时更新V−S={4}，如图2-24所示。
图2-24 景点地图
（11）借东风
刚刚找到了源点到t =5的最短路径，那么对集合V−S中所有t的邻接点j，都可以借助t走捷径。我们从图或邻接矩阵可以看出，5号结点没有邻接点，因此不更新，如图2-25和图2-26所示。
图2-25 最短距离数组dist[]
图2-26 前驱数组p[]
（12）找最小
在集合V−S={4}中，依照贪心策略来寻找dist[]最小的顶点t，只有一个顶点，所以很容易找到，如图2-27所示。
图2-27 最短距离数组dist[]
找到最小值为8，对应的结点t=4。
（13）加入S战队
将顶点t加入集合S中S={1，2，3，5，4}，同时更新V−S={ }，如图2-28所示。
图2-28 景点地图
（14）算法结束
V−S={ }为空时，算法停止。
由此，可求得从源点u到图G的其余各个顶点的最短路径及长度，也可通过前驱数组p[]逆向找到最短路径上经过的城市，如图2-29所示。
图2-29 前驱数组p[]
例如，p[5]=3，即5的前驱是3；p[3]=2，即3的前驱是2；p[2]=1，即2的前驱是1；p[1]= −1，1没有前驱，那么从源点1到5的最短路径为1—2—3—5。
（1）数据结构
n：城市顶点个数。m：城市间路线的条数。map[][]：地图对应的带权邻接矩阵。dist[]：记录源点u到某顶点的最短路径长度。p[]：记录源点到某顶点的最短路径上的该顶点的前一个顶点（前驱）。flag[]：flag[i]等于true，说明顶点i已经加入到集合S，否则顶点i属于集合V−S。
const int N = 100; //初始化城市的个数，可修改
const int INF = 1e7; //无穷大
int map[N][N],dist[N],p[N],n,m;
bool flag[N];（2）初始化源点u到其他各个顶点的最短路径长度，初始化源点u出边邻接点（t的出边相关联的顶点）的前驱为u：
bool flag[n];//如果flag[i]等于true，说明顶点i已经加入到集合S;否则i属于集合V-S
for(int i = 1; i <= n; i ++)
{
dist[i] = map[u][i]; //初始化源点u到其他各个顶点的最短路径长度
flag[i]=false;
if(dist[i]==INF)
p[i]=-1; //说明源点u到顶点i无边相连，设置p[i]=-1
else
p[i]=u; //说明源点u到顶点i有边相连，设置p[i]=u
}（3）初始化集合S，令集合S={u}，从源点到u的最短路径为0。
flag[u]=true; //初始化集合S中，只有一个元素：源点 u
dist[u] = 0; //初始化源点 u的最短路径为0，自己到自己的最短路径（4）找最小
在集合V−S中寻找距离源点u最近的顶点t，若找不到t，则跳出循环；否则，将t加入集合S。
int temp = INF,t = u ;
for(int j = 1 ; j <= n ; j ++) //在集合V-S中寻找距离源点u最近的顶点t
if( !flag[j] && dist[j] < temp)
{
t=j; //记录距离源点u最近的顶点
temp=dist[j];
}
if(t == u) return ; //找不到t，跳出循环
flag[t] = true; //否则，将t加入集合S（5）借东风
考查集合V−S中源点u到t的邻接点j的距离，如果源点u经过t到达j的路径更短，则更新dist[j] =dist[t]+map[t][j]，即松弛操作，并记录j的前驱为t：
for(int j = 1; j <= n; j ++) //更新集合V-S中与t邻接的顶点到源点u的距离
if(!flag[j] && map[t][j]<INF) //!flag[j]表示j在V-S中，map[t][j]<INF表示t与j邻接
if(dist[j]>(dist[t]+map[t][j])) //经过t到达j的路径更短
{
dist[j]=dist[t]+map[t][j] ;
p[j]=t; //记录j的前驱为t
}重复（4）～（5），直到源点u到所有顶点的最短路径被找到。
//program 2-4
#include <cstdio>
#include <iostream>
#include<cstring>
#include<windows.h>
#include<stack>
using namespace std;
const int N = 100; // 城市的个数可修改
const int INF = 1e7; // 初始化无穷大为10000000
int map[N][N],dist[N],p[N],n,m;//n城市的个数，m为城市间路线的条数
bool flag[N]; //如果flag[i]等于true，说明顶点i已经加入到集合S;否则顶点i属于集合V-S
void Dijkstra(int u)
{
for(int i=1; i<=n; i++)//①
{
dist[i] =map[u][i]; //初始化源点u到其他各个顶点的最短路径长度
flag[i]=false;
if(dist[i]==INF)
p[i]=-1; //源点u到该顶点的路径长度为无穷大，说明顶点i与源点u不相邻
else
p[i]=u; //说明顶点i与源点u相邻，设置顶点i的前驱p[i]=u
}
dist[u] = 0;
flag[u]=true; //初始时，集合S中只有一个元素：源点u
for(int i=1; i<=n; i++)//②
{
int temp = INF,t = u;
for(int j=1; j<=n; j++) //③在集合V-S中寻找距离源点u最近的顶点t
if(!flag[j]&&dist[j]<temp)
{
t=j;
temp=dist[j];
}
if(t==u) return ; //找不到t，跳出循环
flag[t]= true; //否则，将t加入集合
for(int j=1;j<=n;j++)//④//更新集合V-S中与t邻接的顶点到源点u的距离
if(!flag[j]&& map[t][j]<INF)//!s[j]表示j在V-S中
if(dist[j]>(dist[t]+map[t][j]))
{
dist[j]=dist[t]+map[t][j] ;
p[j]=t ;
}
}
}
int main()
{
int u,v,w,st;
system("color 0d");
cout << "请输入城市的个数："<<endl;
cin >> n;
cout << "请输入城市之间的路线的个数："<<endl;
cin >>m;
cout << "请输入城市之间的路线以及距离："<<endl;
for(int i=1;i<=n;i++)//初始化图的邻接矩阵
for(int j=1;j<=n;j++)
{
map[i][j]=INF;//初始化邻接矩阵为无穷大
}
while(m--)
{
cin >> u >> v >> w;
map[u][v] =min(map[u][v],w); //邻接矩阵储存，保留最小的距离
}
cout <<"请输入小明所在的位置："<<endl; ;
cin >> st;
Dijkstra(st);
cout <<"小明所在的位置："<<st<<endl;
for(int i=1;i<=n;i++){
cout <<"小明："<<st<<" - "<<"要去的位置："<<i<<endl;
if(dist[i] == INF)
cout << "sorry,无路可达"<<endl;
else
cout << "最短距离为:"<<dist[i]<<endl;
}
return 0;
}算法实现和测试
（1）运行环境
Code::Blocks
（2）输入
请输入城市的个数：
5
请输入城市之间的路线的个数：
11
请输入城市之间的路线以及距离：
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
请输入小明所在的位置：
5（3）输出
小明所在的位置：5
小明:5 - 要去的位置:1 最短距离为：8
小明:5 - 要去的位置:2 最短距离为：24
小明:5 - 要去的位置:3 最短距离为：23
小明:5 - 要去的位置:4 最短距离为：30
小明:5 - 要去的位置:5 最短距离为：0想一想：因为我们在程序中使用p[]数组记录了最短路径上每一个结点的前驱，因此除了显示最短距离外，还可以显示最短路径上经过了哪些城市，可以增加一段程序逆向找到该最短路径上的城市序列。
void findpath(int u)
{
int x;
stack<int>s;//利用C++自带的函数创建一个栈s，需要程序头部引入#include<stack>
cout<<"源点为："<<u<<endl;
for(int i=1;i<=n;i++)
{
x=p[i];
while(x!=-1)
{
s.push(x);//将前驱依次压入栈中
x=p[x];
}
cout<<"源点到其他各顶点最短路径为：";
while(!s.empty())
{
cout<<s.top()<<"--";//依次取栈顶元素
s.pop();//出栈
}
cout<<i<<";最短距离为："<<dist[i]<<endl;
}
}只需要在主函数末尾调用该函数：
findpath(st);//主函数中st为源点输出结果如下。
源点为：5
源点到其他各顶点最短路径为：5--1；最短距离为：8
源点到其他各顶点最短路径为：5--1--2；最短距离为：24
源点到其他各顶点最短路径为：5--1--3；最短距离为：23
源点到其他各顶点最短路径为：5--1--3--4；最短距离为：30
源点到其他各顶点最短路径为：5；最短距离为：0（1）时间复杂度：在Dijkstra算法描述中，一共有4个for语句，第①个for语句的执行次数为n，第②个for语句里面嵌套了两个for语句③、④，它们的执行次数均为n，对算法的运行时间贡献最大，当外层循环标号为1时，③、④语句在内层循环的控制下均执行n次，外层循环②从1～n。因此，该语句的执行次数为n*n= n²，算法的时间复杂度为O(n²)。
（2）空间复杂度：由以上算法可以得出，实现该算法所需要的辅助空间包含为数组flag、变量i、j、t和temp所分配的空间，因此，空间复杂度为O(n)。
在for语句③中，即在集合V−S中寻找距离源点u最近的顶点t，其时间复杂度为O(n)，如果我们使用优先队列，则可以把时间复杂度降为O(log n)。那么如何使用优先队列呢？
（1）优先队列（见附录C）
（2）数据结构
在上面的例子中，我们使用了一维数组dist[t]来记录源点u到顶点t的最短路径长度。在此为了操作方便，我们使用结构体的形式来实现，定义一个结构体Node，里面包含两个成员：u为顶点，step为源点到顶点u的最短路径。
struct Node{
int v,step; // v为顶点，step为源点到顶点v的最短路径
Node(){};
Node(int a,int sp){
v = a; //参数传递，v为顶点
step = sp; //参数传递，step为源点到顶点v的最短路径
}
bool operator < (const Node& a)const{
return step > a.step; //重载 <，step(源点到顶点v的最短路径)最小值优先
}
};上面的结构体中除了两个成员变量外，还有一个构造函数和运算符优先级重载，下面详细介绍其含义用途。
为什么要使用构造函数？
如果不使用构造函数也是可以的，只定义一般的结构体，里面包含两个参数：
struct Node{
int v,step; // v为顶点，step为源点到顶点v的最短路径
};那么在变量参数赋值时，需要这样赋值：
Node vs ; //先定义一个Node结点类型变量
vs.v =3 ,vs.step = 5; //分别对该变量的两个成员进行赋值采用构造函数的形式定义结构体：
struct Node{
int u,step;
Node(){};
Node(int a,int sp){
u = a; //参数传递u为顶点
step = sp; //参数传递step为源点到顶点u的最短路径
}
};则变量参数赋值就可以直接通过参数传递：
Node vs(3,5)上面语句等价于：
vs.v =3 ,vs.step = 5;很明显通过构造函数的形式定义结构体，参数赋值更方便快捷，后面程序中会将结点压入优先队列：
priority_queue <Node> Q; // 创建优先队列，最小值优先
Q.push(Node(i,dist[i])); //将结点Node压入优先队列Q
//参数i传递给顶点v， dist[i]传递给step（3）使用优先队列优化的Dijkstra算法源代码：
//program 2-5
#include <queue>
#include <iostream>
#include<cstring>
#include<windows.h>
using namespace std;
const int N = 100; // 城市的个数可修改
const int INF = 1e7; // 无穷大
int map[N][N],dist[N],n,m;
int flag[N];
struct Node{
int u,step;
Node(){};
Node(int a,int sp){
u=a;step=sp;
}
bool operator < (const Node& a)const{ // 重载 <
return step>a.step;
}
};
void Dijkstra(int st){
priority_queue <Node> Q; // 优先队列优化
Q.push(Node(st,0));
memset(flag,0,sizeof(flag));//初始化flag数组为0
for(int i=1;i<=n;++i)
dist[i]=INF; // 初始化所有距离为，无穷大
dist[st]=0;
while(!Q.empty())
{
Node it=Q.top();//优先队列队头元素为最小值
Q.pop();
int t=it.u;
if(flag[t])//说明已经找到了最短距离，该结点是队列里面的重复元素
continue;
flag[t]=1;
for(int i=1;i<=n;i++)
{
if(!flag[i]&&map[t][i]<INF){ // 判断与当前点有关系的点，并且自己不能到自己
if(dist[i]>dist[t]+map[t][i])
{ // 求距离当前点的每个点的最短距离,进行松弛操作
dist[i]=dist[t]+map[t][i];
Q.push(Node(i,dist[i]));// 把更新后的最短距离压入优先队列，注意：里面的元素有重复
}
}
}
}
}
int main()
{
int u,v,w,st;
system("color 0d");//设置背景及字体颜色
cout << "请输入城市的个数："<<endl;
cin >> n;
cout << "请输入城市之间的路线的个数："<<endl;
cin >>m;
for(int i=1;i<=n;i++)//初始化图的邻接矩阵
for(int j=1;j<=n;j++)
{
map[i][j]=INF;//初始化邻接矩阵为无穷大
}
cout << "请输入城市之间u,v的路线以及距离w："<<endl;
while(m--)
{
cin>>u>>v>>w;
map[u][v]=min(map[u][v],w); //邻接矩阵储存，保留最小的距离
}
cout<<"请输入小明所在的位置："<<endl; ;
cin>>st;
Dijkstra(st);
cout <<"小明所在的位置："<<st<<endl;
for(int i=1;i<=n;i++)
{
cout <<"小明:"<<st<<"--->"<<"要去的位置："<<i;
if(dist[i]==INF)
cout << "sorry,无路可达"<<endl;
else
cout << " 最短距离为："<<dist[i]<<endl;
}
return 0;
}算法实现和测试
（1）运行环境
Code::Blocks
（2）输入
请输入城市的个数：
5
请输入城市之间的路线的个数：
7
请输入城市之间的路线以及距离：
1 2 2
1 3 3
2 3 5
2 4 6
3 4 7
3 5 1
4 5 4
请输入小明所在的位置：
1（3）输出
小明所在的位置：1
小明：1 - 要去的位置：1 最短距离为：0
小明：1 - 要去的位置：2 最短距离为：2
小明：1 - 要去的位置：3 最短距离为：3
小明：1 - 要去的位置：4 最短距离为：8
小明：1 - 要去的位置：5 最短距离为：4在使用优先队列的 Dijkstra 算法描述中，while (!Q.empty())语句执行的次数为n，因为要弹出n个最小值队列才会空；Q.pop()语句的时间复杂度为logn，while语句中的for语句执行n次，for语句中的Q.push (Node(i,dist[i]))时间复杂度为logn。因此，总的语句的执行次数为n* logn+n²*logn，算法的时间复杂度为O(n²logn)。
貌似时间复杂度又变大了？
这是因为我们采用的邻接矩阵存储的，如果采用邻接表存储（见附录D），那么for语句④松弛操作就不用每次执行n次，而是执行t结点的邻接边数x，每个结点的邻接边加起来为边数E，那么总的时间复杂度为O(n*logn+E*logn)，如果En，则时间复杂度为O(E*logn)。
注意：优先队列中尽管有重复的结点，但重复结点最坏是n2，log n2=2 log n，并不改变时间复杂度的数量级。
想一想，还能不能把时间复杂度再降低呢？如果我们使用斐波那契堆，那么松弛操作的时间复杂度O(1)，总的时间复杂度为O(n* logn+E)。
看过谍战电影《风声》的观众都会对影片中神奇的消息传递惊叹不已！吴志国大队长在受了残忍的“针刑”之后躺在手术台上唱空城计，变了音调，把消息传给了护士，顾晓梦在衣服上缝补了长短不一的针脚……那么，片中无处不在的摩尔斯码到底是什么？它又有着怎样的神秘力量呢？
摩尔斯电码（Morse code）由点dot（. ）、划dash（-）两种符号组成。它的基本原理是：把英文字母表中的字母、标点符号和空格按照出现的频率排序，然后用点和划的组合来代表这些字母、标点符号和空格，使频率最高的符号具有最短的点划组合。
图2-30 神秘电报密码
我们先看一个生活中的例子：
有一群退休的老教授聚会，其中一个老教授带着刚会说话的漂亮小孙女，于是大家逗她：“你能猜猜我们多大了吗？猜对了有糖吃哦！”小女孩就开始猜：“你是1岁了吗？”，老教授摇摇头。“你是两岁了吗？”，老教授仍然摇摇头。“那一定是3岁了！”……大家哈哈大笑。或许我们都感觉到了小女孩的天真可爱，然而生活中的确有很多类似这样的判断。
曾经有这样一个C++设计题目：将一个班级的成绩从百分制转为等级制。一同学设计的程序为：
if(score <60) cout << "不及格"<<endl;
else if (score <70) cout << "及格"<<endl;
else if (score <80) cout << "中等"<<endl;
else if (score <90) cout << "良好"<<endl;
else cout << "优秀"<<endl;在上面程序中，如果分数小于60，我们做1次判定即可；如果分数为60～70，需要判定2次；如果分数为70～80，需要判定3次；如果分数为80～90，需要判定4次；如果分数为90～100，需要判定5次。
这段程序貌似是没有任何问题，但是我们却犯了从1岁开始判断一个老教授年龄的错误，因为我们的考试成绩往往是呈正态分布的，如图2-31所示。
图2-31 运行结果
也就是说，大多数（70%）人的成绩要判断3次或3次以上才能成功，假设班级人数为100人，则判定次数为：
100×10%×1+100×20%×2+100×40%×3+100×20%×4+100×10%×5=300（次）
如果我们改写程序为：
if(score <80)
if (score <70)
if (score <60) cout << "不及格"<<endl;
else cout << "及格"<<endl;
else cout << "中等"<<endl;
else if (score <90) cout << "良好"<<endl;
else cout << "优秀"<<endl;则判定次数为：
100×10%×3+100×20%×3+100×40%×2+100×20%×2+100×10%×2=230（次）
为什么会有这样大的差别呢？我们来看两种判断方式的树形图，如图2-32所示。
图2-32 两种判断方式的树形图
从图2-32中我们可以看到，当频率高的分数越靠近树根（先判断）时，我们只用1次猜中的可能性越大。
再看五笔字型的编码方式：
我们在学习五笔时，需要背一级简码。所谓一级简码，就是指25个汉字，对应着25个按键，打1个字母键再加1个空格键就可打出来相应的字。为什么要这样设置呢？因为根据文字统计，这25个汉字是使用频率最高的。
五笔字根之一级简码：
G 一 F 地 D 在 S 要 A 工
H 上 J 是 K 中 L 国 M 同
T 和 R 的 E 有 W 人 Q 我
Y 主 U 产 I 不 O 为 P 这
N 民 B 了 V 发 C 以 X 经
通常的编码方法有固定长度编码和不等长度编码两种。这是一个设计最优编码方案的问题，目的是使总码长度最短。这个问题利用字符的使用频率来编码，是不等长编码方法，使得经常使用的字符编码较短，不常使用的字符编码较长。如果采用等长的编码方案，假设所有字符的编码都等长，则表示n个不同的字符需要
位。例如，3个不同的字符a、b、c，至少需要2位二进制数表示，a为00，b为01，c为10。如果每个字符的使用频率相等，固定长度编码是空间效率最高的方法。
不等长编码方法需要解决两个关键问题：
（1）编码尽可能短
我们可以让使用频率高的字符编码较短，使用频率低的编码较长，这种方法可以提高压缩率，节省空间，也能提高运算和通信速度。即频率越高，编码越短。
（2）不能有二义性
例如，ABCD四个字符如果编码如下。
A：0。B：1。C：01。D：10。
那么现在有一列数0110，该怎样翻译呢？是翻译为ABBA，ABD，CBA，还是CD？那么如何消除二义性呢？解决的办法是：任何一个字符的编码不能是另一个字符编码的前缀，即前缀码特性。
1952年，数学家D.A.Huffman提出了根据字符在文件中出现的频率，用0、1的数字串表示各字符的最佳编码方式，称为哈夫曼（Huffman）编码。哈夫曼编码很好地解决了上述两个关键问题，被广泛应用于数据压缩，尤其是远距离通信和大容量数据存储方面，常用的JPEG图片就是采用哈夫曼编码压缩的。
哈夫曼编码的基本思想是以字符的使用频率作为权构建一棵哈夫曼树，然后利用哈夫曼树对字符进行编码。构造一棵哈夫曼树，是将所要编码的字符作为叶子结点，该字符在文件中的使用频率作为叶子结点的权值，以自底向上的方式，通过n−1次的“合并”运算后构造出的一棵树，核心思想是权值越大的叶子离根越近。
哈夫曼算法采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树，构造一棵新树，新树根节点的权值为其左右孩子结点权值之和，将新树插入到树的集合中，求解步骤如下。
（1）确定合适的数据结构。编写程序前需要考虑的情况有：
（2）初始化。构造n棵结点为n个字符的单结点树集合T={t1，t2，t3，…，tn}，每棵树只有一个带权的根结点，权值为该字符的使用频率。
（3）如果T中只剩下一棵树，则哈夫曼树构造成功，跳到步骤（6）。否则，从集合T中取出没有双亲且权值最小的两棵树ti和tj，将它们合并成一棵新树zk，新树的左孩子为ti，右孩子为tj，zk的权值为ti和tj的权值之和。
（4）从集合T中删去ti，tj，加入zk。
（5）重复以上（3）～（4）步。
（6）约定左分支上的编码为“0”，右分支上的编码为“1”。从叶子结点到根结点逆向求出每个字符的哈夫曼编码，从根结点到叶子结点路径上的字符组成的字符串为该叶子结点的哈夫曼编码。算法结束。
假设我们现在有一些字符和它们的使用频率（见表2-13），如何得到它们的哈夫曼编码呢？
表2-13 字符频率
| 字符 | a | b | c | d | e | f |
|---|---|---|---|---|---|---|
| 频率 | 0.05 | 0.32 | 0.18 | 0.07 | 0.25 | 0.13 |
我们可以把每一个字符作为叶子，它们对应的频率作为其权值，为了比较大小方便，可以对其同时扩大100倍，得到a～f分别对应5、32、18、7、25、13。
（1）初始化。构造n棵结点为n个字符的单结点树集合T={a，b，c，d，e，f}，如图2-33所示。
图2-33 叶子结点
（2）从集合T中取出没有双亲的且权值最小的两棵树a和d，将它们合并成一棵新树t1，新树的左孩子为a，右孩子为d，新树的权值为a和d的权值之和为12。新树的树根t1加入集合T，a和d从集合T中删除，如图2-34所示。
图2-34 构建新树
（3）从集合T中取出没有双亲的且权值最小的两棵树t1和f，将它们合并成一棵新树t2，新树的左孩子为t1，右孩子为f，新树的权值为t1和f的权值之和为25。新树的树根t2加入集合T，将t1和f从集合T中删除，如图2-35所示。
图2-35 构建新树
（4）从集合T中取出没有双亲且权值最小的两棵树c和e，将它们合并成一棵新树t3，新树的左孩子为c，右孩子为e，新树的权值为c和e的权值之和为43。新树的树根t3加入集合T，将c和e从集合T中删除，如图2-36所示。
图2-36 构建新树
（5）从集合T中取出没有双亲且权值最小的两棵树t2和b，将它们合并成一棵新树t4，新树的左孩子为t2，右孩子为b，新树的权值为t2和b的权值之和为57。新树的树根t4加入集合T，将t2和b从集合T中删除，如图2-37所示。
图2-37 构建新树
（6）从集合T中取出没有双亲且权值最小的两棵树t3和t4，将它们合并成一棵新树t5，新树的左孩子为t4，右孩子为t3，新树的权值为t3和t4的权值之和为 100。新树的树根t5加入集合T，将t3和t4从集合T中删除，如图 2-38所示。
图2-38 哈夫曼树
（7）T中只剩下一棵树，哈夫曼树构造成功。
（8）约定左分支上的编码为“0”，右分支上的编码为“1”。从叶子结点到根结点逆向求出每个字符的哈夫曼编码，从根结点到叶子结点路径上的字符组成的字符串为该叶子结点的哈夫曼编码，如图2-39所示。
图2-39 哈夫曼编码
在构造哈夫曼树的过程中，首先给每个结点的双亲、左孩子、右孩子初始化为−1，找出所有结点中双亲为−1、权值最小的两个结点t1、t2，并合并为一棵二叉树，更新信息（双亲结点的权值为t1、t2权值之和，其左孩子为权值最小的结点t1，右孩子为次小的结点t2，t1、t2的双亲为双亲结点的编号）。重复此过程，构造一棵哈夫曼树。
（1）数据结构
每个结点的结构包括权值、双亲、左孩子、右孩子、结点字符信息这 5 个域。如图 2-40所示，定义为结构体形式，定义结点结构体HnodeType：
typedef struct
{
double weight; //权值
int parent; //双亲
int lchild; //左孩子
int rchild; //右孩子
char value; //该节点表示的字符
} HNodeType;图2-40 结点结构体
在编码结构体中，bit[]存放结点的编码，start 记录编码开始下标，逆向译码（从叶子到根，想一想为什么不从根到叶子呢？）。存储时，start从n−1开始依次递减，从后向前存储；读取时，从start+1开始到n−1，从前向后输出，即为该字符的编码。如图2-41所示。
图2-41 编码数组
编码结构体HcodeType：
typedef struct
{
int bit[MAXBIT]; //存储编码的数组
int start; //编码开始下标
} HCodeType; /* 编码结构体 */（2）初始化
初始化存放哈夫曼树数组HuffNode[]中的结点（见表2-14）：
for (i=0; i<2*n-1; i++){
HuffNode[i].weight = 0;//权值
HuffNode[i].parent =-1; //双亲
HuffNode[i].lchild =-1; //左孩子
HuffNode[i].rchild =-1; //右孩子
}表2-14 哈夫曼树构建数组
输入n个叶子结点的字符及权值：
for (i=0; i<n; i++){
cout<<"Please input value and weight of leaf node "<<i + 1<<endl;
cin>>HuffNode[i].value>>HuffNode[i].weight;
}（3）循环构造Huffman树
从集合T中取出双亲为−1且权值最小的两棵树ti和tj，将它们合并成一棵新树zk，新树的左儿子为ti，右孩子为tj，zk的权值为ti和tj的权值之和。
int i, j, x1, x2; //x1、x2为两个最小权值结点的序号。
double m1,m2; //m1、m2为两个最小权值结点的权值。
for (i=0; i<n-1; i++){
m1=m2=MAXVALUE; //初始化为最大值
x1=x2=-1; //初始化为-1
//找出所有结点中权值最小、无双亲结点的两个结点
for (j=0; j<n+i; j++){
if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1){
m2 = m1;
x2 = x1;
m1 = HuffNode[j].weight;
x1 = j;
}
else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1){
m2=HuffNode[j].weight;
x2=j;
}
}
/* 更新新树信息 */
HuffNode[x1].parent = n+i; //x1的父亲为新结点编号n+i
HuffNode[x2].parent = n+i; //x2的父亲为新结点编号n+i
HuffNode[n+i].weight =m1+m2; //新结点权值为两个最小权值之和m1+m2
HuffNode[n+i].lchild = x1; //新结点n+i的左孩子为x1
HuffNode[n+i].rchild = x2; //新结点n+i的右孩子为x2
}
}图解：
（1）i=0时，j=0；j<6；找双亲为−1，权值最小的两个数：
x1=0 x2=3；//x1、x2为两个最小权值结点的序号
m1=5 m2=7；//m1、m2为两个最小权值结点的权值
HuffNode[0].parent = 6; //x1的父亲为新结点编号n+i
HuffNode[3].parent = 6; //x2的父亲为新结点编号n+i
HuffNode[6].weight =12; //新结点权值为两个最小权值之和m1+m2
HuffNode[6].lchild = 0; //新结点n+i的左孩子为x1
HuffNode[6].rchild = 3; //新结点n+i的右孩子为x2数据更新后如表2-15所示。
表2-15 哈夫曼树构建数组
对应的哈夫曼树如图2-42所示。
图2-42 哈夫曼树生成过程
（2）i=1时，j=0；j<7；找双亲为−1，权值最小的两个数：
x1=6 x2=5；//x1、x2为两个最小权值结点的序号
m1=12 m2=13；//m1、m2为两个最小权值结点的权值
HuffNode[5].parent = 7; //x1的父亲为新结点编号n+i
HuffNode[6].parent = 7; //x2的父亲为新结点编号n+i
HuffNode[7].weight =25; //新结点权值为两个最小权值之和m1+m2
HuffNode[7].lchild = 6; //新结点n+i的左孩子为x1
HuffNode[7].rchild = 5; //新结点n+i的右孩子为x2数据更新后如表2-16所示。
表2-16 哈夫曼树构建数组
对应的哈夫曼树如图2-43所示。
图2-43 哈夫曼树生成过程
（3）i=2时，j=0；j<8；找双亲为−1，权值最小的两个数：
x1=2 x2=4；//x1、x2为两个最小权值结点的序号
m1=18 m2=25；//m1、m2为两个最小权值结点的权值
HuffNode[2].parent = 8; //x1的父亲为新结点编号n+i
HuffNode[4].parent = 8; //x2的父亲为新结点编号n+i
HuffNode[8].weight =43; //新结点权值为两个最小权值之和m1+m2
HuffNode[8].lchild = 2; //新结点n+i的左孩子为x1
HuffNode[8].rchild = 4; //新结点n+i的右孩子为x2数据更新后如表2-17所示。
表2-17 哈夫曼树构建数组
对应的哈夫曼树如图2-44所示。
图2-44 哈夫曼树生成过程
（4）i=3时，j=0；j<9；找双亲为−1，权值最小的两个数：
x1=7 x2=1；//x1、x2为两个最小权值结点的序号
m1=25 m2=32；//m1、m2为两个最小权值结点的权值
HuffNode[7].parent = 9; //x1的父亲为新结点编号n+i
HuffNode[1].parent = 9; //x2的父亲为新结点编号n+i
HuffNode[8].weight =57; //新结点权值为两个最小权值之和m1+m2
HuffNode[8].lchild = 7; //新结点n+i的左孩子为x1
HuffNode[8].rchild = 1; //新结点n+i的右孩子为x2数据更新后如表2-18所示。
表2-18 哈夫曼树构建数组
对应的哈夫曼树如图2-45所示。
图2-45 哈夫曼树生成过程
（5）i=4时，j=0；j<10；找双亲为−1，权值最小的两个数：
x1=8 x2=9；//x1、x2为两个最小权值结点的序号
m1=43 m2=57；//m1、m2为两个最小权值结点的权值
HuffNode[8].parent = 10; //x1的父亲为生成的新结点编号n+i
HuffNode[9].parent =10; //x2的父亲为生成的新结点编号n+i
HuffNode[10].weight =100; //新结点权值为两个最小权值之和m1+ m2
HuffNode[10].lchild = 8; //新结点编号n+i的左孩子为x1
HuffNode[10].rchild = 9; //新结点编号n+i的右孩子为x2数据更新后如表2-19所示。
表2-19 哈夫曼树构建数组
对应的哈夫曼树如图2-46所示。
图2-46 哈夫曼树生成过程
（6）输出哈夫曼编码
void HuffmanCode(HCodeType HuffCode[MAXLEAF], int n)
{
HCodeType cd; /* 定义一个临时变量来存放求解编码时的信息 */
int i,j,c,p;
for(i = 0;i < n; i++){
cd.start = n-1;
c = i; //i为叶子结点编号
p = HuffNode[c].parent;
while(p != -1){
if(HuffNode[p].lchild == c){
cd.bit[cd.start] = 0;
}
else
cd.bit[cd.start] = 1;
cd.start--; /* start向前移动一位 */
c = p; /* c,p变量上移，准备下一循环 */
p = HuffNode[c].parent;
}
/* 把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组 */
for (j=cd.start+1; j<n; j++)
HuffCode[i].bit[j] = cd.bit[j];
HuffCode[i].start = cd.start;
}
}图解：哈夫曼编码数组如图2-47所示。
图2-47 哈夫曼编码数组
（1）i=0时，c=0；
cd.start = n-1=5;
p = HuffNode[0].parent=6;//从哈夫曼树建成后的表HuffNode[]中读出
//p指向0号结点的父亲6号构建完成的哈夫曼树数组如表2-20所示。
表2-20 哈夫曼树构建数组
如果p != −1，那么从表HuffNode[]中读出6号结点的左孩子和右孩子，判断0号结点是它的左孩子还是右孩子，如果是左孩子编码为0；如果是右孩子编码为1。
从表2-20可以看出：
HuffNode[6].lchild=0;//0号结点是其父亲6号的左孩子
cd.bit[5] = 0;//编码为0
cd.start--=4; /* start向前移动一位*/哈夫曼编码树如图2-48所示，哈夫曼编码数组如图2-49所示。
图2-48 哈夫曼编码树
图2-49 哈夫曼编码数组
c = p=6; /* c、p变量上移，准备下一循环 */
p = HuffNode[6].parent=7;c、p变量上移后如图2-50所示。
p != -1;
HuffNode[7].lchild=6;//6号结点是其父亲7号的左孩子
cd.bit[4] = 0;//编码为0
cd.start--=3; /* start向前移动一位*/
c = p=7; /* c、p变量上移，准备下一循环 */
p = HuffNode[7].parent=9;图2-50 哈夫曼编码树
哈夫曼编码树如图2-51所示，哈夫曼编码数组如图2-52所示。
图2-51 哈夫曼编码树
图2-52 哈夫曼编码数组
p != -1;
HuffNode[9].lchild=7;//7号结点是其父亲9号的左孩子
cd.bit[3] = 0;//编码为0
cd.start--=2; /* start向前移动一位*/
c = p=9; /* c、p变量上移，准备下一循环 */
p = HuffNode[9].parent=10;哈夫曼编码树如图2-53所示，哈夫曼编码数组如图2-54所示。
p != -1;
HuffNode[10].lchild!=9;//9号结点不是其父亲10号的左孩子
cd.bit[2] = 1;//编码为1
cd.start--=1; /* start向前移动一位*/
c = p=10; /* c、p变量上移，准备下一循环 */
p = HuffNode[10].parent=-1;图2-53 哈夫曼编码树
图2-54 哈夫曼编码数组
哈夫曼编码树如图2-55所示，哈夫曼编码数组如图2-56所示。
p = -1;该叶子结点编码结束。
/* 把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组 */
for (j=cd.start+1; j<n; j++)
HuffCode[i].bit[j] = cd.bit[j];
HuffCode[i].start = cd.start;图2-55 哈夫曼编码树
图2-56 哈夫曼编码数组
HuffCode[]数组如图2-57所示。
图2-57 哈夫曼编码HuffCode[]数组
注意：图中的箭头不表示指针。
//program 2-6
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1
typedef struct
{
double weight;
int parent;
int lchild;
int rchild;
char value;
} HNodeType; /* 结点结构体 */
typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType; /* 编码结构体 */
HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF];/* 定义一个编码结构体数组*/
/* 构造哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE], int n)
{
/* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。
*/
int i, j, x1, x2;
double m1,m2;
/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
for (i=0; i<2*n-1; i++)
{
HuffNode[i].weight = 0;//权值
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].rchild =-1;
}
/* 输入 n 个叶子结点的权值 */
for (i=0; i<n; i++)
{
cout<<"Please input value and weight of leaf node "<<i + 1<<endl;
cin>>HuffNode[i].value>>HuffNode[i].weight;
}
/* 构造 Huffman 树 */
for (i=0; i<n-1; i++)
{//执行n-1次合并
m1=m2=MAXVALUE;
/* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
x1=x2=0;
/* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一棵二叉树 */
for (j=0; j<n+i; j++)
{
if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
{
m2 = m1;
x2 = x1;
m1 = HuffNode[j].weight;
x1 = j;
}
else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}
/* 设置找到的两个子结点 x1、x2 的父结点信息 */
HuffNode[x1].parent = n+i;
HuffNode[x2].parent = n+i;
HuffNode[n+i].weight = m1+m2;
HuffNode[n+i].lchild = x1;
HuffNode[n+i].rchild = x2;
cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<<HuffNode[x1]. weight<<"\t"<<HuffNode[x2].weight<<endl; /* 用于测试 */
}
}
/* 哈夫曼树编码 */
void HuffmanCode(HCodeType HuffCode[MAXLEAF], int n)
{
HCodeType cd; /* 定义一个临时变量来存放求解编码时的信息 */
int i,j,c,p;
for(i = 0;i < n; i++)
{
cd.start = n-1;
c = i;
p = HuffNode[c].parent;
while(p != -1)
{
if(HuffNode[p].lchild == c)
cd.bit[cd.start] = 0;
else
cd.bit[cd.start] = 1;
cd.start--; /* 求编码的低一位 */
c = p;
p = HuffNode[c].parent; /* 设置下一循环条件 */
}
/* 把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组 */
for (j=cd.start+1; j<n; j++)
HuffCode[i].bit[j] = cd.bit[j];
HuffCode[i].start = cd.start;
}
}
int main()
{
int i,j,n;
cout<<"Please input n："<<endl;
cin>>n;
HuffmanTree (HuffNode, n); /* 构造哈夫曼树 */
HuffmanCode(HuffCode, n); /* 哈夫曼树编码 */
/* 输出已保存好的所有存在编码的哈夫曼编码 */
for(i = 0;i < n;i++)
{
cout<<HuffNode[i].value<<": Huffman code is: ";
for(j=HuffCode[i].start+1; j < n; j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
return 0;
}算法实现和测试
（1）运行环境
Code::Blocks
（2）输入
Please input n：
6
Please input value and weight of leaf node 1
a 0.05
Please input value and weight of leaf node 2
b 0.32
Please input value and weight of leaf node 3
c 0.18
Please input value and weight of leaf node 4
d 0.07
Please input value and weight of leaf node 5
e 0.25
Please input value and weight of leaf node 6
f 0.13（3）输出
x1.weight and x2.weight in round 1 0.05 0.07
x1.weight and x2.weight in round 2 0.12 0.13
x1.weight and x2.weight in round 3 0.18 0.25
x1.weight and x2.weight in round 4 0.25 0.32
x1.weight and x2.weight in round 5 0.43 0.57
a: Huffman code is: 1000
b: Huffman code is: 11
c: Huffman code is: 00
d: Huffman code is: 1001
e: Huffman code is: 01
f: Huffman code is: 101（1）时间复杂度：由程序可以看出，在函数HuffmanTree()中，if (HuffNode[j].weight<m1&& HuffNode[j].parent==−1)为基本语句，外层i与j组成双层循环：
i=0时，该语句执行n次；
i=1时，该语句执行n+1次；
i=2时，该语句执行n+2次；
……
i=n−2时，该语句执行n+n−2次；
则基本语句共执行n+（n+1）+（n+2）+…+（n+（n−2））=（n−1）*（3n−2）/2次（等差数列）；在函数HuffmanCode()中，编码和输出编码时间复杂度都接近n2；则该算法时间复杂度为O(n2)。
（2）空间复杂度：所需存储空间为结点结构体数组与编码结构体数组，哈夫曼树数组 HuffNode[]中的结点为n个，每个结点包含bit[MAXBIT]和start两个域，则该算法空间复杂度为O( n* MAXBIT)。
该算法可以从两个方面优化：
（1）函数HuffmanTree()中找两个权值最小结点时使用优先队列，时间复杂度为logn，执行n−1次，总时间复杂度为O( n logn)。
（2）函数HuffmanCode()中，哈夫曼编码数组HuffNode[]中可以定义一个动态分配空间的线性表来存储编码，每个线性表的长度为实际的编码长度，这样可以大大节省空间。
校园网是为学校师生提供资源共享、信息交流和协同工作的计算机网络。校园网是一个宽带、具有交互功能和专业性很强的局域网络。如果一所学校包括多个学院及部门，也可以形成多个局域网络，并通过有线或无线方式连接起来。原来的网络系统只局限于以学院、图书馆为单位的局域网，不能形成集中管理以及各种资源的共享，个别学院还远离大学本部，这些情况严重地阻碍了整个学校的网络化需求。现在需要设计网络电缆布线，将各个单位的局域网络连通起来，如何设计能够使费用最少呢？
图2-58 校园网络
某学校下设10个学院，3个研究所，1个大型图书馆，4个实验室。其中，1～10号节点代表10个学院，11～13号节点代表3个研究所，14号节点代表图书馆，15～18号节点代表4个实验室。该问题用无向连通图G =（V，E）来表示通信网络，V表示顶点集，E表示边集。把各个单位抽象为图中的顶点，顶点与顶点之间的边表示单位之间的通信网络，边的权值表示布线的费用。如果两个节点之间没有连线，代表这两个单位之间不能布线，费用为无穷大。如图2-59所示。
图2-59 校园网连通图
那么我们如何设计网络电缆布线，将各个单位连通起来，并且费用最少呢？
对于n个顶点的连通图，只需n−1条边就可以使这个图连通，n−1条边要想保证图连通，就必须不含回路，所以我们只需要找出n−1条权值最小且无回路的边即可。
需要说明几个概念。
（1）子图：从原图中选中一些顶点和边组成的图，称为原图的子图。
（2）生成子图：选中一些边和所有顶点组成的图，称为原图的生成子图。
（3）生成树：如果生成子图恰好是一棵树，则称为生成树。
（4）最小生成树：权值之和最小的生成树，则称为最小生成树。
本题就是最小生成树求解问题。
找出n−1条权值最小的边很容易，那么怎么保证无回路呢?
如果在一个图中深度搜索或广度搜索有没有回路，是一件繁重的工作。有一个很好的办法——避圈法。在生成树的过程中，我们把已经在生成树中的结点看作一个集合，把剩下的结点看作另一个集合，从连接两个集合的边中选择一条权值最小的边即可。
首先任选一个结点，例如1号结点，把它放在集合U中，U={1}，那么剩下的结点即V−U={2，3，4，5，6，7}，V是图的所有顶点集合。如图2-60所示。
图2-60 最小生成树求解过程
现在只需在连接两个集合（V和V−U）的边中看哪一条边权值最小，把权值最小的边关联的结点加入到集合U。从图2-68可以看出，连接两个集合的3条边中，结点1到结点2的边权值最小，选中此条边，把2号结点加入U集合U={1，2}，V−U={3，4，5，6，7}。
再从连接两个集合（V和V−U）的边中选择一条权值最小的边。从图2-61可以看出，连接两个集合的4条边中，结点2到结点7的边权值最小，选中此条边，把7号结点加入U集合U={1，2，7}，V−U={3，4，5，6}。
图2-61 最小生成树求解过程
如此下去，直到U=V结束，选中的边和所有的结点组成的图就是最小生成树。
是不是非常简单啊？
这就是Prim算法，1957年由美国计算机科学家Robert C.Prim发现的。那么如何用算法来实现呢？
首先，令U={u0}，u0∈V，TE={}。u0可以是任何一个结点，因为最小生成树包含所有结点，所以从哪个结点出发都可以得到最小生成树，不影响最终结果。TE为选中的边集。
然后，做如下贪心选择：选取连接U和V−U的所有边中的最短边，即满足条件i∈U，j∈V−U，且边（i，j）是连接U和V−U的所有边中的最短边，即该边的权值最小。
然后，将顶点j加入集合U，边（i，j）加入TE。继续上面的贪心选择一直进行到U=V为止，此时，选取到的所有边恰好构成图G的一棵最小生成树T。
算法设计及步骤如下。
步骤1：确定合适的数据结构。设置带权邻接矩阵C存储图G，如果图G中存在边（u，x），令C[u][x]等于边（u，x）上的权值，否则，C[u][x]=∞；bool数组s[]，如果s[i]=true，说明顶点i已加入集合U。
如图2-62所示，直观地看图很容易找出 U 集合到 V−U集合的边中哪条边是最小的，但是程序中如果穷举这些边，再找最小值就太麻烦了，那怎么办呢？
图2-62 最小生成树求解过程
可以通过设置两个数组巧妙地解决这个问题，closest[j]表示V−U中的顶点j到集合U中的最邻近点，lowcost[j]表示V−U中的顶点j到集合U中的最邻近点的边值，即边（j,closest[j]）的权值。
例如，在图2-62中，7号结点到U集合中的最邻近点是2，closest[7]=2，如图2-63所示。7号结点到最邻近点2的边值为1，即边（2，7）的权值，记为lowcost[7]=1，如图2-64所示。
图2-63 closest[]数组
图2-64 lowcost[]数组
只需要在V−U集合中找lowcost[]值最小的顶点即可。
步骤2：初始化。令集合U={u0}，u0∈V，并初始化数组closest[]、lowcost[]和s[]。
步骤3：在V−U集合中找lowcost值最小的顶点t，即lowcost[t]=min{lowcost[j]|j∈V−U}，满足该公式的顶点t就是集合V−U中连接集合U的最邻近点。
步骤4：将顶点t加入集合U。
步骤5：如果集合V−U，算法结束，否则，转步骤6。
步骤6：对集合V−U中的所有顶点j，更新其lowcost[]和closest[]。更新公式：if（C[t] [j]<lowcost [j] ) { lowcost [j]= C [t] [j]; closest [j] = t; }，转步骤3。
按照上述步骤，最终可以得到一棵权值之和最小的生成树。
设G =（V，E）是无向连通带权图，如图2-65所示。
图2-65 无向连通带权图G
（1）数据结构
设置地图的带权邻接矩阵为C[][]，即如果从顶点i到顶点j有边，就让C[i][j]=<i，j>的权值，否则C[i][j]=∞（无穷大），如图2-66所示。
图2-66 邻接矩阵C[ ][ ]
（2）初始化
假设u0=1；令集合U={1}，V−U={2，3，4，5，6，7}，TE={}，s[1]=true，初始化数组closest[]：除了1号结点外其余结点均为1，表示V−U中的顶点到集合U的最临近点均为1，如图2-67所示。lowcost[]：1号结点到V−U中的顶点的边值，即读取邻接矩阵第1行，如图2-68所示。
图2-67 closest[]数组
图2-68 lowcost[]数组
初始化后如图2-69所示。
图2-69 最小生成树求解过程
（3）找最小
在集合V−U={2，3，4，5，6，7}中，依照贪心策略寻找V−U集合中lowcost最小的顶点t，如图2-70所示。
图2-70 lowcost[]数组
找到最小值为23，对应的结点t=2。
选中的边和结点如图2-71所示。
图2-71 最小生成树求解过程
（4）加入U战队
将顶点t加入集合U={1，2}，同时更新V−U={3，4，5，6，7}。
（5）更新
刚刚找到了到U集合的最邻近点t = 2，那么对t在集合V−U中每一个邻接点j，都可以借助t更新。我们从图或邻接矩阵可以看出，2号结点的邻接点是3和7号结点：
C[2][3]=20<lowcost[3]=∞，更新最邻近距离lowcost[3]=20，最邻近点closest[3]=2；
C[2][7]=1<lowcost[7]=36，更新最邻近距离lowcost[7]=1，最邻近点closest[7]=2；
更新后的closest[j]和lowcost[j]数组如图2-72和图2-73所示。
图2-72 closest[]数组
图2-73 lowcost[]数组
更新后如图2-74所示。
图2-74 最小生成树求解过程
closest[j]和lowcost[j]分别表示V−U集合中顶点j到U集合的最邻近顶点和最邻近距离。3号顶点到U集合的最邻近点为2，最邻近距离为20；4、5号顶点到U集合的最邻近点仍为初始化状态1，最邻近距离为∞；6号顶点到U集合的最邻近点为1，最邻近距离为26；7号顶点到U集合的最邻近点为2，最邻近距离为1。
（6）找最小
在集合V−U={3，4，5，6，7}中，依照贪心策略寻找V−U集合中lowcost最小的顶点t，如图2-75所示。
图2-75 lowcost[]数组
找到最小值为1，对应的结点t=7。
选中的边和结点如图2-76所示。
图2-76 最小生成树求解过程
（7）加入U战队
将顶点t加入集合U={1，2，7}，同时更新V−U={3，4，5，6}。
（8）更新
刚刚找到了到U集合的最邻近点t =7，那么对t在集合V−U中每一个邻接点j，都可以借t更新。我们从图或邻接矩阵可以看出，7号结点在集合V−U中的邻接点是3、4、5、6结点：
C[7][3]=4<lowcost[3]=20，更新最邻近距离lowcost[3]=4，最邻近点closest[3]=7；
C[7][4]=9<lowcost[4]=∞，更新最邻近距离lowcost[4]=9，最邻近点closest[4]=7；
C[7][5]=16<lowcost[5]=∞，更新最邻近距离lowcost[5]=16，最邻近点closest[5]=7；
C[7][6]=25<lowcost[6]=28，更新最邻近距离lowcost[6]=25，最邻近点closest[6]=7；
更新后的closest[j]和lowcost[j]数组如图2-77和图2-78所示。
图2-77 closest[]数组
图2-78 lowcost[]数组
更新后如图2-79所示。
图2-79 最小生成树求解过程
closest[j]和lowcost[j]分别表示V−U集合中顶点j到U集合的最邻近顶点和最邻近距离。3号顶点到U集合的最邻近点为7，最邻近距离为4；4号顶点到U集合的最邻近点为7，最邻近距离为9；5号顶点到U集合的最邻近点为7，最邻近距离为16；6号顶点到U集合的最邻近点为7，最邻近距离为25。
（9）找最小
在集合V−U={3，4，5，6}中，依照贪心策略寻找V−U集合中lowcost最小的顶点t，如图2-80所示。
图2-80 lowcost[]数组
找到最小值为4，对应的结点t=3。
选中的边和结点如图2-81所示。
图2-81 最小生成树求解过程
（10）加入U战队
将顶点t加入集合U ={1，2，3，7}，同时更新V−U={4，5，6}。
（11）更新
刚刚找到了到U集合的最邻近点t =3，那么对t在集合V−U中每一个邻接点j，都可以借助t更新。我们从图或邻接矩阵可以看出，3号结点在集合V−U中的邻接点是4号结点：
C[3][4]=15>lowcost[4]=9，不更新。
closest[j]和lowcost[j]数组不改变。
更新后如图2-82所示。
图2-82 最小生成树求解过程
closest[j]和lowcost[j]分别表示V−U集合中顶点j到U集合的最邻近顶点和最邻近距离。4号顶点到U集合的最邻近点为7，最邻近距离为9；5号顶点到U集合的最邻近点为7，最邻近距离为16；6号顶点到U集合的最邻近点为7，最邻近距离为25。
（12）找最小
在集合V−U={4，5，6}中，依照贪心策略寻找V−U集合中lowcost最小的顶点t，如图2-83所示。
图2-83 lowcost[]数组
找到最小值为9，对应的结点t=4。
选中的边和结点如图2-84所示。
图2-84 最小生成树求解过程
（13）加入U战队
将顶点t加入集合U ={1，2，3，4，7}，同时更新V−U={5，6}。
（14）更新
刚刚找到了到U集合的最邻近点t =4，那么对t在集合V−U中每一个邻接点j，都可以借助t更新。我们从图或邻接矩阵可以看出，4号结点在集合V−U中的邻接点是5号结点：
C[4][5]=3<lowcost[5]=16，更新最邻近距离lowcost[5]=3，最邻近点closest[5]=4；
更新后的closest[j]和lowcost[j]数组如图2-85和图2-86所示。
图2-85 closest[]数组
图2-86 lowcost[]数组
更新后如图2-87所示。
图2-87 最小生成树求解过程
closest[j]和lowcost[j]分别表示V−U集合中顶点j到U集合的最邻近顶点和最邻近距离。5号顶点到U集合的最邻近点为4，最邻近距离为3；6号顶点到U集合的最邻近点为7，最邻近距离为25。
（15）找最小
在集合V−U={5，6}中，依照贪心策略寻找V−U集合中lowcost最小的顶点t，如图2-88所示。
图2-88 lowcost[]数组
找到最小值为3，对应的结点t=5。
选中的边和结点如图2-89所示。
图2-89 最小生成树求解过程
（16）加入U战队
将顶点t加入集合U={1，2，3，4，5，7}，同时更新V−U={6}。
（17）更新
刚刚找到了到U集合的最邻近点t =5，那么对t在集合V−U中每一个邻接点j，都可以借助t更新。我们从图或邻接矩阵可以看出，5号结点在集合V−U中的邻接点是6号结点：
C[5][6]=17<lowcost[6]=25，更新最邻近距离lowcost[6]=17，最邻近点closest[6]=5；
更新后的closest[j]和lowcost[j]数组如图2-90和图2-91所示。
图2-90 closest[]数组
图2-91 lowcost[]数组
更新后如图2-92所示。
图2-92 最小生成树求解过程
closest[j]和lowcost[j]分别表示V−U集合中顶点j到U集合的最邻近顶点和最邻近距离。6号顶点到U集合的最邻近点为5，最邻近距离为17。
（18）找最小
在集合V−U={6}中，依照贪心策略寻找V−U集合中lowcost最小的顶点t，如图2-93所示。
图2-93 lowcost[]数组
找到最小值为17，对应的结点t=6。
选中的边和结点如图2-94所示。
图2-94 最小生成树求解过程
（19）加入U战队
将顶点t加入集合U ={1，2，3，4，5，6，7}，同时更新V−U={}。
（20）更新
刚刚找到了到U集合的最邻近点t =6，那么对t在集合V−U中每一个邻接点j，都可以借t更新。我们从图2-94可以看出，6号结点在集合V−U中无邻接点，因为V−U={}。
closest[j]和lowcost[j]数组如图2-95和图2-96所示。
图2-95 closest[]数组
图2-96 lowcost[]数组
得到的最小生成树如图2-97所示。
图2-97 最小生成树
最小生成树权值之和为57，即把lowcost数组中的值全部加起来。
（1）初始化。s[1]=true，初始化数组closest，除了u0外其余顶点最邻近点均为u0，表示V−U中的顶点到集合U的最临近点均为u0；初始代数组lowcost，u0到V−U中的顶点的边值，无边相连则为∞（无穷大）。
s[u0] = true; //初始时，集合中U只有一个元素，即顶点u0
for(i = 1; i <= n; i++)
{
if(i != u0) //除u0之外的顶点
{
lowcost[i] = c[u0][i]; //u0到其它顶点的边值
closest[i] = u0; //最邻近点初始化为u0
s[i] = false; //初始化u0之外的顶点不属于U集合，即属于V-U集合
}
else
lowcost[i] =0;
}（2）在集合V−U中寻找距离集合U最近的顶点t。
int temp = INF;
int t = u0;
for(j = 1; j <= n; j++) //在集合中V-U中寻找距离集合U最近的顶点t
{
if((!s[j]) && (lowcost[j] < temp)) //!s[j] 表示j结点在V-U集合中
{
t = j;
temp = lowcost[j];
}
}
if(t == u0) //找不到t，跳出循环
break;（3）更新lowcost和closest数组。
s[t] = true; //否则，讲t加入集合U
for(j = 1; j <= n; j++) //更新lowcost和closest
{
if((!s[j]) && (c[t][j] < lowcost[j])) // !s[j] 表示j结点在V-U集合中
//t到j的边值小于当前的最邻近值
{
lowcost[j] = c[t][j]; //更新j的最邻近值为t到j的边值
closest[j] = t; //更新j的最邻近点为t
}
}//program 2-7
#include <iostream>
using namespace std;
const int INF = 0x3fffffff;
const int N = 100;
bool s[N];
int closest[N];
int lowcost[N];
void Prim(int n, int u0, int c[N][N])
{ //顶点个数n、开始顶点u0、带权邻接矩阵C[n][n]
//如果s[i]=true,说明顶点i已加入最小生成树
//的顶点集合U；否则顶点i属于集合V-U
//将最后的相关的最小权值传递到数组lowcost
s[u0] = true; //初始时，集合中U只有一个元素，即顶点u0
int i;
int j;
for(i = 1; i <= n; i++)//①
{
if(i != u0)
{
lowcost[i] = c[u0][i];
closest[i] = u0;
s[i] = false;
}
else
lowcost[i] =0;
}
for(i = 1; i <= n; i++) //②
{
int temp = INF;
int t = u0;
for(j = 1; j <= n; j++) //③在集合中V-u中寻找距离集合U最近的顶点t
{
if((!s[j]) && (lowcost[j] < temp))
{
t = j;
temp = lowcost[j];
}
}
if(t == u0)
break; //找不到t，跳出循环
s[t] = true; //否则，讲t加入集合U
for(j = 1; j <= n; j++) //④更新lowcost和closest
{
if((!s[j]) && (c[t][j] < lowcost[j]))
{
lowcost[j] = c[t][j];
closest[j] = t;
}
}
}
}
int main()
{
int n, c[N][N], m, u, v, w;
int u0;
cout <<"输入结点数n和边数m："<<endl;
cin >> n >> m;
int sumcost = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
c[i][j] = INF;
cout <<"输入结点数u，v和边值w："<<endl;
for(int i=1; i<=m; i++)
{
cin >> u >> v >> w;
c[u][v] = c[v][u] = w;
}
cout <<"输入任一结点u0："<<endl;
cin >> u0 ;
//计算最后的lowcos的总和，即为最后要求的最小的费用之和
Prim(n, u0, c);
cout <<"数组lowcost的内容为："<<endl;
for(int i = 1; i <= n; i++)
cout << lowcost[i] << " ";
cout << endl;
for(int i = 1; i <= n; i++)
sumcost += lowcost[i];
cout << "最小的花费是：" << sumcost << endl << endl;
return 0;
}算法实现和测试
（1）运行环境
Code::Blocks
（2）输入
输入结点数n和边数m：
7 12
输入结点数u，v和边值w：
1 2 23
1 6 28
1 7 36
2 3 20
2 7 1
3 4 15
3 7 4
4 5 3
4 7 9
5 6 17
5 7 16
6 7 25
输入任一结点u0：
1（3）输出
数组lowcost的内容为：
0 23 4 9 3 17 1
最小的花费是：57（1）时间复杂度：在Prim（int n，int u0，int c[N][N]）算法中，一共有4个for语句，第①个for语句的执行次数为n，第②个for语句里面嵌套了两个for语句③、④，它们的执行次数均为n，对算法的运行时间贡献最大。当外层循环标号为1时，③、④语句在内层循环的控制下均执行n次，外层循环②从1～n。因此，该语句的执行次数为n*n=n²，算法的时间复杂度为O(n²)。
（2）空间复杂度：算法所需要的辅助空间包含i、j、lowcost和closest，则算法的空间复杂度是O(n)。
该算法可以从两个方面优化：
（1）for语句③找lowcost最小值时使用优先队列，每次出队一个最小值，时间复杂度为logn，执行n次，总时间复杂度为O( n logn)。
（2）for语句④更新lowcost和closest数据时，如果图采用邻接表存储，每次只检查t的邻接边，不用从1～n检查，检查更新的次数为E（边数），每次更新数据入队，入队的时间复杂度为logn，这样更新的时间复杂度为O( Elogn)。
构造最小生成树还有一种算法，Kurskal算法：设G=（V，E）是无向连通带权图，V={1，2，…，n}；设最小生成树T=（V，TE），该树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），Kruskal算法将这n个顶点看成是n个孤立的连通分支。它首先将所有的边按权值从小到大排序，然后只要T中选中的边数不到n−1，就做如下的贪心选择：在边集E中选取权值最小的边（i，j），如果将边（i，j）加入集合TE中不产生回路（圈），则将边（i，j）加入边集TE中，即用边（i，j）将这两个连通分支合并连接成一个连通分支；否则继续选择下一条最短边。把边（i，j）从集合E中删去。继续上面的贪心选择，直到T中所有顶点都在同一个连通分支上为止。此时，选取到的n−1条边恰好构成G的一棵最小生成树T。
那么，怎样判断加入某条边后图T会不会出现回路呢？
该算法对于手工计算十分方便，因为用肉眼可以很容易看到挑选哪些边能够避免构成回路（避圈法），但使用计算机程序来实现时，还需要一种机制来进行判断。Kruskal算法用了一个非常聪明的方法，就是运用集合避圈：如果所选择加入的边的起点和终点都在T的集合中，那么就可以断定一定会形成回路（圈）。其实就是我们前面提到的“避圈法”：边的两个结点不能属于同一集合。
步骤1：初始化。将图G的边集E中的所有边按权值从小到大排序，边集TE={ }，把每个顶点都初始化为一个孤立的分支，即一个顶点对应一个集合。
步骤2：在E中寻找权值最小的边（i，j）。
步骤3：如果顶点i和j位于两个不同连通分支，则将边（i，j）加入边集TE，并执行合并操作，将两个连通分支进行合并。
步骤4：将边（i，j）从集合E中删去，即E=E−{（i，j）}。
步骤 5：如果选取边数小于n−1，转步骤2；否则，算法结束，生成最小生成树T。
设G =（V，E）是无向连通带权图，如图2-98所示。
图2-98 无向连通带权图G
（1）初始化
将图G的边集E中的所有边按权值从小到大排序，如图2-99所示。
图2-99 按边权值排序后的图G
边集初始化为空集，TE={ }，把每个结点都初始化为一个孤立的分支，即一个顶点对应一个集合，集合号为该结点的序号，如图2-100所示。
图2-100 每个结点初始化集合号
（2）找最小
在E中寻找权值最小的边e1（2，7），边值为1。
（3）合并
结点2和结点7的集合号不同，即属于两个不同连通分支，则将边（2，7）加入边集TE，执行合并操作（将两个连通分支所有结点合并为一个集合）；假设把小的集合号赋值给大的集合号，那么7号结点的集合号也改为2，如图2-101所示。
图2-101 最小生成树求解过程
（4）找最小
在E中寻找权值最小的边e2（4，5），边值为3。
（5）合并
结点4和结点5集合号不同，即属于两个不同连通分支，则将边（4，5）加入边集TE，执行合并操作将两个连通分支所有结点合并为一个集合；假设我们把小的集合号赋值给大的集合号，那么5号结点的集合号也改为4，如图2-102所示。
图2-102 最小生成树求解过程
（6）找最小
在E中寻找权值最小的边e3（3，7），边值为4。
（7）合并
结点3和结点7集合号不同，即属于两个不同连通分支，则将边（3，7）加入边集TE，执行合并操作将两个连通分支所有结点合并为一个集合；假设我们把小的集合号赋值给大的集合号，那么3号结点的集合号也改为2，如图2-103所示。
图2-103 最小生成树求解过程
（8）找最小
在E中寻找权值最小的边e4（4，7），边值为9。
（9）合并
结点4和结点7集合号不同，即属于两个不同连通分支，则将边（4，7）加入边集TE，执行合并操作将两个连通分支所有结点合并为一个集合；假设我们把小的集合号赋值给大的集合号，那么4、5号结点的集合号都改为2，如图2-104所示。
图2-104 最小生成树求解过程
（10）找最小
在E中寻找权值最小的边e5（3，4），边值为15。
（11）合并
结点3和结点4集合号相同，属于同一连通分支，不能选择，否则会形成回路。
（12）找最小
在E中寻找权值最小的边e6（5，7），边值为16。
（13）合并
结点5和结点7集合号相同，属于同一连通分支，不能选择，否则会形成回路。
（14）找最小
在E中寻找权值最小的边e7（5，6），边值为17。
（15）合并
结点5和结点6集合号不同，即属于两个不同连通分支，则将边（5，6）加入边集TE，执行合并操作将两个连通分支所有结点合并为一个集合；假设我们把小的集合号赋值给大的集合号，那么6号结点的集合号都改为2，如图2-105所示。
图2-105 最小生成树求解过程
（16）找最小
在E中寻找权值最小的边e8（2，3），边值为20。
（17）合并
结点2和结点3集合号相同，属于同一连通分支，不能选择，否则会形成回路。
（18）找最小
在E中寻找权值最小的边e9（1，2），边值为23。
（19）合并
结点1和结点2集合号不同，即属于两个不同连通分支，则将边（1，2）加入边集TE，执行合并操作将两个连通分支所有结点合并为一个集合；假设我们把小的集合号赋值给大的集合号，那么2、3、4、5、6、7号结点的集合号都改为1，如图2-106所示。
图2-106 最小生成树
（20）选中的各边和所有的顶点就是最小生成树，各边权值之和就是最小生成树的代价。
（1）数据结构
int nodeset[N];//集合号数组
struct Edge {//边的存储结构
int u;
int v;
int w;
}e[N*N];（2）初始化
void Init(int n)
{
for(int i = 1; i <= n; i++)
nodeset[i] = i;//每个结点赋值一个集合号
}（3）对边进行排序
bool comp(Edge x, Edge y)
{
return x.w < y.w;//定义优先级，按边值进行升序排序
}
sort(e, e+m, comp);//调用系统排序函数（4）合并集合
int Merge(int a, int b)
{
int p = nodeset[a];//p为a结点的集合号
int q = nodeset[b]; //q为b结点的集合号
if(p==q) return 0; //集合号相同，什么也不做，返回
for(int i=1;i<=n;i++)//检查所有结点，把集合号是q的全部改为p
{
if(nodeset[i]==q)
nodeset[i] = p;//a的集合号赋值给b集合号
}
return 1;
}//program 2-8
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100;
int nodeset[N];
int n, m;
struct Edge {
int u;
int v;
int w;
}e[N*N];
bool comp(Edge x, Edge y)
{
return x.w < y.w;
}
void Init(int n)
{
for(int i = 1; i <= n; i++)
nodeset[i] = i;
}
int Merge(int a, int b)
{
int p = nodeset[a];
int q = nodeset[b];
if(p==q) return 0;
for(int i=1;i<=n;i++)//检查所有结点，把集合号是q的改为p
{
if(nodeset[i]==q)
nodeset[i] = p;//a的集合号赋值给b集合号
}
return 1;
}
int Kruskal(int n)
{
int ans = 0;
for(int i=0;i<m;i++)
if(Merge(e[i].u, e[i].v))
{
ans += e[i].w;
n--;
if(n==1)
return ans;
}
return 0;
}
int main()
{
cout <<"输入结点数n和边数m："<<endl;
cin >> n >> m;
Init(n);
cout <<"输入结点数u,v和边值w："<<endl;
for(int i=1;i<=m;i++)
cin >> e[i].u>> e[i].v >>e[i].w;
sort(e, e+m, comp);
int ans = Kruskal(n);
cout << "最小的花费是：" << ans << endl;
return 0;
}（1）时间复杂度：算法中，需要对边进行排序，若使用快速排序，执行次数为e*loge，算法的时间复杂度为O(e*loge)。而合并集合需要n−1次合并，每次为O(n)，合并集合的时间复杂度为O(n2)。
（2）空间复杂度：算法所需要的辅助空间包含集合号数组 nodeset[n]，则算法的空间复杂度是O(n)。
该算法合并集合的时间复杂度为O(n2)，我们可以用并查集（见附录E）的思想优化，使合并集合的时间复杂度降为O(e*logn)，优化后的程序如下。
//program 2-9
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100;
int father[N];
int n, m;
struct Edge {
int u;
int v;
int w;
}e[N*N];
bool comp(Edge x, Edge y) {
return x.w < y.w;//排序优先级，按边的权值从小到大
}
void Init(int n)
{
for(int i = 1; i <= n; i++)
father[i] = i;//顶点所属集合号，初始化每个顶点一个集合号
}
int Find(int x) //找祖宗
{
if(x != father[x])
father[x] = Find(father[x]);//把当前结点到其祖宗路径上的所有结点的集合号改为祖宗集合号
return father[x]; //返回其祖宗的集合号
}
int Merge(int a, int b) //两结点合并集合号
{
int p = Find(a); //找a的集合号
int q = Find(b); //找b的集合号
if(p==q) return 0;
if(p > q)
father[p] = q;//小的集合号赋值给大的集合号
else
father[q] = p;
return 1;
}
int Kruskal(int n)
{
int ans = 0;
for(int i=0;i<m;i++)
if(Merge(e[i].u, e[i].v))
{
ans += e[i].w;
n--;
if(n==1)
return ans;
}
return 0;
}
int main()
{
cout <<"输入结点数n和边数m："<<endl;
cin >> n >> m;
Init(n);
cout <<"输入结点数u，v和边值w："<<endl;
for(int i=1;i<=m;i++)
cin>>e[i].u>>e[i].v>>e[i].w;
sort(e, e+m, comp);
int ans = Kruskal(n);
cout << "最小的花费是：" << ans << endl;
return 0;
}算法实现和测试
（1）运行环境
Code::Blocks
（2）输入
输入结点数n和边数m：
7 12
输入结点数u，v和边值w：
1 2 23
1 6 28
1 7 36
2 3 20
2 7 1
3 4 15
3 7 4
4 5 3
4 7 9
5 6 17
5 7 16
6 7 25
（3）输出
最小的花费是：57（1）从算法的思想可以看出，如果图G中的边数较小时，可以采用Kruskal算法，因为Kruskal算法每次查找最短的边；边数较多可以用Prim算法，因为它是每次加一个结点。可见，Kruskal算法适用于稀疏图，而Prim算法适用于稠密图。
（2）从时间上讲，Prim算法的时间复杂度为O(n2)，Kruskal算法的时间复杂度为O(eloge)。
（3）从空间上讲，显然在Prim算法中，只需要很小的空间就可以完成算法，因为每一次都是从V−U集合出发进行扫描的，只扫描与当前结点集到U集合的最小边。但在Kruskal算法中，需要对所有的边进行排序，对于大型图而言，Kruskal算法需要占用比Prim算法大得多的空间。
