一、定義

對于一個帶權(quán)連通無向圖G=(V,E)，生成樹不同，每棵樹的權(quán)(即樹中所有邊上的權(quán)值之和)也可能不同。設(shè)R為G的所有生成樹的集合，若T為R中邊的權(quán)值之和最小的生成樹，則T稱為G的最小生成樹(Minimum-Spanning-Tree, MST)。

二、手動實現(xiàn)算法

（1）Prim算法

介紹：從某一個頂點開始構(gòu)建生成樹;每次將代價最小的新頂點納入生成樹，直到所有頂點都納入為止。

時間復(fù)雜度:O()，適合用于邊稠密圖

例子1：

1、我們從P城開始，找到權(quán)最小的路徑，并構(gòu)建出新的樹。此時最小為1

2、再次尋找權(quán)最短的路徑，為P城到礦場。

3、如此反復(fù)，得到最終結(jié)果。

（2）Kruskal算法

介紹：每次選擇一條權(quán)值最小的邊，使這條邊的兩頭連通(原本已經(jīng)連通的就不選)，直到所有結(jié)點都連通。

時間復(fù)雜度:O(|E|*log2|E|)，適合用于邊稀疏圖

例子2：

1、我們從P城出發(fā)，找一條權(quán)值最小的邊，我們找到學(xué)校到P城的路徑為1（最短），于是連通它們。

2、再次找最短，找到2，連通它們。

3、反復(fù)執(zhí)行這個操作，直到所有的結(jié)點都連通。