有向圖的路徑輸出_第1頁
有向圖的路徑輸出_第2頁
有向圖的路徑輸出_第3頁
有向圖的路徑輸出_第4頁
有向圖的路徑輸出_第5頁
已閱讀5頁,還剩8頁未讀, 繼續(xù)免費閱讀

下載本文檔

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

文檔簡介

1、實驗報告(一) 有向圖的路徑問題1. 結(jié)構(gòu)體 typedef struct ArcNodeint adjvex; /地點序號char data;int weight; /權(quán)重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地點名 ArcNode *firstarc;VNode,AdjListMVNum;typedef structAdjList vertices;int vexnum; /地點數(shù)量int arcnum; /邊數(shù)ALGraph;2. 函數(shù)int LocateVex( ALGraph G,char ve

2、x) /找到地點對應序號void Insert_vex( ALGraph &G , int i, int vex) /插入頂點void Insert_arc( ALGraph &G ,char v1,char v2,int weight) /插入信息/創(chuàng)建有向圖void CreatALGraph ( ALGraph &G )/Floyd算法void Floyd( ALGraph &G ,int TMVNumMVNum,int pathMVNumMVNum)void Find( ALGraph G ,int TMVNumMVNum,int pathMVNumMVN

3、um)3. 截圖4. 實驗心得重點是Floydy算法總體不難,做多了也就簡單了。5. 源代碼 #include "iostream"#include "string"using namespace std;#define MaxInt 32767#define MVNum 100typedef struct ArcNodeint adjvex; /地點序號char data;int weight; /權(quán)重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地點名 ArcNode

4、*firstarc;VNode,AdjListMVNum;typedef structAdjList vertices;int vexnum; /地點數(shù)量int arcnum; /邊數(shù)ALGraph;int LocateVex( ALGraph G,char vex) /找到地點對應序號for( int i = 0; i <G.vexnum ;i+ )if( G.verticesi.data = vex )return i;void Insert_vex( ALGraph &G , int i, int vex) /插入頂點G.verticesi.data = vex;G.ver

5、ticesi.firstarc = NULL;void Insert_arc( ALGraph &G ,char v1,char v2,int weight) /插入信息ArcNode *p1;p1 = new ArcNode;int i,j;i = LocateVex(G,v1);j = LocateVex(G,v2);p1->adjvex = j; /頂點序號p1->data = G.verticesj.data; /頂點p1->weight = weight; /權(quán)值p1->nextarc = G.verticesi.firstarc; G.vertice

6、si.firstarc = p1;/創(chuàng)建有向圖void CreatALGraph ( ALGraph &G )G.vexnum = 6;G.arcnum = 8;/信息初始化Insert_vex( G,0,'A');Insert_vex( G,1,'B');Insert_vex( G,2,'C');Insert_vex( G,3,'D');Insert_vex( G,4,'E');Insert_vex( G,5,'F'); /頂點1,頂點2,權(quán)值Insert_arc( G,'A

7、9;,'C',10);Insert_arc( G,'A','E',30);Insert_arc( G,'A','F',100);Insert_arc( G,'B','C',5);Insert_arc( G,'C','D',50);Insert_arc( G,'D','F',10);Insert_arc( G,'E','D',20);Insert_arc( G,'E',

8、9;F',60);/輸出信息for( int i = 0; i <G.vexnum; i + )ArcNode *p1;p1 = G.verticesi.firstarc;while(p1)cout<<G.verticesi.data<<"t"<<p1->data<<"t"<<p1->weight<<endl;p1 = p1->nextarc;cout<<endl;/Floyd算法void Floyd( ALGraph &G ,in

9、t TMVNumMVNum,int pathMVNumMVNum)/初始化默認值for(int m = 0; m < G.vexnum ; m +)for(int n = 0;n < G.vexnum; n +)Tmn = MaxInt;pathmn = -1;/初始化賦值for( int i = 0; i < G.vexnum ; i +)ArcNode *p;p = G.verticesi.firstarc;while(p)Tip->adjvex = p->weight;pathip->adjvex = i;p = p->nextarc;for(i

10、nt k = 0;k < G.vexnum; k+)for(i = 0;i < G.vexnum ; i+)for( int j =0; j < G.vexnum; j +)if( Tik+Tkj < Tij )Tij = Tik+Tkj;pathij = pathkj; /j的前驅(qū)變?yōu)閗void Find( ALGraph G ,int TMVNumMVNum,int pathMVNumMVNum)char v1,v2;cout<<endl<<"請輸入要查詢的兩個點:"cin>>v1>>v2;int

11、i,j;i = LocateVex(G,v1);j = LocateVex(G,v2);/輸出最短時間并 循環(huán)查找前驅(qū)int t = j;if(pathit != -1 && i != t)cout<<v1<<" "<<v2<<" 有路徑!"<<endl;else cout<<v1<<" "<<v2<<" 沒有路徑!"<<endl;int main()ALGraph G;Creat

