prim算法和kruscal算法的區(qū)別？Prim算法：Prim算法將所有頂點分為A和B兩部分。A是目標(biāo)集。該算法可以看作是一個不斷地將B中的頂點轉(zhuǎn)移到一個集合的過程。在這個過程中，從B中的每個頂點到樹

prim算法和kruscal算法的區(qū)別？

Prim算法：

Prim算法將所有頂點分為A和B兩部分。A是目標(biāo)集。該算法可以看作是一個不斷地將B中的頂點轉(zhuǎn)移到一個集合的過程。在這個過程中，從B中的每個頂點到樹的最短距離是不斷更新和排序的。根據(jù)貪心思想，將無環(huán)最短路徑的頂點從B移到a，Prim算法是在加權(quán)連通圖中尋找最小生成樹，即權(quán)值最小且連通到所有節(jié)點的樹。重點放在樹上，樹沒有環(huán)。

Prim算法是這樣做的：

首先將一個節(jié)點作為最小生成樹的初始節(jié)點，然后迭代求出最小生成樹中每個節(jié)點的最小權(quán)邊，并將其加入到最小生成樹中。如果連接后生成循環(huán)，請?zhí)^此邊并選擇下一個節(jié)點。當(dāng)所有節(jié)點都加入到最小生成樹中時，就可以找到連通圖中的最小生成樹。

2、Kruskal算法：

kruska算法將多個頂點分成N個部分。該算法可以看作是一個連續(xù)合并n個部分的過程。在此過程中，根據(jù)權(quán)值對多條邊進(jìn)行排序，然后根據(jù)貪婪思想對權(quán)值最短且無循環(huán)的頂點進(jìn)行合并。

Kruskal算法和prim算法的區(qū)別在于，Kruskal需要將所有權(quán)重邊從小到大排序，然后才能找到最小的生成樹節(jié)點。排序后的加權(quán)邊依次添加到最小生成樹中。如果添加時生成循環(huán)，將跳過此邊并添加下一條邊。當(dāng)所有節(jié)點都加入到最小生成樹中時，就會找到最小生成樹。

毫無疑問，Kruskal算法比prim算法在效率上更快，因為Kruskal只需要對加權(quán)邊進(jìn)行一次排序，而prim算法需要對加權(quán)邊進(jìn)行多次排序。盡管prim算法所涉及的加權(quán)邊可能不能覆蓋連通圖中的所有邊，但隨著排序算法效率的提高，Kruskal算法與prim算法的區(qū)別將更加明顯。

圖所示是一個無向帶權(quán)圖,請分別按Prim算法和Kruskal算法求最小生成樹？

prim算法的基本思想是假設(shè)n=（V，e）是一個有n個頂點的連通網(wǎng)絡(luò)，T=（U，TE）是最小生成樹，其中U是T的頂點集，TE是T的邊集。（1）初始U={U0}（U0∈V），TE=φ；（2）從U∈U的所有邊中選擇最小代價邊（U0，V0），V∈V-U并合為te，V0并合為U；（3）重復(fù)（2）直到U=V，此時te必須包含n-1條邊，則t=（V，{te}）是n的最小生成樹，Kruskal算法的基本思想是假設(shè)n=（V，e）是一個具有n個頂點的連通網(wǎng)絡(luò)，（1）n個頂點被視為n個集合；（2） 根據(jù)從小到大的權(quán)重順序選擇邊。所選邊應(yīng)滿足兩個頂點不在同一組頂點中，且該邊位于生成樹的邊集中。同時，合并邊的兩個頂點集；（3）重復(fù)（2），直到所有頂點都在同一個頂點集中。注：1。最小生成樹不是唯一的。2圖形從最小的節(jié)點開始。