普里姆算法可以有回路吗路吗

❶ 普里姆算法是什么

普里姆(Prim)算法，和克鲁斯卡尔算法一样，是用来求加权连通图的最小生成树的算法。

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

基本思想：

对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。

从所有uЄU，vЄ(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v)，将顶点v加入集合U中，将边(u, v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。

❷ 普里姆算法是什么

在计算机科学中，普里姆(也称为Jarník's)算法是一种贪婪算法，它为加权的无向图找到一个最小生成树 。

相关简介：

这意味着它找到边的一个子集，能够形成了一个包括所有顶点的树，其中在树中所有边的权重总和最小。该算法通过从任意起始顶点开始一次给树增加一个顶点来操作，在每个步骤中添加从树到另一个顶点的花费最小的可能的连接。

该算法由捷克数学家沃伊茨奇·贾尼克于1930年开发后，后来在1957年被计算机科学家罗伯特·普里姆，以及在1959年被艾兹赫尔·戴克斯特拉重新发现和重新出版。因此，它有时也被称为Jarník算法,普里姆-jarník算法。普里姆-迪克斯特拉算法或者DJP算法。

这个问题的其他众所周知的算法包括克鲁斯卡尔算法和 Borvka's算法。这些算法在一个可能的非连通图中找到最小生成森林；相比之下，普里姆算法最基本的形式只能在连通图中找到最小生成树。然而，为图中的每个连通分量单独运行普里姆算法，也可以用于找到最小生成森林。

就渐近时间复杂度而言，这三种算法对于稀疏图来说速度相同，但比其他更复杂的算法慢。然而，对于足够密集的图，普里姆算法可以在线性时间内运行，满足或改进其他算法的时间限制。

❸ prim算法是基于什么原理

贪心
具体证明可以看《算法导论》最小生成树那章

❹ Prim算法为什么能保证迷宫有唯一通路

为了减少不必要的麻烦，可以不妨设图中所有边的权重都不同，这样最小生成树是唯一的
然后直接用反证法就行了
如果Prim算法得到G，而最小生成树是T
设在生成G的过程中第一次产生的不在T中的边是e，而在G中去掉e得到的两个连通分支记为V1和V2，那么e连接了V1和V2

把e加入T之后会出现环，在这个环里面V1的顶点和V2的顶点至少还被另一条边f连接（否则T本身就不连通了），由Prim算法的贪心策略可知e比f权重低，那么在T里面把f换成e可得一个总权重更小的生成树，与T的最小性矛盾

（因为最小生成树的总权重的边的权重的连续函数，对于有权重重复出现的情况可以利用连续性取极限，这样即使最小生成树不唯一仍然可以保证Prim算法生成的树具有最小权重）

❺ 在N个城市之间铺设煤气管道,只需架设N-1条线路即可,如何以最低的经济代价铺设.(普里姆算法)

此题可以用最小生成树的办法解决即普里姆算法:把N个城市看作N个顶点,把可以铺设管道的两个城市间用线连起来,把相连的两个城市之间的距离作为这一条边的权(假设所有管道的单位造价相同).把所有边的权按照大小排列起来,先选权最小的边的两个顶点纳入集合S,再选第二条边,把与这条边关联的顶点纳入S,但前提是所选的边不能与前面所选的边构成回路,就这样依次选取.若有权相同的n条边则任选一条,但前提是所选的边不能与前面所选的边构成回路.接下来选的时候还是选n条边中的一条前提依然和前面相同.当所选的路的个数为N-1时就停止.此时的线路即为最优的铺设线路.

❻ prim算法的三项原则

每次选最小边
不构成回路

❼ 普里姆算法

可以这么理解：因为最小生成树是包含所有顶点的所以开始lowcost先储存到第一个点的所有值，然后执行下面算法，找到最小值并记录是第几个点，比如说这个点是3，这样有了一条1-3得道路已经确定，现在从3出发找从3出发到其他顶点的路径，如果这个从3出发到达的路径长度比从1出发的短，则更新lowcost，这样使得lowcost保存一直到达该顶点的最短路径。比如1-4是5，3-4是4，则lowcost从原来的5被改为4。

❽ prim算法是什么

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。

算法的发展：

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

❾ 怎样判断prim算法中是否出现环路

有圈就是环路，这个应该很好看出来的，prim算法就不会出现环路
如果你非要判断的话，那就加上线以后拓扑排序，判断有无环路

❿ 普里姆算法的相关概念

1）生成树一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成树是对连通图而言的，是连通图的极小连通子图，包含图中的所有顶点，有且仅有n-1条边。非连通图的生成树则组成一个生成森林；若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。
2）和树的遍历相似，若从图中某顶点出发访遍图中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历，(Traversing Graph)。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的遍历顺序有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。对每种搜索顺序，访问各顶点的顺序也不是唯一的。
3）在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G′称做图G的生成树。一个图可以有多个生成树，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边也就不同。
在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。常见的求最小生成树的方法有两种：克鲁斯卡尔(Kruskal)算法和普里姆（Prim）算法。