12、ALGraph( G );int TMVNum MVNum ;int pathMVNumMVNum ;Floyd(G,T,path);cout<<endl;doFind(G,T,path);cout<<endl<<"continue? Y/N"char select;cin>>select;if(select = 'n' | select = 'N')break;while(1);return 0;(二) 有向圖的路徑問題1. 結(jié)構(gòu)體typedef struct ArcNodeint adjve

13、x; /地點序號char data;double money; /權(quán)重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地點名 ArcNode *firstarc;VNode,AdjListMVNum;typedef structAdjList vertices;int vexnum; /地點數(shù)量int arcnum; /邊數(shù)ALGraph;2. 函數(shù) int LocateVex( ALGraph G,char vex) /找到地點對應序號void Insert_vex( ALGraph &G , int i

14、, int vex) /插入頂點void Insert_arc( ALGraph &G ,char v1,char v2,int weight) /插入信息/創(chuàng)建有向圖void CreatALGraph ( ALGraph &G )/Floyd算法void Floyd( ALGraph &G ,int TMVNumMVNum,int pathMVNumMVNum)void Find( ALGraph G ,int TMVNumMVNum,int pathMVNumMVNum)3. 截圖4. 實驗心得實驗不難。重點是輸出最短路徑的算法。5. 源代碼#include &qu

15、ot;iostream"#include "string"using namespace std;#define MaxInt 32767#define MVNum 100typedef struct ArcNodeint adjvex; /地點序號char data;double money; /權(quán)重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地點名 ArcNode *firstarc;VNode,AdjListMVNum;typedef structAdjList vertic

16、es;int vexnum; /地點數(shù)量int arcnum; /邊數(shù)ALGraph;int LocateVex( ALGraph G,char vex) /找到地點對應序號for( int i = 0; i <G.vexnum ;i+ )if( G.verticesi.data = vex )return i;void Insert_vex( ALGraph &G , int i, int vex) /插入頂點G.verticesi.data = vex;G.verticesi.firstarc = NULL;void Insert_arc( ALGraph &G ,c

17、har v1,char v2,double money) /插入信息ArcNode *p1;p1 = new ArcNode;int i,j;i = LocateVex(G,v1);j = LocateVex(G,v2);p1->adjvex = j; /頂點序號p1->data = G.verticesj.data; /頂點p1->money = money; /權(quán)值p1->nextarc = G.verticesi.firstarc; G.verticesi.firstarc = p1;/創(chuàng)建有向圖void CreatALGraph ( ALGraph &G

18、 )G.vexnum = 6;G.arcnum = 8;/信息初始化Insert_vex( G,0,'A');Insert_vex( G,1,'B');Insert_vex( G,2,'C');Insert_vex( G,3,'D');Insert_vex( G,4,'E');Insert_vex( G,5,'F'); /頂點1,頂點2,權(quán)值Insert_arc( G,'A','C',1);Insert_arc( G,'A','E',3

19、);Insert_arc( G,'A','F',10);Insert_arc( G,'B','C',0.5);Insert_arc( G,'C','D',5);Insert_arc( G,'D','F',1);Insert_arc( G,'E','D',2);Insert_arc( G,'E','F',6);/輸出信息for( int i = 0; i <G.vexnum; i + )ArcNode

20、 *p1;p1 = G.verticesi.firstarc;while(p1)cout<<G.verticesi.data<<"t"<<p1->data<<"t"<<p1->money<<endl;p1 = p1->nextarc;cout<<endl;/Floyd算法void Floyd( ALGraph &G ,int TMVNumMVNum,int pathMVNumMVNum)/初始化默認值for(int m = 0; m < G

21、.vexnum ; m +)for(int n = 0;n < G.vexnum; n +)Tmn = MaxInt;pathmn = -1;/初始化賦值for( int i = 0; i < G.vexnum ; i +)ArcNode *p;p = G.verticesi.firstarc;while(p)Tip->adjvex = p->money;pathip->adjvex = i;p = p->nextarc;for(int k = 0;k < G.vexnum; k+)for(i = 0;i < G.vexnum ; i+)for(

22、 int j =0; j < G.vexnum; j +)if( Tik+Tkj < Tij )Tij = Tik+Tkj;pathij = pathkj; /j的前驅(qū)變?yōu)閗void Find( ALGraph G ,int TMVNumMVNum,int pathMVNumMVNum)char v1,v2;cout<<endl<<"請輸入要查詢的兩個點:"cin>>v1>>v2;int i,j;i = LocateVex(G,v1);j = LocateVex(G,v2);/輸出最短時間并 循環(huán)查找前驅(qū)int t = j;if(pathit != -1 && i != t)cout<<G.verticesi.data<<&qu

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論