數(shù)據(jù)結(jié)構(gòu)實驗報告-最短路徑

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

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

3、的距離，我們才需要進(jìn)行更新）其中N為圖中結(jié)點的個數(shù)。數(shù)組distanceN：此數(shù)組記錄圖中的點到源點的距離。這個數(shù)組里面存放的值是不斷進(jìn)行更新的。其中N為圖中結(jié)點的個數(shù)。3、程序簡單模板只是參考，不需要照著這個來寫/最短路徑#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;三 、實驗代碼#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;/頂點數(shù)組 int nodenum;/經(jīng)過的頂點數(shù);class Mgraph/鄰接矩陣儲存結(jié)構(gòu)public: Mgraph() Mgraph() void CreatMGraph(); void DFS (int

6、 );/用遞歸實現(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;/頂點數(shù)目 int arcnum;/邊的數(shù)目 char vexs50; int arcs5050; int visited50;/便利時的輔助工具 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<<"頂點為： " 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()/圖的鄰接矩陣儲存結(jié)構(gòu) char vex1,vex2; int i,j,k,m; cout<<"請輸入定點數(shù)，邊數(shù)："<<endl; cin>>

9、;number>>arcnum; cout<<"請輸入頂點（字符串類型）："<<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<<"請輸入邊的兩個頂點及邊的權(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)/用遞歸實現(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<<"請輸入起始頂點："<<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;/每一個頂點屬于一顆樹 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<<"請輸入起始點"<<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)過的頂點為："<<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