有向圖的路徑輸出

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

2、x) /找到地點(diǎn)對(duì)應(yīng)序號(hào)void Insert_vex( ALGraph &G , int i, int vex) /插入頂點(diǎn)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. 實(shí)驗(yàn)心得重點(diǎn)是Floydy算法總體不難，做多了也就簡(jiǎn)單了。5. 源代碼 #include "iostream"#include "string"using namespace std;#define MaxInt 32767#define MVNum 100typedef struct ArcNodeint adjvex; /地點(diǎn)序號(hào)char data;int weight; /權(quán)重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地點(diǎn)名 ArcNode

4、*firstarc;VNode,AdjListMVNum;typedef structAdjList vertices;int vexnum; /地點(diǎn)數(shù)量int arcnum; /邊數(shù)ALGraph;int LocateVex( ALGraph G,char vex) /找到地點(diǎn)對(duì)應(yīng)序號(hào)for( int i = 0; i <G.vexnum ;i+ )if( G.verticesi.data = vex )return i;void Insert_vex( ALGraph &G , int i, int vex) /插入頂點(diǎn)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; /頂點(diǎn)序號(hào)p1->data = G.verticesj.data; /頂點(diǎn)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'); /頂點(diǎn)1，頂點(diǎn)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)/初始化默認(rèn)值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<<"請(qǐng)輸入要查詢的兩個(gè)點(diǎn):"cin>>v1>>v2;int

11、i,j;i = LocateVex(G,v1);j = LocateVex(G,v2);/輸出最短時(shí)間并 循環(huán)查找前驅(qū)int t = j;if(pathit != -1 && i != t)cout<<v1<<" "<<v2<<" 有路徑!"<<endl;else cout<<v1<<" "<<v2<<" 沒(méi)有路徑!"<<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;(二) 有向圖的路徑問(wèn)題1. 結(jié)構(gòu)體typedef struct ArcNodeint adjve

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

14、, int vex) /插入頂點(diǎn)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. 實(shí)驗(yàn)心得實(shí)驗(yàn)不難。重點(diǎn)是輸出最短路徑的算法。5. 源代碼#include &qu

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

16、es;int vexnum; /地點(diǎn)數(shù)量int arcnum; /邊數(shù)ALGraph;int LocateVex( ALGraph G,char vex) /找到地點(diǎn)對(duì)應(yīng)序號(hào)for( int i = 0; i <G.vexnum ;i+ )if( G.verticesi.data = vex )return i;void Insert_vex( ALGraph &G , int i, int vex) /插入頂點(diǎn)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; /頂點(diǎn)序號(hào)p1->data = G.verticesj.data; /頂點(diǎn)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'); /頂點(diǎn)1，頂點(diǎn)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)/初始化默認(rèn)值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<<"請(qǐng)輸入要查詢的兩個(gè)點(diǎn):"cin>>v1>>v2;int i,j;i = LocateVex(G,v1);j = LocateVex(G,v2);/輸出最短時(shí)間并 循環(huán)查找前驅(qū)int t = j;if(pathit != -1 && i != t)cout<<G.verticesi.data<<&qu