【读书笔记】算法漫步 第8章

问题9 连通的代价

 图的连通问题是一个图的基本问题，如何用最小的代价把图中所有节点连通起来，称为最小生成树问题。最小生成树问题的应用很广。

本章在介绍问题求解时，按照算法基本思想—算法描述—算法运行示例—算法分析这4个步骤展开介绍。【作者感受，这个4个步骤是学习各种算法的标准步骤，对学习者各方面能力的训练都有帮助，还可以加上，代码实现，就更完整】

本书详细介绍的求解最小生成树问题的算法，不是一般数据结构、算法书中常见的Kruskal算法、Prim算法、破圈法算法。而且没有给出算法的出处。这里就不详细介绍了，推荐自读。

【作者感受】

求解最小生成树问题的有效算法值得学习，因为最小生成树问题应用很广。

图的生成树和最小生成树有很多（图的）特色性质，有兴趣的读者可以在图论中学习。

针对图的最小生成树问题，可以采用贪心算法设计策略，如何设计具体的贪心策略，就是不同的算法。不同的算法可能展现出不同的优势，更好地适应不同的输入数据（图）；同时，学习不同的算法，分析不同算法的性能（效率和适用性），可以加深对最小生成树问题的理解，训练读者的算法思维。

要实现最小生成树算法的实际运行时间，需要一些复杂的数据结构的支持（空间换时间）。

证明最小生成树算法的正确性，需要用到图论的一些知识，还会用到归纳法或反证法，需要一定的数学基础。

学习本章，对算法逻辑、程序和数据结构、数学知识都涉猎，有一点难度，但是难度还好。

所以，最小生成树算法是数据结构、算法教材中必有的内容。