Prim的算法(Prim's Algorithm)
Prim用于查找最小成本生成树的算法（如Kruskal算法）使用贪婪方法。 Prim的算法与shortest path first算法共享相似性。
与Kruskal算法相比，Prim的算法将节点视为单个树，并继续从给定图形向生成树添加新节点。
为了与Kruskal的算法形成对比并更好地理解Prim算法，我们将使用相同的例子 -
第1步 - 删除所有循环和平行边缘
从给定图中删除所有循环和平行边。 如果是平行边缘，请保留成本最低的一个并删除所有其他边缘。
步骤2 - 选择任意节点作为根节点
在这种情况下，我们选择S节点作为Prim生成树的根节点。 此节点是任意选择的，因此任何节点都可以是根节点。 有人可能想知道为什么任何视频都可以成为根节点。 所以答案是，在生成树中，包含图形的所有节点，并且因为它是连接的，所以必须至少有一条边，它将它连接到树的其余部分。
第3步 - 检查传出边缘并选择成本较低的边缘
在选择根节点S ，我们看到S，A和S，C分别是权重为7和8的两条边。 我们选择边缘S，A，因为它比另一边小。
现在，树S-7-A被视为一个节点，我们检查从它出来的所有边缘。 我们选择成本最低的那个并将其包含在树中。
在该步骤之后，形成S-7-A-3-C树。 现在我们将再次将其视为一个节点，并将再次检查所有边缘。 但是，我们只会选择成本最低的优势。 在这种情况下，C-3-D是新的边缘，小于其他边缘的成本8,6,4等。
在将节点D添加到生成树之后，我们现在有两个具有相同成本的边缘，即D-2-T和D-2-B。 因此，我们可以添加任何一个。 但下一步将再次产生边缘2作为最低成本。 因此，我们正在显示包含两个边的生成树。
我们可能会发现使用两种不同算法的同一图的输出生成树是相同的。
