实验五 图(to student).docx

实验五 图一、实验目的1. 掌握图的基本存储方法； 2. 掌握有关图的操作算法并用高级语言实现； 3. 熟练掌握图的两种搜索路径的遍历方法。二、实验内容假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。三、实验步骤1. 定义结点结构，定义图结构。2.存储图信息；3. 定义求任意两点最短路径函数；4. 写出主函数。四、实现提示typedef struct node int no; float wgt; struct node *next; edgenode; typedef struct char vtx; edgenode *link; vexnode; typedef vexnode Graphn; void Floyd(Graph G, float Ann, int pnn) int i, j, k; for (i=0; in; i+) for(j=0;jn;j+) Aij=Gij; Pij=-1; for (k=0; kn; k+) for (i=0; in; i+) for (j=0; jn; j+) if(Aik +AkjAij) Pij=k; Aij=Aik+Akj; 五、思考与提高（直接将答案写在小题后面）1. 判断两点是否可达。2.如何对程序进行修改，找一条人最少的公交线路？3.练习图的拓扑排序六、调试以下参考程序代码，并将运行效果截图1.图的建立与遍历#include #include #include #include #define MAX_VERTEX_NUM 20 /图的最大顶点数#define MAXQSIZE 30 /队列的最大容量 enum BOOL False,True;typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置 struct ArcNode *nextarc; /指向下一条弧的指针ArcNode; /弧结点typedef structArcNode* AdjListMAX_VERTEX_NUM; /指向第一条依附该顶点的弧的指针 int vexnum,arcnum; /图的当前顶点和弧数 int GraphKind; /图的种类，0-无向图，1-有向图Graph; typedef struct /队列结构int elemMAXQSIZE; /数据域 int front; /队头指针 int rear; /队尾指针SqQueue; BOOL visitedMAX_VERTEX_NUM; /全局变量访问标志数组void CreateGraph(Graph &); /生成图的邻接表void DFSTraverse(Graph); /深度优先搜索遍历图void DFS(Graph,int); void BFSTraverse(Graph); /广度优先搜索遍历图void Initial(SqQueue &); /初始化一个队列BOOL QueueEmpty(SqQueue); /判断队列是否空BOOL EnQueue(SqQueue &,int); /将一个元素入队列BOOL DeQueue(SqQueue &,int &); /将一个元素出队列int FirstAdjVex(Graph,int); /求图中某一顶点的第一个邻接顶点int NextAdjVex(Graph,int,int); /求某一顶点的下一个邻接顶点void main()Graph G; /采用邻接表结构的图 char j=y;printf(本程序将演示生成一个图，并对它进行遍历.n); printf(首先输入要生成的图的种类.n); printf(0-无向图, 1-有向图n); printf(之后输入图的顶点数和弧数。n格式：顶点数，弧数；例如:4,3n); printf(接着输入各边(弧尾，弧头).n例如:n1,2n1,3n2,4n); printf(程序会生成一个图，并对它进行深度和广度遍历.n); printf(深度遍历:1-2-4-3n广度遍历:1-2-3-4n);while(j!=N&j!=n) printf(请输入要生成的图的种类(0/1):); scanf(%d,&G.GraphKind); /输入图的种类 printf(请输入顶点数和弧数：); scanf(%d,%d,&G.vexnum,&G.arcnum); /输入图的顶点数和弧数 CreateGraph(G); /生成邻接表结构的图 DFSTraverse(G); /深度优先搜索遍历图 BFSTraverse(G); /广度优先搜索遍历图 printf(图遍历完毕，继续进行吗?(Y/N); scanf( %c,&j); void CreateGraph(Graph &G)/构造邻接表结构的图G int i; int start,end; ArcNode *s; for(i=1;i=G.vexnum;i+) G.AdjListi=NULL; /初始化指针数组 for(i=1;inextarc=G.AdjListstart; /插入到邻接表中 s-adjvex=end; G.AdjListstart=s; if(G.GraphKind=0) /若是无向图，再插入到终点的弧链中 s=(ArcNode *)malloc(sizeof(ArcNode);s-nextarc=G.AdjListend;s-adjvex=start;G.AdjListend=s; void DFSTraverse(Graph G)/深度优先遍历图G int i; printf(DFSTraverse:); for(i=1;i=G.vexnum;i+) visitedi=False; /访问标志数组初始化 for(i=1;i,i); for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w) if(!visitedw) DFS(G,w); /对尚未访问的邻接顶点w调用DFSvoid BFSTraverse(Graph G)/按广度优先非递归的遍历图G，使用辅助队列Q和访问标志数组visited int i,u,w; SqQueue Q; printf(BFSTreverse:); for(i=1;i= G.vexnum;i+) visitedi=False; /访问标志数组初始化 Initial(Q); /初始化队列 for(i=1;i,i); EnQueue(Q,i); /将序号i入队列 while(!QueueEmpty(Q) /若队列不空，继续 DeQueue(Q,u); /将队头元素出队列并置为ufor(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w) if(!visitedw) /对u的尚未访问的邻接顶点w进行访问并入队列 visitedw=True; printf(%d-,w); EnQueue(Q,w); printf(bb n);int FirstAdjVex(Graph G,int v)/在图G中寻找第v个顶点的第一个邻接顶点 if(!G.AdjListv) return 0; else return(G.AdjListv-adjvex);int NextAdjVex(Graph G,int v,int u)/在图G中寻找第v个顶点的相对于u的下一个邻接顶点 ArcNode *p; p=G.AdjListv; while(p-adjvex!=u) p=p-nextarc; /在顶点v的弧链中找到顶点u if(p-nextarc=NULL) return 0; /若已是最后一个顶点，返回0 else return(p-nextarc-adjvex); /返回下一个邻接顶点的序号void Initial(SqQueue &Q) /队列初始化 Q.front=Q.rear=0; BOOL QueueEmpty(SqQueue Q)/判断队列是否已空，若空返回True,否则返回False if(Q.front=Q.rear) return True; else return False;BOOL EnQueue(SqQueue &Q,int ch)/入队列，成功返回True，失败返回False if(Q.rear+1)%MAXQSIZE=Q.front) return False; Q.elemQ.rear=ch; Q.rear=(Q.rear+1)%MAXQSIZE; return True;BOOL DeQueue(SqQueue &Q,int &ch)/出队列,成功返回True，并用ch返回该元素值，失败返回False if(Q.front=Q.rear) return False; ch=Q.elemQ.front; Q.front=(Q.front+1)%MAXQSIZE; return True; /成功出队列，返回True2.最短路径-迪杰斯特拉算法#include #include #include #include #define INFINITY 30000 /定义一个权值的最大值#define MAX_VERTEX_NUM 20 /图的最大顶点数enum BOOL False,True;typedef structint arcsMAX_VERTEX_NUMMAX_VERTEX_NUM; /邻接矩阵 int vexnum,arcnum; /图的当前顶点和边数Graph;void CreateGraph(Graph &); /生成图的邻接矩阵void ShortestPath_DiJ(Graph,int,intMAX_VERTEX_NUM,int); /用迪杰斯特拉算法求从某一源点到其余顶点的最短路径void Print_ShortestPath(Graph,int,intMAX_VERTEX_NUM,int); /显示最短路径void main()Graph G; /采用邻接矩阵结构的图 char j=y; int u; int PMAX_VERTEX_NUMMAX_VERTEX_NUM; /存放从源点到各顶点的最短路径 int DMAX_VERTEX_NUM; /存放从源点到各顶点的最短路径的距离printf(本程序将演示利用迪杰斯特拉算法求n从图的一点到其余顶点的最短路径.n); printf(首先输入图的顶点数和弧数.n格式：顶点数，弧数；例如:5,7n); printf(然后输入各弧和权值.n格式：弧尾，弧头，权值；例如:n1,2,10n1,3,18n2,4,5n3,2,5n4,3,2n4,5,2n5,3,2n); printf(再输入从哪个顶点出发，例如:1n); printf(程序将会找出从1到其余顶点的最短路径.n); printf(10 1-2n17 1-2-4-3n15 1-2-4n17 1-2-4-5n);while(j!=N&j!=n) CreateGraph(G); /生成邻接矩阵结构的图 printf(从哪个顶点出发:); scanf(%d,&u); /输入迪杰斯特拉算法中的起始顶点 ShortestPath_DiJ(G,u,P,D); /利用迪杰斯特拉算法求最短路径 Print_ShortestPath(G,u,P,D); /显示最短路径 printf(最短路径演示完毕，继续进行吗?(Y/N); scanf( %c,&j); void CreateGraph(Graph &G)/构造邻接矩阵结构的图G int i,j; int start,end,weight; printf(请输入图的顶点数和弧数(顶点数，弧数):); scanf(%d,%d,&G.vexnum,&G.arcnum); /输入图的顶点数和边数 for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+) G.arcsij=INFINITY; /初始化邻接矩阵 printf(输入各弧和权值，格式：弧尾，弧头，权值n); for(i=1;i=G.arcnum;i+) scanf(%d,%d,%d,&start,&end,&weight); /输入边的起点和终点及权值 G.arcsstartend=weight; void ShortestPath_DiJ(Graph G,int v0,int PMAX_VERTEX_NUM,int D)/用迪杰斯特拉算法求有向网G的v0顶点到其余顶点v的最短路径Pv及其带权路径长度Dv /若Pv00,表明从源点出发存在一条到顶点v的最短路径，该路径存放在Pv中 /finalv为True则表明已经找到从v0到v的最短路径 int i,j,w,v; int min; BOOL finalMAX_VERTEX_NUM; for(v=1;v=G.vexnum;v+) /初始化 finalv=False; Dv=G.arcsv0v; for(i=0;i=G.vexnum;i+) Pvi=0; /设空路径 /if(DvINFINITY) Pv0=v0; /若从v0到v有直达路径 Dv0=0; finalv0=True; /初始时，v0属于S集 /开始主循环，每次求得v0到某个顶点v的最短路径，并加v到S集 for(i=1;i=G.vexnum;i+) /寻找其余G.vexnum-1个顶点 v=0; min=INFINITY; for(w=1;w=G.vexnum;w+) /寻找当前离v0最近的顶点v if(!finalw)&(Dwmin) v=w;min=Dw; if(!v) break; /若v=0表明所有与v0有通路的顶点均已找到了最短路径，退出主循环 finalv=True; /将v加入S集 for(j=0;Pvj!=0;j+) ; Pvj=v; /将路径Pv延伸到顶点v for(w=1;w=G.vexnum;w+) /更新当前最短路径及距离 if(!finalw&(min+G.arcsvwDw) Dw=min+G.arcsvw; for(j=0;Pvj!=0;j+) Pwj=Pvj; void Print_ShortestPath(Graph G,int v0,int PMAX_VERTEX_NUM,int D)/显示从顶点u到其余顶点的最短路径及距离 int v,j; printf(The shortest path from Vertex %d to the other Vertex:n); for(v=1;v,v0); for(j=0;Pvj!=0;j+) printf(%d-,Pvj); printf(bb n); 3.最短路径-弗洛依德算法#include #include #include #include #define INFINITY 10000 /定义权值的最大值 #define MAX_NUM 20 /图的最大顶点数enum BOOL False,True;typedef structint arcsMAX_NUMMAX_NUM; /邻接矩阵 int vexnum,arcnum; /图的当前顶点和边数Graph;void CreateGraph(Graph &); /生成图的邻接矩阵void ShortestPath_Floyd(Graph,BOOLMAX_NUMMAX_NUM,intMAX_NUM); /用弗洛依德算法求每对顶点之间的最短路径void Print_ShortestPath(Graph,BOOLMAX_NUMMAX_NUM,intMAX_NUM); /显示用弗洛依德算法所求得的最短路径void Print_OnePath(int,int,int,BOOLMAX_NUMMAX_NUM); /显示一对顶点之间的最短路径void main()Graph G; /采用邻接矩阵结构的图 char j=y; int u; BOOL PMAX_NUMMAX_NUMMAX_NUM; /存放每对顶点的最短路径 int DMAX_NUMMAX_NUM; /存放每对顶点的最短路径的距离printf(本程序演示弗洛依德算法求图的每一对顶点之间的最短路径。n); printf(首先输入图的顶点和弧的数目。n例如：3,5n); printf(接着输入弧(i,j)和其权值。n例如：n1,2,4n2,1,6n1,3,11n3,1,3n2,3,2n); printf(程序将会显示出每对顶点之间的最短路径值和所经过的路径：n); printf(4 1-2n6 1-2-3n5 2-3-1n2 2-3n3 3-1n7 3-1-2n);while(j!=N&j!=n) CreateGraph(G); /生成邻接矩阵结构的图 ShortestPath_Floyd(G,P,D); /利用弗洛依德算法求最短路径 Print_ShortestPath(G,P,D); /显示每对顶点之间的最短路径 printf(继续执行吗?(Y/N); scanf( %c,&j); printf(程序运行结束，按任意键退出窗口!); getch();void CreateGraph(Graph &G)/构造邻接矩阵结构的图G int i,j; int start,end,weight; printf(请输入顶点和弧的数目，格式：顶点数，弧数n); scanf(%d,%d,&G.vexnum,&G.arcnum); /输入图的顶点数和边数 for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+) G.arcsij=INFINITY; /初始化邻接矩阵 printf(请输入各条弧和其权值，格式：弧尾，弧头，权值：n); for(i=1;i=G.arcnum;i+) scanf(%d,%d,%d,&start,&end,&weight); /输入边的起点和终点及权值 G.arcsstartend=weight; void ShortestPath_Floyd(Graph G,BOOL PMAX_NUMMAX_NUM,int DMAX_NUM)/用弗洛依德算法求有向网G的每对顶点v和w之间的最短路径Pvw /及其带权路径长度Dvw, /若Pvwu为True,表明u是从v到w当前求得最短路径上的顶