數據結構prim演算法

1. 這是一道數據結構問題，問題如下：對於如下圖所示的帶權無向圖，給出利用普利姆（Prim)演算法和克魯斯卡爾

自己按下面的先後過程畫圖即是生成過程；說雀雀明（i,j）是一條連接頂點i和j的一條邊；
普利姆（Prim)演算法：從頂點0開始頃世早構造
（0,1），（0,2），（1,2），（2,5），（5,4）
克魯斯卡爾演算法：
（0,1），（0,2），（返或1,2），（4,5），（2,5）

2. 什麼是普利姆演算法

Prim演算法：是圖的最小生成樹的一種構造演算法。

假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，TV 是 WN 上最小生成樹中頂點的集合，TE 是最小生成樹中邊的集合。顯然，在演算法執行結束時，TV=V，而 TE 是 E 的一個子集。在演算法開始執行時，TE 為空集，TV 中只有一個頂點，因此，按普里姆演算法構造最小生成樹的過程為：在所有「其一個頂點已經落在生成樹上，而另一個頂點尚未落在生成樹上」的邊中取一條權值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止。

如果看不懂還可以找一本數據結構的書看，這個演算法挺簡單的。

btw：其實你有空問，應該有空網路啊~網路就有了。懶得寫，我還是直接從網路過來的~

3. 數據結構里提到的普里母和克魯斯卡爾分別是哪個國家的

普里母演算法和克魯斯卡爾方法求最小生成樹完整程序

1、普里姆演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點（英語：Vertex (graph theory)），且其所有邊的權值之和亦為最小。該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發現；並在1957年由美國計算機科學家羅伯特·普里姆（英語：Robert C. Prim）獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆－亞爾尼克演算法

2、Kruskal演算法是一種用來尋找最小生成樹的演算法，由Joseph Kruskal在1956年發表。用來解決同樣問題的還有Prim演算法和Boruvka演算法等。三種演算法都是貪婪演算法的應用。和Boruvka演算法不同的地方是，Kruskal演算法在圖中存在相同權值的邊時也有效。

4. prim演算法是什麼

prim演算法是圖論中的一種演算法。

普里姆演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點（英語：Vertex (graph theory)），且其所有邊的權值之和亦為最小。

簡介

最小生成樹是數據結構中圖的一種重要應用，它的要求是從一個帶權無向完全圖中選擇n－1條邊並使這個圖仍然連通（也即得到了一棵生成樹）,同時還要考慮使樹的權最小。

為了得到最小生成樹，人們設計了很多演算法，最著名的有prim演算法和kruskal演算法。教材中介紹了prim演算法，但是講得不夠詳細，理解起來比較困難，為了幫助大家更好的理解這一演算法，本文對書中的內容作了進一步的細化，希望能對大家有所幫助。