大家好，今天小編來為大家解答普里姆算法最小生成樹這個問題，克魯斯卡爾算法例題圖解很多人還不知道，現(xiàn)在讓我們一起來看看吧！

普里姆算法最小生成樹唯一嗎

不唯一

普里姆算法(Prim算法)是圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹。即由此算法搜索到的邊子集所構(gòu)成的樹中，不但包括了連通圖里的所有頂點，且其所有邊的權(quán)值之和亦為最小。該算法于1930年由捷克數(shù)學(xué)家沃伊捷赫·亞爾尼克(英語：VojtěchJarník)發(fā)現(xiàn)；并在1957年由美國計算機科學(xué)家羅伯特·普里姆(RobertC.Prim)獨立發(fā)現(xiàn)；1959年，艾茲格·迪科斯徹再次發(fā)現(xiàn)了該算法。因此，在某些場合，普里姆算法又被稱為DJP算法、亞爾尼克算法或普里姆－亞爾尼克算法。

pprim算法創(chuàng)始人

prim算法

羅伯特·普里姆

Prim算法,是普里姆算法,是圖論中的一種算法,可在加權(quán)連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構(gòu)成的樹中,不但包括了連通圖里的所有頂點,且其所有邊的權(quán)值之和亦為最小。該算法于1930年由捷克數(shù)學(xué)家沃伊捷赫·亞爾尼克發(fā)現(xiàn)

已知一個無向圖如下，分別用普里姆和克魯斯卡爾算法生成最小生成樹（假設(shè)以1為起點，試畫出構(gòu)造過程）

圖看不清，p，樹向外擴張，找最短外擴路徑k，增加一條不會造成回路的邊(現(xiàn)在選中的邊可以暫不相連)

prim算法時間復(fù)雜度為什么是ov

主要有兩個：

1.普里姆（Prim)算法特點：時間復(fù)雜度為O(n2).適合于求邊稠密的最小生成樹。

2.克魯斯卡爾（Kruskal)算法特點：時間復(fù)雜度為O(eloge)(e為網(wǎng)中邊數(shù)），適合于求稀疏的網(wǎng)的最小生成樹。

prim算法提出時間

Prim算法是一種用于解決最小生成樹問題的經(jīng)典算法，由捷克數(shù)學(xué)家沃伊切赫·約瑟夫·普里姆（VojtěchJarník）和美國計算機科學(xué)家羅伯特·普里姆（RobertPrim）分別在1930年和1957年提出。

沃伊切赫·約瑟夫·普里姆在1930年的論文中首次提出了Prim算法的基本思想和原理，用于解決最小生成樹問題。然而，當(dāng)時這個算法并沒有引起廣泛的注意和應(yīng)用。

后來，羅伯特·普里姆在1957年的論文中獨立地提出了類似的算法，稱之為Prim算法，并詳細描述了其工作原理和應(yīng)用。Prim算法通過貪心策略逐步選擇最小權(quán)重的邊來構(gòu)建最小生成樹，直到所有的頂點都被包含在生成樹中。

因此，Prim算法的提出可以追溯到1930年和1957年，分別由沃伊切赫·約瑟夫·普里姆和羅伯特·普里姆提出。這個算法在計算機科學(xué)和網(wǎng)絡(luò)優(yōu)化等領(lǐng)域得到了廣泛的應(yīng)用。

文章到此結(jié)束，如果本次分享的普里姆算法最小生成樹和克魯斯卡爾算法例題圖解的問題解決了您的問題，那么我們由衷的感到高興！