今天來(lái)介紹第二部分，圖論中非常重要的知識(shí)點(diǎn)——最小生成樹(shù)。作為數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)，Prim算法和克魯斯卡爾算法的思想此處博主不詳細(xì)介紹，建議在閱讀本帖前熟練掌握。

對(duì)于無(wú)向帶權(quán)圖，在MATLAB中可以直接以鄰接矩陣的方式創(chuàng)建出來(lái)，如下：

A=[0 20 0 0 15 0;20 0 20 60 25 0;0 20 0 30 18 0;0 60 30 0 35 10;15 25 18 35 0 15;0 0 0 10 15 0];
G=graph(A);

但是這種創(chuàng)建方式對(duì)于可視化并不是很友好——無(wú)法在圖上顯示每條邊對(duì)應(yīng)的權(quán)值，因此采用下面的方式創(chuàng)建：

s=[1 1 2 2 2 3 3 4 4 5];
t=[2 5 3 4 5 4 5 5 6 6];
weights=[20 15 20 60 25 30 18 35 10 15];
G=graph(s,t,weights);
plot(G,'EdgeLabel',weights);

創(chuàng)建出的帶全無(wú)向圖如下：

?首先我們先用普利姆算法手寫(xiě)一遍，得出的答案如下：

然后用MATLAB計(jì)算并可視化，用到內(nèi)置函數(shù)minspantree：?

T=minspantree(G);
plot(T);

計(jì)算結(jié)果如下：

如圖，和博主手算的略微有區(qū)別：其實(shí)是因?yàn)?——2與2——3兩條邊的權(quán)值一致，所以最后找到的結(jié)點(diǎn)2無(wú)論和結(jié)點(diǎn)1還是結(jié)點(diǎn)3連接都正確~?