对最小生成树的两种普遍方法的小比较,总的来说prim和kruskal算法其实是互通的,区别在于prim是从点开始找到最小的那棵树,而kruskal是从边开始找最小的那棵树,所以就造成了我们要通过题意和题目的输入去判断我们该用那种方法去做更简单.最简单的判定方式是一般用kruskal算法做,因为kruskal算法简单易敲.当然也是要看题目的输入.
比如这道题(请点击这个蓝色字体)
题目输入是以一个矩阵形式输入,所以明显用prim做更简单.
还有一点就是在用prim做的题中每两个地点是只有一条路的,而kruskal不管是多少条路都适用。
总之,变形题也有很多,需要我们严谨的思考,多动动脑袋就能A出来的!!!
网友评论