普里姆演算法可以有迴路嗎路嗎

❶ 普里姆演算法是什麼

普里姆(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）演算法。