第一篇：图的应用 实验
图的应用 实验日志
实验题目：图的建立及输出
实验目的：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。实验主要步骤： 1.编辑源程序；
2.编写有向图的实现程序； 3.编写实现无向图的源程序；
4.连接—编译—运行该程序，并在过程中调试。源程序：
#include
typedef struct{ int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int vexnum;int arcnum;char vexs[MAX_VERTEX_NUM];}MGraph;
int LocateVex(MGraph G,char v){ int i;for(i=0;i if(G.vexs[i]==v) return i;} return 0;} int CreateUDG(MGraph G){ int i,j,k,w;char v1,v2;printf(“请输入顶点和边：n”);scanf(“%d%d”,&G.vexnum,&G.arcnum);for(i=0;i int CreateDG(MGraph G){ int i,j,k,w;char v1,v2;printf(“请输入顶点和边：n”);scanf(“%d%d”,&G.vexnum,&G.arcnum);for(i=0;i n”);} printf(“输出的领接矩阵是：n”);for(i=0;i printf(“ %d ”,G.arcs[i][j]);printf(“n”);} return 0;} void main(){ char kind[5];MGraph G;printf(“请输入要建立的图的类型(UDG或DG)：n”); scanf(“%s”,kind);if(strcmp(“UDG”,kind)==0) CreateUDG(G);if(strcmp(“DG”,kind)==0) CreateDG(G);} 实验结果： 心得体会：通过实验掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构； 数据结构上机实验六 实验内容:图的基本操作 实验要求: 1)图的遍历与基本操作要作为函数被调用.2)把自己使用的图结构明确的表达出来.3)基本上实现每个实验题目的要求.分组要求：可单独完成，也可两人一组。 实验目的: 1)熟悉C/C++基本编程,培养动手能力.2)通过实验,加深对图的理解.评分标准： 1)只完成第一和第二题，根据情况得4，5分； 2）完成前3题，根据情况得5至7分； 3）在2）基础上，选做四）中题目，根据情况得8至10分。 题目: 一)建立一个无向图+遍历+插入 (1)以数组表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图； (2)对（1）中生成的无向图进行广度优先遍历并打印结果； (3)向（1）中生成的无向图插入一条新弧并打印结果； 二)建立一个有向图+遍历+插入+删除 (1)以邻接表作为图的存储结构，从键盘输入图的顶点与弧的信息建立一个有向图； (2)对（1）中生成的有向图进行深度优先遍历并打印结果； (3)在（1）中生成的有向图中，分别插入与删除一条弧并打印其结果； (4)在（1）中生成的有向图中，分别插入与删除一个顶点并打印结果； (5)在（1）中生成的有向图中,各顶点的入度与出度并打印结果； 三）基本应用题 （1）编写算法，判断图中指定的两个顶点是否连通。 （2）编写算法，判断图的连通性。如果不连通，求连通分量的个数 （3）编写算法，判断图中任意两个顶点的连通性 （4）编写算法，判断图中是否存在回路。 （5）实现图的广度优先搜索算法。 四）高级应用题 （1）实现Prim算法 （2）实现Kruskal算法 （3）实现迪杰斯特拉算法 （4）实现拓扑排序算法 （5）实现关键路径算法 北京邮电大学信息与通信工程学院 数据结构实验报告 实验名称： 实验二——图 学生姓名： 佘晨阳 班 级： 2014211117 班内序号： 20 学 号： 2014210491 日 期： 2015年12月05日 1．实验要求 根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能： 1、图的建立 2、图的销毁 3、深度优先遍历图 4、广度优先遍历图 5、使用普里姆算法生成最小生成树 6、使用克鲁斯卡尔算法生成最小生成树 7、求指定顶点到其他各顶点的最短路径 8、其他：比如连通性判断等自定义操作 编写测试main()函数测试图的正确性 2.程序分析 本实验要求掌握图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念，学习使用图解决实际问题的能力。 2.1 存储结构 存储结构：1.不带权值的无向图邻接矩阵 2.带权值的无向图邻接矩阵 3.带权值的有向图邻接矩阵 1．不带权值的无向图邻接矩阵 第1页 北京邮电大学信息与通信工程学院 2带权值的无向图邻接矩阵.3.带权值的有向图邻接矩阵 [备注]： 1.在使用打印元素、BFS、DFS 采用无权值的无向图邻接矩阵存储方式 2.在使用PRIM、KRUSKAL、3.在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式 2.2 关键算法分析 第2页 北京邮电大学信息与通信工程学院 一．图的邻接矩阵构造函数： 1.关键算法： template //带权值的图的构造函数 { int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for(k = 0;k < n;k++){ vertex[k] = a[k];} //初始化顶点 for(k = 0;k for(i = 0;i < n;i++) { arc[k][i] =-1; if(i == k)arc[k][i] = 0; //初始化权值的大小 } visited[k] = 0;} cout << endl;for(k = 0;k //初始化边 { cout << “请输入线性链接节点:”; cin >> s1 >> s2 >> height; arc[convert(s1)][convert(s2)] = height; arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)];//采用无向图带权值的邻接矩阵 } cout << endl;cout << “所得邻接矩阵为：” << endl; for(k = 0;k for(i = 0;i < n;i++) { if(arc[k][i] ==-1) cout << “∞” << “ ”; else cout << arc[k][i] << “ ”; //打印邻接矩阵的格式 } cout << endl; } cout << endl 2.算法的时间复杂度 第3页 北京邮电大学信息与通信工程学院 有构造可知，初始化时其时间复杂度：O(n2) 二．深度优先便利DFS: 1.关键算法 ①从某顶点v出发并访问 ②访问v的第一个未访问的邻接点w，访问w的第一个未访问的邻接点u，…… ③若当前顶点的所有邻接点都被访问过，则回溯，从上一级顶点的下一个未访问过的顶点开始深度优先遍历 ④直到所有和v路径相通的顶点都被访问到； 2.代码图解： 深度优先遍历示意图 3.代码详解： template for(int j = 0;j < vnum;j++) //连通图 if((visited[j] == 0)&&(arc[v][j] >= 1))DFS(j);//当存在回路时，则连通深一层遍历 } 4.时间复杂度 时间复杂度：O(n2) 空间复杂度：栈的深度O(n) 辅助空间O(n) 第4页 北京邮电大学信息与通信工程学院 三．广度遍历BFS 1.关键算法 ①访问顶点v ②依次访问v的所有未被访问的邻接点v1,v2,v3… ③分别从v1,v2,v3…出发依次访问它们未被访问的邻接点 ④反复①②③，直到所有和v路径相通的顶点都被访问到； 2.代码图解 3.代码详解 1.初始化队列Q 2.访问顶点v，visited[v]=1 3.while(队列非空) 3.1 v=队头元素出队 3.2 访问队头元素的所有未访问的邻接点 4.时间复杂度 时间复杂度：O(n2) 空间复杂度：辅助空间O(n) 四.最小生成树——普里姆算法 1,关键思路 一般情况下，假设n个顶点分成两个集合：U(包含已落在生成树上的结点)和V-U(尚未落在生成树上的顶点)，则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。主数据结构： 邻接矩阵 辅助数据结构： int adjvex[MAXSIZE];// U集中的顶点序号 第5页 北京邮电大学信息与通信工程学院 int lowcost[MAXSIZE]; // U(V-U)的最小权值边 2.代码图解 第6页 北京邮电大学信息与通信工程学院 第7页 北京邮电大学信息与通信工程学院 3;代码详解 template //辅助数组存储所有到的V0边 { adjvex[i] = 0;lowcost[i] = arc[0][i]; } lowcost[0] = 0;for(int j = 1;j < vnum;j++) //循环n-1次 { int k = Mininum(lowcost); //求下一个顶点 cout << vertex[adjvex[k]] << “->” << vertex[k] << endl; lowcost[k] = 0; //U=U+{Vk} for(int j = 0;j < vnum;j++) //设置辅助数组 { if((lowcost[j]!= 0 && arc[k][j] < lowcost[j])) { lowcost[j] = arc[k][j]; adjvex[j] = k; } } 第8页 北京邮电大学信息与通信工程学院 } } 4,时间复杂度： 时间复杂度O(n2)，适合稠密图 五.最小生成树----克鲁斯卡尔算法 1,关键思路 先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。2.代码图解： 3.代码详解 template //最小生成树—kruskal算法 { cout<<“Krusal算法结果为：”< int k = 0, j = 0; while(k < vnum-1){ int m = vedgelist[j].fromv, n = vedgelist[j].endv; int sn1 = vset[m]; int sn2 = vset[n]; //两个顶点分属 第9页 北京邮电大学信息与通信工程学院 不同的集合 if(sn1!= sn2) { cout << vertex[m] << “->” << vertex[n] << endl; k++; for(int i = 0;i < vnum;i++) { if(vset[i] == sn2) vset[i] = sn1; //集合sn2全部改成sn1 } } j++;} } 4.时间复杂度 时间复杂度O(nlogn)，适合稀疏图 六．最短路径——Dijkstra算法 1.关键代码 • 按路径长度递增的次序产生源点到其余各顶点的最短路径。• 1)设置集合s存储已求得的最短路径的顶点，• 2)初始状态：s=源点v • 3)叠代算法： • 直接与v相连的最近顶点vi,加入s • 从v经过vi可以到达的顶点中最短的，加入s …… 2.代码图解 第10页 北京邮电大学信息与通信工程学院 3.代码详解 emplate //关于最短路径的初始化 { int v=convert(x); for(int i = 0;i < vnum;i++) //初始化路径和点 { s[i]=0; disk[i] = arc[v][i]; if(disk[i]!= maxs)path[i] = v; else path[i] =-1;} s[v] = 1;disk[v] = 0;path[v]=-1;for(int i = 0;i < vnum;i++) //反复经过从该点到其他点的路径 { if((v = FindMin())==-1)continue; s[v] = 1; for(int j = 0;j < vnum;j++) if(!s[j] &&(disk[j]>arc[v][j] + disk[v])) { 第11页 北京邮电大学信息与通信工程学院 disk[j] = arc[v][j] + disk[v]; path[j] = v; } } Print(); //打印路径长度和遍历 } 4.时间复杂度 时间复杂度为：n^2 七．判断连通图算法 template { cout<<“该图为连通图！*******输入成功！”< return false; } else { cout<<“该图不为连通图！*******请重新输入”< return true; } } 时间复杂度：n^2 3.程序运行结果 1.测试主函数流程： 第12页 北京邮电大学信息与通信工程学院 函数流程图： 1.输入图的连接边并打印 构造下面所示图的邻接矩阵： 第13页 北京邮电大学信息与通信工程学院 2.判断图连通是否成功 3.BFS DFS PRIM算法的实现 第14页 北京邮电大学信息与通信工程学院 4.克鲁斯卡尔算法实现过程 4.有向图邻接矩阵的构建 第15页 北京邮电大学信息与通信工程学院 插入V0位置后打印距离并开始回溯 总结 1.调试时出现的问题及解决的方法 问题一：prim算法中 解决方法：调整循环条件，修正函数体注意有无Next的区别 第16页 北京邮电大学信息与通信工程学院 问题二：BFS和DFS同时在一个类里作用时会输出错误 解决方案：每次BFS/DFS使用时都把visited数组初始化一遍 问题三：在最短路径，经常出现了停止输入的情况 解决方法：改return为continue，并修改打印算法 2.心得体会 通过本次实验，基本熟练掌握了c++基本语句，尤其对图的结构及应用有了较深了解；调试代码时尽量做到完成一个代码段调试一次，可以最快检测出错误所在；类的封装和调用，类的共有成员和私有成员的设置。 3.下一步的改进 第一，设置增加图节点和边的函数 第二，实现图形化输出图的路径的功能 第三，主函数设计简单，不要过于累赘 4.程序中出现的亮点 1)利用dfs算法衍生生成判断是否为连通图的连通算法 2)采用graph类实现所有图的所有算法，所需的数据类型均在私有成员内，封装 3)利用convert函数采取象意输入，采用ABCD的节点输入方式而并非转化成01234再输入。 4)BFS中采用c++标准库的。 5)打印邻接矩阵时，打印出非链接的∞符号和与自身路径的0距离 6)判断图为非连通图后，提示输入错误，重新输入图元素 第17页 “数据结构和算法II”课程实验报告 实验名称：图及其应用 班级 姓名 学号 实验日期： 实验机时：2 学时 实验成绩： -----------------一.实验目的： 1.熟练掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法 2.掌握图的基本运算及应用 3.加深对图的理解，逐步培养解决实际问题的编程能力 二.实验内容：（1）基本实验内容： 采用邻接表或邻接矩阵方式存储图，实现图的深度遍历和广度遍历； 用广度优先搜索方法找出从一顶点到另一顶点边数最少的路径。三.程序及注释： #include “stdio.h” #include “limits.h” //INT_MAX头文件 #include “windows.h” //boolean头文件 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 #define OVERFLOW-1 #define OK 1 #define ERROR 0 typedef int Status;typedef enum {DG,DN,UDG,UDN} GraphKind;typedef int VRType;typedef char VertexType;typedef char* InfoType;typedef int QElemType;//边信息 typedef struct ArcCell{ VRType adj;//1或0表示是否邻接,对带权图，则为权值类型 InfoType *info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//图结构 typedef struct { VertexType vexs[MAX_VERTEX_NUM];//定点向量 AdjMatrix arcs; //邻接矩阵，为一二维数组 //图的当前顶点数和弧数 int vexnum,arcnum;GraphKind kind; //图的种类标志 }MGraph;//辅助队列 typedef struct QNode{ QElemType data;//数值域 struct QNode *next;//指针域 }QNode, *QueuePtr;typedef struct{ QueuePtr front;//队头 QueuePtr rear;//队尾 }LinkQueue;//初始化队列 Status InitQueue(LinkQueue &Q){ Q.front = Q.rear =(QueuePtr)malloc(sizeof(QNode));if(!Q.front){ printf(“内存分配失败!”);exit(OVERFLOW);} Q.front->next = NULL;return OK;} //插入元素到队尾 Status EnQueue(LinkQueue &Q,QElemType e){ QueuePtr p =(QueuePtr)malloc(sizeof(QNode));if(!p){printf(“n内存分配失败!”);exit(OVERFLOW);} p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;} //队列判空 Status QueueEmpty(LinkQueue Q){ return Q.front == Q.rear;} //销毁队列 Status DestroyQueue(LinkQueue &Q){ while(Q.front){Q.rear = Q.front->next;free(Q.front);Q.front = Q.rear;} return OK;} //删除队头元素 Status DeQueue(LinkQueue &Q,QElemType &e){ if(QueueEmpty(Q)){printf(“n队列为空！”);return ERROR;} QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear==p)Q.rear = Q.front;free(p);return OK;} //对顶点v定位，返回该顶点在数组的下标索引，若找不到则返回-1 int LocateVex(MGraph G,char v){ for(int i=0;i G.kind = UDN;printf(“输入顶点个数和边数(如：4,3):”);int vexnum,arcnum;scanf(“%d,%d”,&vexnum,&arcnum);G.vexnum=vexnum;G.arcnum=arcnum;//判断是否超过顶点最大个数 while(G.vexnum>MAX_VERTEX_NUM){printf(“最大顶点为20，重新输入(如：4,3):”);scanf(“%d,%d”,&G.vexnum,&G.arcnum);} printf(“n依次输入顶点向量值n”);int i;for(i=0;i //清空缓冲区 fflush(stdin);printf(“第%d个:”,i+1);scanf(“%c”,&G.vexs[i]);} //初始化邻接矩阵 for(i=0;i int values;printf(“n输入依附两个顶点的边及其权值<如，a,b,1>n”);for(i=0;i printf(“第%d条：”,i+1);//清空缓冲区 fflush(stdin);scanf(“%c,%c,%d”,&rear,&front,&values);int m,n;//定位两顶点在vexs数组中的索引 m = LocateVex(G,rear);n = LocateVex(G,front);if(m==-1||n==-1){ printf(“输入顶点或不在此图中，请重新输入！n”);i--;continue;} //赋予对应矩阵位置的权值，以及对称弧的权值 G.arcs[m][n].adj = values;G.arcs[n][m].adj = values;} return OK;} //CreateUDG //矩阵输出 void printArcs(MGraph G){ int i;printf(“ ”);//输出第一行的顶点向量 for(i=0;i for(int j=0;j else printf(“ %d”,G.arcs[i][j].adj);}} printf(“ ∞”); printf(“n”);} //访问顶点v输出 Status printAdjVex(MGraph G,int v){ printf(“%c ”,G.vexs[v]);return OK;} //查找v顶点的第一个邻接点 Status FirstAdjVex(MGraph G,int v){ //查找与顶点v的第一个邻接点，找到后立即返回其索引，若找不到，则返回-1 for(int i=1;i return i;} return-1;} //查找基于v顶点的w邻接点的下一个邻接点 Status NextAdjVex(MGraph G,int v,int w){ //查找基于顶点v的w邻接点的下一个邻接点，找到之后立即返回其索引，若找不到，则返回-1 for(int i=w+1;i boolean visited[MAX_VERTEX_NUM];//函数指针变量 Status(* VisitFunc)(MGraph G,int v);//DFS,从第v个顶点出发递归深度优先遍历图G void DFS(MGraph G,int v){ visited[v] = TRUE;//访问第v个顶点 VisitFunc(G,v);for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){if(!visited[w]) DFS(G,w);}} //深度优先遍历 void DFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //将函数复制给全局的函数指针变量，待调用DFS时使用 VisitFunc = Visit;int v;//将访问标记初始化为false for(v=0;v void BFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //按广度优先非递归遍历图G，使用辅助队列Q和访问标志数组Visited int v;int u;//将访问标记数组初始化为false for(v = 0;v //判断顶点V是否被访问 if(!visited[v]){//将第一次访问的顶点对应的访问标记数组位置赋值为TRUE visited[v] = TRUE;//输出顶点v Visit(G,v);EnQueue(Q,v);while(!QueueEmpty(Q)){//按入队序列取出顶点，便于查找此顶点的邻接点 DeQueue(Q,u);//查找当前顶点邻接点 for(int w=FirstAdjVex(G,u);w>=0;w = NextAdjVex(G,u,w)) if(!visited[w]){visited[w] =TRUE;Visit(G,w);EnQueue(Q,w);}}} //销毁队列 DestroyQueue(Q);} int main(){ printf(“====图的创建及其应用====n”);//创建一个图 MGraph G;CreateUDN(G);//用邻接矩阵输出图 printf(“n图的邻接矩阵输出如下:n”);printArcs(G);//深度优先遍历 printf(“n深度优先遍历序列:n”);DFSTraverse(G,printAdjVex);printf(“n”);//广度优先遍历 } printf(“n广度优先遍历序列:n”);BFSTraverse(G,printAdjVex);printf(“n”);四.运行结果： 五.实验心得： 通过本次课程设计，对图的概念有了一个新的认识，在学习离散数学的时候，总觉得图是很抽象的东西，但是在学习了《数据结构与算法》这门课程之后，我慢慢地体会到了其中的奥妙，图能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也就说明了想要把生活中的信息转化到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点之间的联系。图分为有向图和无向图，而无向图又是有向图在权值双向相等下的一种特例，如何能在计算机中表示一个双向权值不同的图，这就是一件很巧妙的事情。有了这次课程设计的经验和教训，我能够很清楚的对自己定一个合适的水平。 一、实验项目： 实验项目一：平面图测绘实习 实验目的：通过实习使学生掌握平面图测绘的基本原理，学会小平板与皮尺配合测绘大比例尺平面图的方法和过程。 实验任务：学生分成每组4-5人，每组完成校园内部分地物的平面图测绘。 实验器材：小平板仪、皮尺、三角板、比例尺、分规、大头针、花杆、工具包 实验要求： 1、掌握平板仪的安置方法； 2、掌握碎部点的测绘方法； 3、会用地形图图式符号表示地物。 实验项目二：扫描矢量化成图 实验目的：使学生了解扫描矢量化的基本原理，学会用矢量化软件进行地图数字化。 实验任务：先由指导教师进行演示与操作，学生认真观察，指导完成后，学生方可进行地图数字化。 实验器材：微机、扫描矢量化软件、地形图一幅 实验要求： 1、地图扫描成栅格图形； 2、栅格图形矢量化。实验项目三：数字化测图系统认识实习 实验目的：使学生对数字化测图系统的构成有较为深刻的认识，从而理解数字化测图系统的全过程。 实验任务：实验时，以指导教师进行演示与操作为主，学生认 真观察，指导完成后，学生方可进行相应适当的操作。 实验器材：全站仪、数字化仪、绘图仪、绘图软件、扫描仪。实验要求： 1、演示现有地图数字化方法（扫描数字化）； 2、演示全站仪外业数据向微机传送； 3、演示内业成图的方法，使学生了解成图软件； 4、演示绘图仪绘图的过程，使学生初步认识绘图仪。 实验项目四：全站仪的认识与使用 实验目的：了解全站仪的基本结构，全站仪的基本操作方法。实验任务：实验时，先由指导教师进行演示与操作，学生认 真观察，指导完成后，学生方可进行相应的操作。 实验器材：每组全站仪1台，脚架2个，花杆2根，反光镜2个，记录板，铅笔。 实验要求： 1、熟悉全站仪测角模式、测距模式和坐标模式下的基本操作； 2、一个测站上已知数据的输入和碎部点坐标的测量方法。 实验项目五：野外数据采集测量实习 实验目的：使学生学会使用全站仪进行野外大比例尺数字测图的基本方法。 实验任务：先由指导教师进行演示与操作，学生认真观察，指导完成后，学生方可进行相应的操作。 实验器材：每组全站仪一台、脚架两个、花杆两个、反光镜两个、记录板、铅笔 实验要求： 1、熟悉全站仪在数据采集模式下的基本操作； 2、了解外业数据文件的记录格式； 3、学会“一步测量法”野外数据测图的基本方法； 4、学会野外工作草图的绘制和记录方法； 5、根据具体条件每组完成老师指定范围内的地形测量任务。 实验项目六：地形图的内业编绘和输出 实验目的：使学生学会地形图的内业编绘和输出方法。实验任务：先由指导教师进行演示与操作，学生认真观察，指导完成后，学生方可进行地形图的编绘。实验器材：微机、绘图仪、成图软件 实验要求： 1、将实习5中预处理过的数据，利用成图软件绘成地形图； 2、对所绘地形图进行编辑修改（包括注记）； 3、学会地形图分幅及图廓的绘制和注记； 4、将所绘图形在绘图仪上输出。 二、实验课考核方式： （1）实习报告：每位参加实验的同学必须提交实习报告。实习报告主要内容包括：实习的目的、要求及内容，实验原理、方法、步骤，技术参数，实验结果及实验结果分析，实习体会等。（2）实验课考核方式 考核方式：评阅实习报告与仪器操作测验相结合。第二篇：数据结构上机实验--图
第三篇：数据结构 实验一 图[推荐]
第四篇：湘潭大学 数据结构实验5 实验报告 源代码 图的应用
第五篇：数字测图实验指导书
点击咨询 