迪杰斯特拉算法和普利姆算法的区别?似乎感觉道理是一样的?

迪杰斯特拉算法和普利姆算法的区别?似乎感觉道理是一样的?
迪杰斯特拉算法和普利姆算法的区别?似乎感觉道理是一样的?

迪杰斯特拉算法和普利姆算法的区别?似乎感觉道理是一样的?
D算法是对边排序,然后找最短的,不在生成树中的,且加入后不会让生成树成环 的边,加入生成树,直到扫描完毕全部边.
P算法是先选出一个点加入生成树,然后找和这个生成树相连的边中最短的一条,加入生成树.直到全部点都被包括.

都是贪心算法.区别是,D算法实现时不需要考虑已有的生成树是什么样子的,但是要考虑一条边相连的两个点是不是在同一个连通块中,这点可以用并查集实现.P算法不需要考虑所有的边,但是需要"动态"地找出当前与生成树相连的边中最短一条,这点可以用堆实现.