数据结构与算法之图.doc

仲恺农业工程学院实验报告纸 （院、系） 专业 班 组 课学号 姓名 实验日期 教师评定 实验四 图的建立及应用一、实验目的 1、掌握图的存储思想及其存储实现。 2、掌握图的深度、广度优先遍历算法思想及其程序实现。 3、理解最小生成树的有关概念以及普里姆算法和克鲁斯卡尔算法的实现。 4、理解最短路径、拓朴排序、关键路径算法及实现。二、实验要求 1、 编写程序实现图的各种运算，并在此基础上设计主函数，使其完成如下功能： （1）建立无向图 （2）输出无向图对应的邻接表。 （3）实现深度遍历和广度遍历。三、程序运算结果截图 四、程序源代码#include#includeusing namespace std;/#define N 20typedef char VertexType;/typedef struct ArcNodeint adjdex;struct ArcNode *next; /图的边界点AN;/typedef struct VNodeVertexType data;bool mark;AN *firstarc; /图的顶点VN;/VN GN; /定义图的顶点/void Create(int n,VN G) /创建无向图AN *p,*q;int i,e;VertexType d;coutInput the information of the vertexn;for(i=0;in;i+)coutGid;Gi.data=d; /初始化图的顶点Gi.firstarc=NULL;Gi.mark=false;for(i=0;in;i+)coutCreate the edges fo the Gie;while(e!=-1)p=(AN*)malloc(sizeof(AN);p-next=NULL;p-adjdex=e; /建立顶点间的关系if(Gi.firstarc=NULL)Gi.firstarc=p;elseq-next=p;q=p;cout按 -1 退出，否则继续创建边结点e;/void visit(VN G,int v)coutGv=Gv.dataadjdex; /查找顶点的第一条边return -1;/int NextAdj(VN G,int v)AN *p;p=Gv.firstarc;while(p-next!=NULL)if(Gp-next-adjdex.mark=true) /查找顶点的下一条边p=p-next;elsereturn p-next-adjdex;return -1;/void Visit(VN G,int n)int i,j,w;for(i=0;in;i+)Gi.mark=false;for(i=0;in;i+)coutGi:;w=FirstAdj(G,i);while(w!=-1) /输出邻接表if(Gw.mark=false)coutGw ;Gw.mark=true;w=NextAdj(G,i);coutendl;for(j=0;jn;j+)Gj.mark=false;/void DFS(VN G,int v)int w;visit(G,v);Gv.mark=true;w=FirstAdj(G,v); /深度优先遍历图的主算法while(w!=-1)if(Gw.mark=false)DFS(G,w);w=NextAdj(G,v);/void Travel_DFS(VN G,int n)int i;for(i=0;in;i+)Gi.mark=false;for(i=0;in;i+)if(Gi.mark=false) /深度优先遍历图DFS(G,i);/void BFS(VN G,int v)int w;visit(G,v);Gv.mark=true;w=FirstAdj(G,v);while(w!=-1) /广度优先遍历图的主算法if(Gw.mark=false)visit(G,w);Gw.mark=true;w=NextAdj(G,v);/void Travel_BFS(VN G,int n)int i;for(i=0;in;i+)Gi.mark=false;for(i=0;in;i+)if(Gi.mark=false) /广度优先遍历图BFS(G,i);/void main()int n;coutn;Create(n,G);cout邻接表:endl; Visit(G,n);couten