体现了贪心算法的两种经典思想:选择最优解和子问题最优解的无后效性
1.选择最优解:Prim-Jarnik算法从一个任意节点开始,逐步向外扩展生成树,每次从尚未加入生成树的节点中选取距离生成树最近的一个节点并将其加入到生成树中。这个选择过程保证了每次选取都是当前状态下最优的决策,即选择离生成树最近的节点作为下一个节点,从而得到最小生成树。
2.子问题最优解的无后效性:Prim-Jarnik算法中的主要子问题是如何找到距离生成树最近的节点,并将其加入到生成树中。在这个子问题中,我们只关注已经加入生成树的节点与尚未加入生成树的节点之间的边,而不关注之前已经做出的选择。这种策略保证了选择当前状态下的最优解所得到的结果,不会因为之前的选择而发生改变。