Prim针对点，而Kruskal针对边。Prim只适合无向带权图。维持一个集合，一开始选定一个点作为初始集合，另维持一个prev和dist列表。dist列表表示初始集合到其余所有点的距离，prev表示新加入集合的节点的前一个节点。它的加入策略是：不属于集合的且离集合最近的点。
即：Prim算法不断加入节点，直到所有节点都加入集合。
需要注意Prim和Dijkstra算法很相似，Dijkstra也是维持一个节点列表，并不断往集合中添加节点，但是Dijkstra也适合有向图，而且Dijkstra计算的是单一源节点到其余所有节点的最短距离，而Prim生成的是使得所有边的权值之和最小。
Kruskal算法是针对边的算法，采用并查集的方法。其首先以每个顶点单独作为一个集合，然后对所有边进行排序，选取最短的边，如果该边中两个节点不属于同一个并查集，那么就将这两个节点所属的并查集合并为同一个并查集，n个节点，共需要n-1条有效边。
并查集：定义一个father列表，一开始每个节点的father都是它自己，然后加入新节点后，新节点的father定义为这个并查集的总的father，然后每次判断两个节点是否在同一个并查集时，只需判断他们father是否相同即可。关于father的查找，可以用father[x] == x来判断，为True，就找到了该并查集的father。
同时father列表也可以用于保存最小生成树的形状。
而如果不需要保存最小生成树的形状，也可以在A、B并查集合并时，让B集中所有元素的father都等于A的father，这样每个节点都能直接找到最终father，能加快速度。
每发现一条有效边时，需要保存其权重，作为最终的权值之和。
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/rfx/25049.html