数据结构&算法 Prim 生成树算法

  • 生成树 Kruskal 算法

    Prim的寻找最小成本生成树的算法(如Kruskal的算法)使用贪婪方法。Prim的算法与最短路径优先算法具有相似之处。与Kruskal算法相反,Prim算法将节点视为一棵树,并继续从给定图向生成树添加新节点。为了与Kruskal算法进行对比并更好地了解Prim算法,我们将使用相同的示例-
    tree
    第1步-删除所有循环和平行边
    tree
    如果边缘平行,则保持成本最低的边缘,并去除所有其他边缘。
    tree
    第2步-选择任意节点作为根节点
    在这种情况下,我们选择S节点作为Prim生成树的根节点。该节点是任意选择的,因此任何节点都可以是根节点。有人可能想知道为什么任何视频都可以成为根节点。因此答案是,在生成树中,包括了图的所有节点,并且由于它是连接的,因此必须至少有一条边,它将其连接到树的其余部分。
    第3步-检查输出边并选择成本较低的边
    选择根节点S后,我们看到S,A和S,C分别是权重为7和8的两个边。我们选择边S,A,因为它比另一个小。
    tree
    步骤3-添加重量最小的边缘
    现在,将树S-7-A视为一个节点,我们检查所有从树出的边。我们选择成本最低的一种并将其包括在树中。
    tree
    在该步骤之后,形成S-7-A-3-C树。现在,我们再次将其视为节点,并将再次检查所有边缘。但是,我们只会选择成本最低的优势。在这种情况下,C-3-D是新边,它比其他边的成本8、6、4等少。
    tree
    在将节点D添加到生成树之后,现在有两个边缘具有相同的开销,即D-2-T和D-2-B。因此,我们可以添加一个。但是,下一步将再次使边缘2成本最低。因此,我们显示了一个包含两个边缘的生成树。
    tree
    我们可能会发现使用两种不同算法的同一图的输出生成树是相同的。