primkruskal演算法

① Kruskal演算法和Prim演算法構造它的一棵最小代價生成樹的過程

Prim演算法復雜度：O(n2), 與邊無關，適合求邊稠密的網的最小生成樹。

演算法思想：假設N={V,{E}}是連通網，TE是N上最小生成樹中邊的集合。演算法從U={u0},TE ={}開始，重復執行下述操作：在所有u∈U,v∈V-U的邊（u，v）∈E中找一條代價最小的邊（u0,v0）並入集合TE，同時v0並入U，直至U=V為止。

Kruskal演算法復雜度：O(eloge)，相對於Prim而言，適合求邊稀疏的網的最小生成樹。

演算法思想：最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=(V,{})，圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則捨去次邊而選擇下一條代價最小的邊。直至T中所有頂點都在同一連通分量上為止。

② prim和kruscal演算法得到的最小生成樹是否一樣

應該不一樣。可以用一個圖根據兩演算法試一下，若一樣，再修改圖，之後應該就可以了。
（網路或者查書本更加有效……）
構造G的最小生成樹的Prim演算法的基本思想是：首先置S={1}，然後，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且c[i][j]最小的邊，將頂點j添加到S中。
這個過程一直進行到S=V時為止。
Kruskal演算法構造G的最小生成樹：將所有的邊按權從小到大排序。然後從第一條邊開始，依邊權遞增的順序查看每一條邊，並按下述方法連接2個不同的連通分支：當查看到第k條邊(v, w)時，如果端點v和w分別是當前2個不同的連通分支T1和T2中的頂點時，就用邊(v, w)將T1和T2連接成一個連通分支，然後繼續查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看第k+1條邊。這個過程一直進行到只剩下一個連通分支時為止

③ prim演算法和kruskal演算法的區別

邊數較少可以用Kruskal,因為Kruskal演算法每次查找最短的邊。 邊數較多可以用Prim，因為它是每次加一個頂點，對邊數多的適用。

④ 已知一個無向圖如下圖所示,要求分別用Prim和Kruskal演算法生成最小樹(假設以①為起點,試畫出

p，樹向外擴張，找最短外擴路徑

k，增加一條不會造成迴路的邊(現在選中的邊可以暫不相連)

按照prim是：（從起點到終點的邊）

46，45，51，63，12，32

按照kruskal是：

46，15，45，63，12，32

克魯斯卡爾演算法思想先將邊中的權值從小到大排序，每次找出候選邊中權值最小的邊，就將該邊並入生成樹中。重復此過程直到所有邊都被檢測完為止。

其中要注意的是克魯斯卡爾演算法需要用到並查集，以此來判斷接下來要並入的邊是否會和已並入的邊構成迴路。這兩個圖分別用普里姆和克魯斯卡爾生成的最小生成樹見圖。

(4)primkruskal演算法擴展閱讀：

無向圖G=<V,E>,其中：

1、V是非空集合，稱為頂點集。

2、E是V中元素構成的無序二元組的集合，稱為邊集。

解釋

直觀來說，若一個圖中每條邊都是無方向的，則稱為無向圖。

無向邊的表示

無向圖中的邊均是頂點的無序對，無序對通常用圓括弧表示。

⑤ prim演算法構造出的最小生成樹唯一嗎prim演算法和kruskal演算法構造出的最小生成樹一樣嗎

不唯一，兩種演算法構造出的最小生成不一定相同。

⑥ 13.用Prim演算法和Kruskal演算法構造圖的最小生成樹,所得到的最小生成樹是否相同

如果原來的圖裡面任何兩條邊長都不相同,那麼最小生成樹是唯一的,此時不管用什麼方法算出來的都是一樣的
但是如果圖里有相等的邊,那麼最小生成樹可能會不唯一,這樣就無法保證不同的方法得到同一棵樹（即使是同一個演算法,只要圖的編號方式改變也可能得到不同的最小生成樹）

⑦ 圖所示是一個無向帶權圖,請分別按Prim演算法和Kruskal演算法求最小生成樹.

•普里姆（Prim）演算法

基本思想

假設N=(V,E)是一個具有n個頂點的連通網，T=(U,TE)是所求的最小生成樹，其中U是T的頂點集，TE是T的邊集。

（1）初始U={u0}(u0∈V),TE=φ；

（2）在所有u∈U,v∈V-U的邊中選一條代價最小的邊（u0，v0）並入集合TE，同時將v0並入U；

（3）重復（2），直到U=V為止。

此時，TE中必含有n-1條邊，則T=（V，{TE}）為N的最小生成樹。

注意：1.最小生成樹不唯一。

2.該圖從節點最小開始。

⑧ 如何用淺顯的語言解釋Kruskal演算法和Prim演算法

不嚴謹的說：將全集分為遍歷集合未遍歷集。兩種演算法都是遍歷集慢慢擴大為全集的過程。
Kruskal：集合中元素是邊，每次從未遍歷集中找一個最短邊，如果遍歷集包含它後不會構成迴路，就包含，重復過程直到所有點都連通。
Prim：集合中元素是點，每次從未遍歷集中找一個距離遍歷集距離最近的點，將其包含，重復過程直到包含所有點。
當然對於Kruskal，遍歷集並沒有擴展為全集，把全部邊都包含了也沒有意義了。

⑨ 用普里姆（Prim）或克魯斯卡爾（Kruskal）演算法，畫出下列無向網的最小生成樹

如圖，這是Prim演算法構造最小生成樹的每一步，這里是以A點為初始點。

最小生成樹用權重是60

⑩ 如圖1所示，用prim演算法和Kruskal演算法構造最小生成樹。

prim演算法：假設初始節點為A，則擴展的點的順序為：
加入邊AC，擴展C節點
加入邊AB，擴展B節點
加入邊CD，擴展D節點
加入邊BF，擴展F節點
加入邊DE，擴展E節點

所以最小生成樹含有的邊為：AC、AB、CD、BF、DE

kruskal演算法：
加入邊AC
加入邊DE
加入邊AB
加入邊BF
加入邊CD

最小生成樹與上面一樣