算法圖論實(shí)驗(yàn)報(bào)告2

1、云南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院實(shí)驗(yàn)教學(xué)中心云南大學(xué)數(shù)學(xué)系算法圖論實(shí)驗(yàn)上機(jī)實(shí)驗(yàn)報(bào)告課程名稱(chēng)：算法圖論實(shí)驗(yàn)學(xué)期：20132014學(xué)年秋季學(xué)期成績(jī)：指導(dǎo)教師：李建平學(xué)生姓名：學(xué)生學(xué)號(hào)：實(shí)驗(yàn)名稱(chēng): 求一個(gè)賦權(quán)圖中權(quán)重值不超過(guò)B的最小插點(diǎn)數(shù)問(wèn)題實(shí)驗(yàn)編號(hào)：No.2實(shí)驗(yàn)日期：2014.10.15實(shí)驗(yàn)學(xué)時(shí)：學(xué)院：數(shù)學(xué)與統(tǒng)計(jì)學(xué)院專(zhuān)業(yè)：數(shù)學(xué)與應(yīng)用數(shù)學(xué)年級(jí)：2011級(jí)1、 實(shí)驗(yàn)?zāi)康模?） 求一個(gè)賦權(quán)圖中權(quán)重值不超過(guò)B的最小插點(diǎn)數(shù)問(wèn)題，即求解給定賦權(quán)圖的最小支撐樹(shù)的插點(diǎn)數(shù)問(wèn)題。（2） 復(fù)習(xí)一下上學(xué)期學(xué)習(xí)的求最小支撐樹(shù)的算法。二、實(shí)驗(yàn)內(nèi)容（1）先求解下列賦權(quán)圖的最小支撐樹(shù)：（2）然后再求解其最小支撐樹(shù)的最小插點(diǎn)數(shù)。三、使用環(huán)境

2、個(gè)人計(jì)算機(jī)，MATLAB軟件四、算法介紹Algorithm Name: 最小支撐數(shù)的插點(diǎn)數(shù)Input: 輸入約束權(quán)重值B、限制長(zhǎng)度d、賦權(quán)圖帶權(quán)鄰接矩陣a、頂點(diǎn)個(gè)數(shù)nOutput: 輸出最小支撐樹(shù)的邊E(T)以及該支撐樹(shù)相應(yīng)的最小插點(diǎn)數(shù)Begin Step1: 由Prim算法求出賦權(quán)圖的最小支撐樹(shù)T； Step2: 當(dāng)W(T)>B時(shí)，則停止，無(wú)可行解； Step3: 對(duì)于最小支撐樹(shù)T的邊，且權(quán)重為w(e),在邊e中插入insert(e)個(gè)頂點(diǎn)，其中； Step4: 對(duì)于最小支撐樹(shù)T的邊，求出；End第 6 頁(yè) 共 6 頁(yè)五、調(diào)試過(guò)程1. 程序代碼%B=15%d=1.5%a=inf 3 4

3、 inf inf inf;3 inf 6 4 2 inf;4 6 inf 5 inf inf;inf 4 5 inf 4 1;inf 2 inf 4 inf 2;inf inf inf 1 2 inf%n=6clc;clear;B=input('請(qǐng)輸入約束權(quán)重值：'); %權(quán)重值不超過(guò)Bd=input('請(qǐng)輸入限制長(zhǎng)度：');a=input('請(qǐng)輸入賦權(quán)圖帶權(quán)鄰接矩陣：');n=input('請(qǐng)輸入賦權(quán)圖頂點(diǎn)個(gè)數(shù)：');V=ones(1,n); %把頂點(diǎn)全部標(biāo)記為1V(1)=0; %選第一個(gè)頂點(diǎn)為初值，選出的頂點(diǎn)標(biāo)記為0s=1;

4、%記下已選出的頂點(diǎn)數(shù)目k=0; %用來(lái)記錄選出的邊minW=0; %用來(lái)累加權(quán)值sum=0; %用來(lái)累加插點(diǎn)數(shù)while s<n %當(dāng)頂點(diǎn)數(shù)小于n時(shí)循環(huán) for i=1:n %從候選邊（即反圈集合）中找出權(quán)重最小的邊 de=Inf; %所選邊的權(quán)重初值 for j=1:n if V(i)=0&&V(j)=1&&a(i,j)<de de=a(i,j); f=i; e=j; %記錄下滿(mǎn)足條件的邊i-j end end if de=Inf flag=0; V(e)=0; %對(duì)已選的頂點(diǎn)標(biāo)號(hào)為0 k=k+1; s=s+1; minW=minW+de; %累加

5、最小權(quán)值 Tree(:,k)=f,e,de; %最小支撐樹(shù)的第k條邊及權(quán)值 end endendif minW<=B m=size(Tree,2); insert=0; for j=1:m insert=ceil(Tree(3,j)/d)-1; sum=sum+insert; end disp('插點(diǎn)數(shù)為：'); sum %最小支撐樹(shù)的插點(diǎn)數(shù)else disp('不存在最小插點(diǎn)數(shù)!')endif flag=0 disp('最小樹(shù)邊權(quán)矩陣為：'); Tree %最小支撐樹(shù)的邊權(quán)矩陣 disp('最小樹(shù)權(quán)值為：'); minW

6、%最小支撐樹(shù)的權(quán)值end2運(yùn)行窗口：（1）在命令窗口中輸入：請(qǐng)輸入約束權(quán)重值：15請(qǐng)輸入限制長(zhǎng)度：1.5請(qǐng)輸入賦權(quán)圖帶權(quán)鄰接矩陣：inf 3 4 inf inf inf;3 inf 6 4 2 inf;4 6 inf 5 inf inf;inf 4 5 inf 4 1;inf 2 inf 4 inf 2;inf inf inf 1 2 inf請(qǐng)輸入賦權(quán)圖頂點(diǎn)個(gè)數(shù)：6（2）輸出：所以最小支撐樹(shù)為：最小支撐樹(shù)的插點(diǎn)圖（圖中的點(diǎn)圈表示插點(diǎn)）如下：六、總結(jié)本實(shí)驗(yàn)主要是先用反圈法找出圖的最小支撐樹(shù)，然后再判斷此最小支撐樹(shù)的權(quán)重值之和是否超過(guò)B，如果不超過(guò)B，再計(jì)算其最小插點(diǎn)數(shù)。通過(guò)本實(shí)驗(yàn)，讓我復(fù)習(xí)了上學(xué)期學(xué)習(xí)的找最小支撐樹(shù)的算法。在編程的過(guò)程中，對(duì)程序循環(huán)部分有點(diǎn)困難，后來(lái)，通過(guò)問(wèn)同學(xué)，看書(shū)，解決了這個(gè)問(wèn)題，這樣才順利的完成了這個(gè)實(shí)驗(yàn)。在做這個(gè)實(shí)驗(yàn)的同時(shí)，我也學(xué)到了很多知識(shí)，比如說(shuō)，編程方面的知識(shí)，有關(guān)ma