




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、prim算法設(shè)置兩個(gè)集合P和Q,其中P 用于存放G的最小生成樹(shù)中的頂點(diǎn),集合Q存放G的最小生成樹(shù)中的邊。令集合P的初值為P=V1(假設(shè)構(gòu)造最小生成樹(shù)時(shí),從頂點(diǎn)V1出發(fā)),集合Q的初值為 。Prime算法的思想是,從所有p P,vV-P的邊中,選取具有最小權(quán)值的邊pv,將頂點(diǎn)v加入集合P中,將邊pv 加入集合Q中,如此不斷重復(fù),直到P=V時(shí),最小生成樹(shù)構(gòu)造完畢,這時(shí)集合Q中包含了最小生成的所有邊。(找最小的權(quán),不連成圈即可) clc;clear; M=1000; 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(
2、4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70; a=a;zeros(2,7); a=a+a;a(find(a=0)=M; 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 例 、一個(gè)鄉(xiāng)有7個(gè)自然村,其間道路如圖所示,要
3、以村為中心建有線廣播網(wǎng)絡(luò),如要求沿道路架設(shè)廣播線,應(yīng)如何架設(shè)?1 / 9Kruskal算法 每步從未選的邊中選取邊e,使它與已選邊不構(gòu)成圈,且e是未選邊中的最小權(quán)邊,直到選夠n-1條邊為止。 clc;clear; M=1000; 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; i,j=find(a=0)&(a=M); b=a(find(a=0)&(a=M); data=i;j;b;index=data(1:2,:); loop=
4、max(size(a)-1; result=; while length(result)v2 index(find(index=v1)=v2; else index(find(index=v2)=v1; end data(:,flag)=; index(:,flag)=; end result中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題也可以表示為:在一個(gè)有奇點(diǎn)的連通圖中。要求增加一些重復(fù)邊,使得新的連通圖不含有奇點(diǎn),并且增加的重復(fù)邊總權(quán)最小。我們把增加重復(fù)邊后不含奇點(diǎn)的新的連通圖叫做郵遞路線,而總權(quán)最小的郵遞路線叫做最優(yōu)郵遞路線。求圖中所示的中國(guó)郵遞員問(wèn)題 Fleury算法(在一個(gè)Euler圖中找出Eule
5、r環(huán)游) 注:包括三個(gè)文件;fleuf1.m, edf.m, flecvexf.m function T c=fleuf1(d) %注:必須保證是Euler環(huán)游,否則輸出T=0,c=0 n=length(d); b=d; b(b=inf)=0; b(b=0)=1; m=0; a=sum(b); eds=sum(a)/2; ed=zeros(2,eds); vexs=zeros(1,eds+1); matr=b; for i=1:n if mod(a(i),2)=1 m=m+1; end end if m=0 fprintf(there is not exit Euler path.n) T=0
6、;c=0; end if m=0 vet=1; flag=0; t1=find(matr(vet,:)=1); for ii=1:length(t1) ed(:,1)=vet,t1(ii); vexs(1,1)=vet;vexs(1,2)=t1(ii); matr(vexs(1,2),vexs(1,1)=0; flagg=1;tem=1; while flagg flagg ed=edf(matr,eds,vexs,ed,tem); tem=tem+1; if ed(1,eds)=0 & ed(2,eds)=0 T=ed; T(2,eds)=1; c=0; for g=1:eds c=c+d(
7、T(1,g),T(2,g); end flagg=0; break; end end end end functionflag ed=edf(matr,eds,vexs,ed,tem) flag=1; for i=2:eds dvex f=flecvexf(matr,i,vexs,eds,ed,tem); if f=1 flag=0; break; end if dvex=0 ed(:,i)=vexs(1,i) dvex; vexs(1,i+1)=dvex; matr(vexs(1,i+1),vexs(1,i)=0; else break; end end function dvex f=fl
8、ecvexf(matr,i,vexs,eds,ed,temp) f=0; edd=find(matr(vexs(1,i),:)=1); dvex=0; dvex1=; ded=; if length(edd)=1 dvex=edd; else dd=1;dd1=0;kkk=0; for kk=1:length(edd) m1=find(vexs=edd(kk); if sum(m1)=0 dvex1(dd)=edd(kk); dd=dd+1; dd1=1; else kkk=kkk+1; end end if kkk=length(edd) tem=vexs(1,i)*ones(1,kkk);
9、 edd1=tem;edd; for l1=1:kkk lt=0;ddd=1; for l2=1:eds if edd1(1:2,l1)=ed(1:2,l2) lt=lt+1; end end if lt=0 ded(ddd)=edd(l1); ddd=ddd+1; end end end if templength(dvex1) & temp0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1). a(c1(m),c1(m+1)+a(c1(n),c1
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025屆四川省成都實(shí)驗(yàn)高級(jí)中學(xué)化學(xué)高一下期末統(tǒng)考模擬試題含解析
- 杭州禽類交易管理辦法
- 發(fā)票管理辦法開(kāi)具發(fā)票
- 村鎮(zhèn)規(guī)劃果園管理辦法
- 區(qū)域醫(yī)師注冊(cè)管理辦法
- 核算崗位電價(jià)管理辦法
- 小區(qū)物業(yè)管理制度監(jiān)督考核方案
- 紫蘇生長(zhǎng)與土壤微生物互作機(jī)制:有機(jī)無(wú)機(jī)肥配施效應(yīng)
- 北京教委賽事管理辦法
- 沉浸式劇本殺管理辦法
- 2024起重吊裝及起重機(jī)械安裝拆卸工程監(jiān)理作業(yè)指引
- 威脅情報(bào)收集與整合-洞察分析
- 期末教師會(huì)議校長(zhǎng)精彩講話:最后講了存在的問(wèn)題
- 知名連鎖漢堡店食安QSC稽核表
- 攝影設(shè)備采購(gòu)合同范例
- DB41T 1812-2019 蘋果簡(jiǎn)約栽培技術(shù)規(guī)程
- 【《三只松鼠公司員工激勵(lì)現(xiàn)狀調(diào)查及優(yōu)化建議(附問(wèn)卷)14000字》(論文)】
- 護(hù)理不良事件登記本及護(hù)理不良事件報(bào)告新規(guī)制度
- 農(nóng)業(yè)土壤檢測(cè)技術(shù)行業(yè)發(fā)展前景及投資風(fēng)險(xiǎn)預(yù)測(cè)分析報(bào)告
- 廣東省深圳市羅湖區(qū)2023-2024學(xué)年二年級(jí)下學(xué)期期末考試數(shù)學(xué)試題
- 長(zhǎng)沙新華書(shū)店面試題目
評(píng)論
0/150
提交評(píng)論