數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-最短路徑_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-最短路徑_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-最短路徑_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-最短路徑_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-最短路徑_第5頁(yè)
已閱讀5頁(yè),還剩7頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、實(shí) 驗(yàn) 報(bào) 告 實(shí)驗(yàn)名稱 最短路徑 課程名稱 數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn) | 專業(yè)班級(jí):信息安全 學(xué) 號(hào): 姓 名:實(shí)驗(yàn)六 最短路徑一、實(shí)驗(yàn)?zāi)康?.學(xué)習(xí)掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)2.學(xué)會(huì)編寫求最短路徑的算法二、實(shí)驗(yàn)內(nèi)容1、實(shí)驗(yàn)題目編寫代碼實(shí)現(xiàn)Dijkstra生成最短路徑的算法,其中要有完整的圖的輸入輸出2、簡(jiǎn)單介紹圖的存儲(chǔ):用鄰接矩陣,這樣會(huì)方便不少。鄰接矩陣是一個(gè)二維數(shù)組,數(shù)組中的元素是邊的權(quán)(一些數(shù)值),數(shù)組下標(biāo)號(hào)為結(jié)點(diǎn)的標(biāo)號(hào)。(1)例如二維數(shù)組中的一個(gè)元素M56的值為39,則表示結(jié)點(diǎn)5、6連接,且其上的權(quán)值為39。(2)用鄰接矩陣存儲(chǔ)圖,對(duì)圖的讀寫就簡(jiǎn)單了。因?yàn)猷徑泳仃嚲褪且粋€(gè)二維數(shù)組,因此對(duì)圖的讀寫就是

2、對(duì)二維數(shù)組的操作。只要能弄清楚邊的編號(hào),就能把圖讀入了。用一對(duì)結(jié)點(diǎn)表示邊(也就是輸入的時(shí)候輸入一對(duì)結(jié)點(diǎn)的編號(hào))求最短路徑的算法:求最短路徑就是求圖中的每一個(gè)點(diǎn)到圖中某一個(gè)給定點(diǎn)(這里認(rèn)為是編號(hào)為0的點(diǎn))的最短距離。具體算法就是初始有一個(gè)舊圖,一個(gè)新圖。開始的時(shí)候舊圖中有所有的結(jié)點(diǎn),新圖中初始為只有一個(gè)結(jié)點(diǎn)(源點(diǎn),路徑的源頭)。整個(gè)算法就是不停的從舊圖中往新圖中添加點(diǎn),直到所有的點(diǎn)都添加到新圖中為止。要實(shí)現(xiàn)這個(gè)算法,除了用二維數(shù)組保存圖,還需要使用到兩個(gè)輔助的數(shù)組數(shù)組findN:此數(shù)組是用來(lái)表示標(biāo)號(hào)對(duì)應(yīng)的結(jié)點(diǎn)是否已經(jīng)被添加到新圖中(因?yàn)橹挥信f圖中的點(diǎn)我們才需要添加到新圖中,并且只有舊圖中點(diǎn)到源點(diǎn)

3、的距離,我們才需要進(jìn)行更新)其中N為圖中結(jié)點(diǎn)的個(gè)數(shù)。數(shù)組distanceN:此數(shù)組記錄圖中的點(diǎn)到源點(diǎn)的距離。這個(gè)數(shù)組里面存放的值是不斷進(jìn)行更新的。其中N為圖中結(jié)點(diǎn)的個(gè)數(shù)。3、程序簡(jiǎn)單模板只是參考,不需要照著這個(gè)來(lái)寫/最短路徑#ifndef MYGRAPH_H_#define MYGRAPH_H_class MyGraphpublic:void readDirectedGraph();MyGraph(int size);/構(gòu)造函數(shù)中設(shè)置圖的大小,分配空間void writeGraph();void shortPath(int source);/求最短路徑protected:private:int

4、 *m_graph;/用二維數(shù)組保存圖int m_size;/圖的大小;#endif/ /構(gòu)造函數(shù)中設(shè)置圖的大小,分配空間MyGraph:MyGraph(int size)int i,j;m_size=size;/給圖分配空間m_graph=new int* m_size;for (i=0;i<m_size;i+)m_graphi=new intm_size;for (i=0;i<m_size;i+)for(j=0;j<m_size;j+)m_graphij=INT_MAX;三 、實(shí)驗(yàn)代碼#include<iostream>#include <iomanip

5、>#include <stack>#include <deque>#include <fstream>using namespace std;struct primnodepublic: char begvex; char endvex; int lowcost;struct adknode int dist;/最近距離 char way50;/頂點(diǎn)數(shù)組 int nodenum;/經(jīng)過的頂點(diǎn)數(shù);class Mgraph/鄰接矩陣儲(chǔ)存結(jié)構(gòu)public: Mgraph() Mgraph() void CreatMGraph(); void DFS (int

6、 );/用遞歸實(shí)現(xiàn) void DFS1(int );/非遞歸 void BFS(int ); void print(); void prim(); int mini(); int low();/最短距離函數(shù)的輔助函數(shù) int LocateVex(char); void kruskal(); void Dijkstra(); void Floyd();private: int number;/頂點(diǎn)數(shù)目 int arcnum;/邊的數(shù)目 char vexs50; int arcs5050; int visited50;/便利時(shí)的輔助工具 primnode closeedge50;/prim adk

