模型建立與算法構(gòu)造：基于Prim算法構(gòu)造最小生成樹

李琳 趙娟 虎建勛

摘 要 最小生成樹有許多重要的應(yīng)用。例如：要在n個城市之間鋪設(shè)光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設(shè)光纜的費用很高，且各個城市之間鋪設(shè)光纜的費用不同，因此另一個目標是要使鋪設(shè)光纜的總費用最低。這就需要找到帶權(quán)的最小生成樹。本文通過使用Matlab軟件進行編程實現(xiàn)了用Prim算法構(gòu)造最小生成樹的分析運算。本程序可以方便地處理層次分析法下較大的運算量，解決層次分析法的效率問題，提高計算機輔助決策的時效性。其中建立了有效的基于Prim算法的數(shù)學(xué)模型并驗證了模型的合理性和科學(xué)準確性。利用MATLAB、EXCEL、SPSS13.0 for windows等軟件，實現(xiàn)了高效、準確的研究。

關(guān)鍵詞 模型 atlab軟件 算法構(gòu)造

中圖分類號：TP312文獻標識碼：A

1建立結(jié)構(gòu)模型

1.1最小生成樹相關(guān)概念

連通圖：任意兩個結(jié)點之間都有一個路徑相連。

生成樹（Spannirng Tree）：連通圖的一個極小的連通子圖，它含有圖中全部n個頂點，但只有足以構(gòu)成一棵樹的n-1條邊。

最小生成樹（Minimum Spannirng Tree）：連通圖的最小代價的生成樹（各邊的權(quán)值之和最小）。

最小生成樹即對于連通的帶權(quán)圖（連通網(wǎng)）G，其生成樹也是帶權(quán)的。生成樹T各邊的權(quán)值總和稱為該樹的權(quán)，記作：這里：TE表示T的邊集，w（u，v）表示邊（u，v）的權(quán)。權(quán)最小的生成樹稱為G的最小生成樹（Minimum SpannirngTree）。最小生成樹可簡記為MST。

1.2 Prim算法實現(xiàn)

Prim算法是一種貪心算法，將全部的頂點劃分為2個集合，每次總在2個集合之間中找最小的一條邊，局部最優(yōu)最終達到全局最優(yōu)，這正是貪心的思想。在無向加權(quán)圖中，n個頂點的最小生成樹有n-1條邊，這些邊使得n個頂點之間可達，且總的代價最小。

Prim算法的每一步都會為一棵生長中的樹添加一條邊，該樹最開始只有一個頂點，然后會添加個邊。每次總是添加生長中的樹和樹中除該生長的樹以外的部分形成的切分的具有最小權(quán)值的橫切邊。

設(shè)置兩個集合P和Q，其中P用來存放Q的最小生成樹中的頂點，集合Q存放G的最小生成樹的邊。令集合P的初值為P={V1}（假設(shè)構(gòu)造最小生成樹時，從頂點V1出發(fā)），集合Q的初值為Q= 。Prim算法的思想是，從所有的邊中，選取具有最小權(quán)值的邊PV，將頂點V加入集合Q中，如此不斷重復(fù)，直到P=V時，最小生成樹構(gòu)造完畢，這時集合Q中包含了最小生成樹的所有邊。

Prim的算法如下：

2案例分析

舉例：用Prim求圖1最小生成樹。

用的第一、二、三行分別表示樹的起點、終點、權(quán)集合。MATLAB 程序如下：

clc;

clear;

a=zeros（7）;

a（1，2）=50;a（1，3）=60;

a（2，4）=65;a（2，5）=40;

a（3，4）=52;a（3，7）=45;

a（4，5）=50;a（4，6）=30;a（4，7）=42;

a（5，6）=70;

a=a+a';a（find（a==0））=inf;

result=[];p=1;tb=2;length（a）;

while length（result）～=length（a）-1

temp=a（p，tb）;temp=temp（：）;

d=min（temp）;

[jb，kb]=find（a（p，tb）==d）;

j=p（jb（1））;k=tb（kb（1））;

result=[result，[j;k;d]];p=[p，k];tb（find（tb==k））=[];

end

Result

計算結(jié)果如圖2所示：所以由結(jié)果可得起點為1，終點為2，權(quán)集合為50。很明顯對于每個節(jié)點（初始節(jié)點除外），都要進行此次遍歷查找距離樹最近節(jié)點O（n），和一次更新操作O（n），所以總的時間復(fù)雜度為O（n^2）。

參考文獻

[1] 嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)預(yù)算法分析[M].北京：清華大學(xué)出版社，2011.

[2] 劉來福，曾文藝.數(shù)學(xué)模型與數(shù)學(xué)建模[M].北京：北京師范大學(xué)出版社，1997.

[3] 王周宏.運籌學(xué)基礎(chǔ)[M].北京：清華大學(xué)出版社，北京交通大學(xué)出版社，2010.

[4] 徐全智，楊晉浩.數(shù)學(xué)建模[M].高等教育出版社，2004.

[5] 姜啟源，謝金星等.數(shù)學(xué)模型（第三版）[M].高等教育出版社，2004.

[6] 程杰.大話數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社，2011.

[7] 梁西陳.最小生成樹在網(wǎng)絡(luò)設(shè)計中的應(yīng)用[J].宿州教育學(xué)院學(xué)報，2008（11）.

[8] 王新奇.最小生成樹算法及其應(yīng)用[J].西安文理學(xué)院學(xué)報，2009（12）.