有向图的路径输出

1、实验报告(一) 有向图的路径问题1. 结构体 typedef struct ArcNodeint adjvex; /地点序号char data;int weight; /权重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地点名 ArcNode *firstarc;VNode,AdjListMVNum;typedef structAdjList vertices;int vexnum; /地点数量int arcnum; /边数ALGraph;2. 函数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) /插入信息/创建有向图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; /权重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地点名 ArcNode

4、*firstarc;VNode,AdjListMVNum;typedef structAdjList vertices;int vexnum; /地点数量int arcnum; /边数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; /权值p1->nextarc = G.verticesi.firstarc; G.vertice

6、si.firstarc = p1;/创建有向图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，权值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的前驱变为kvoid 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);/输出最短时间并 循环查找前驱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. 结构体typedef struct ArcNodeint adjve

13、x; /地点序号char data;double money; /权重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地点名 ArcNode *firstarc;VNode,AdjListMVNum;typedef structAdjList vertices;int vexnum; /地点数量int arcnum; /边数ALGraph;2. 函数 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) /插入信息/创建有向图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; /权重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地点名 ArcNode *firstarc;VNode,AdjListMVNum;typedef structAdjList vertic

16、es;int vexnum; /地点数量int arcnum; /边数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; /权值p1->nextarc = G.verticesi.firstarc; G.verticesi.firstarc = p1;/创建有向图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，权值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的前驱变为kvoid 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);/输出最短时间并 循环查找前驱int t = j;if(pathit != -1 && i != t)cout<<G.verticesi.data<<&qu