7、node dist50;/最短路徑 int D2020;/floyd算法距離 int P202020;/floyd算法路徑; int Mgraph:LocateVex(char s) for(int i=0;i<number;i+) if (vexsi=s) return i; return -1;void Mgraph:print() cout<<"頂點(diǎn)為: " for(int k=0;k<number;k+) cout<<vexsk; cout<<endl; for(int i=0;i<number;i+) for(

8、int j=0;j<number;j+) cout<<setw(6)<<left<<arcsij<<" " cout<<endl; for(int m=0;m<number;m+) cout<<visitedm; cout<<endl;void Mgraph:CreatMGraph()/圖的鄰接矩陣儲(chǔ)存結(jié)構(gòu) char vex1,vex2; int i,j,k,m; cout<<"請(qǐng)輸入定點(diǎn)數(shù),邊數(shù):"<<endl; cin>>

9、;number>>arcnum; cout<<"請(qǐng)輸入頂點(diǎn)(字符串類型):"<<endl; for(i=0;i<number;i+) cin>>vexsi; for(i=0;i<number;i+) for(j=0;j<number;j+) arcsij=1000; for(k=0;k<arcnum;k+) cout<<"請(qǐng)輸入邊的兩個(gè)頂點(diǎn)及邊的權(quán)值: "<<endl; cin>>vex1>>vex2>>m; i=Locat

10、eVex(vex1); j=LocateVex(vex2); arcsij=m; arcsji=m; void Mgraph:DFS(int i=0)/用遞歸實(shí)現(xiàn) int j; cout<<vexsi<<"->" visitedi=1; for (j=0;j<number;j+) if(!(arcsij=1000)&&!visitedj) DFS(j); void Mgraph:DFS1(int i=0)/非遞歸 stack<int> st; st.push(i); while(!st.empty() int

11、j=st.top(); st.pop(); cout<<vexsj<<"->" visitedj=1; for(int k=0;k<number;k+) if(!(arcsjk=1000)&&!visitedk) st.push(k); void Mgraph:BFS(int i=0)/廣度優(yōu)先遍歷 deque<int> de; de.push_back(i); cout<<vexsi<<"->" visitedi=1; while(!de.empty() in

12、t k=de.front(); for(int j=0;j<number;j+) if(arcskj!=1000&&!visitedj) cout<<vexsj<<"->" visitedj=1; de.push_back(j); de.pop_front(); int Mgraph:mini() static int i; int min=0; for (int j=0;j<number;j+) if(!visitedj) if (closeedgemin.lowcost>closeedgej.lowcost

13、) min=j; i=min; cout<<"包括邊("<<closeedgei.begvex<<","<<closeedgei.endvex<<")" return i;void Mgraph:prim() char u; cout<<"請(qǐng)輸入起始頂點(diǎn):"<<endl; cin>>u; int i=LocateVex(u); visitedi=1; for(int j=0;j<number;j+) closeed

14、gej.begvex=u; closeedgej.endvex=vexsj; closeedgej.lowcost=arcsij; for (int m=1;m<number;m+) int n=mini(); visitedn=1; closeedgen.lowcost=1000; for (int p=0;p<number;p+) if(!visitedp) if(arcspn<closeedgep.lowcost) closeedgep.lowcost=arcspn; closeedgep.begvex=vexsn; void Mgraph:kruskal() int

15、a,b,k=0; int min=1000; int arcs12020; for (int m=0;m<number;m+) visitedm=m;/每一個(gè)頂點(diǎn)屬于一顆樹 for (int i=0;i<number;i+) for(int j=0;j<number;j+) arcs1ij=arcsij; while (k<number-1) min=1000; for (int i=0;i<number;i+) for (int j=0;j<number;j+) if (arcs1ij<min) a=i; b=j; min=arcs1ij; if (

16、visiteda!=visitedb) cout<<"包括邊("<<vexsa<<","<<vexsb<<")" k+; for (int n=0;n<number;n+) if (visitedn=visitedb) visitedn=visiteda; else arcs1ab=arcsba=1000; void Mgraph:Dijkstra() cout<<"請(qǐng)輸入起始點(diǎn)"<<endl; char u; cin>

17、>u; int i=LocateVex(u); visitedi=1; for (int j=0;j<number;j+) distj.dist=arcsij; distj.nodenum=0; for (j=1;j<number;j+) int distance=1000; int min=0; for (int n=0;n<number;n+) if(!visitedn) if (distance>distn.dist) distance=distn.dist; min=n; int m=min; visitedm=1; for (n=0;n<numbe

18、r;n+) if(!visitedn) if(distm.dist+arcsmn)<distn.dist) distn.dist=distm.dist+arcsmn; distn.nodenum=0; for (int x=0;x<distm.nodenum;x+) distn.wayx=distm.wayx; distn.nodenum+; distn.waydistn.nodenum+=vexsm; /輸出功能 for (int n=0;n<number;n+) if (n!=i) if(distn.dist<1000) cout<<vexsi<&

19、lt;"到"<<vexsn<<"的最近距離為:"<<distn.dist<<endl; cout<<"經(jīng)過的頂點(diǎn)為:"<<vexsi<<"->" for (int p=0;p<distn.nodenum;p+) cout<<distn.wayp<<"->" cout<<vexsn<<endl; else cout<<vexsi<&

20、lt;"到"<<vexsn<<"沒有通路"<<endl; void Mgraph:Floyd() int i,j,m,n; for ( i=0;i<number;i+) for ( j=0;j<number;j+) for (m=0;m<number;m+) Pijm=0; for ( i=0;i<number;i+) for ( j=0;j<number;j+) Dij=arcsij; if(Dij<1000) Piji=1; Pijj=1; for ( i=0;i<number;i+) for ( j=0;j<number;j

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝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ù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 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ì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論