數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-最短路徑

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