数据结构上机实验--图.docx

数据结构上机实验--图

第一篇：数据结构上机实验--图数据结构上机实验六实验内容:图的基本操作实验要求: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．不带权值的无向图邻接矩阵北京邮电大学信息与通信工程学院2带权值的无向图邻接矩阵.3.带权值的有向图邻接矩阵[备注]：1.在使用打印元素、BFS、DFS采用无权值的无向图邻接矩阵存储方式2.在使用PRIM、KRUSKAL、3.在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式2.2关键算法分析北京邮电大学信息与通信工程学院一．图的邻接矩阵构造函数：1.关键算法：templateGraph::Graph(fa[],intn,inte)//带权值的图的构造函数{inti,j,k,height;fs1,s2;vnum=n;arcnum=e;for(k=0;k//初始化顶点for(k=0;kfor(i=0;i{arc[k][i]=-1;if(i==k)arc[k][i]=0;//初始化权值的大小}visited[k]=0;}cout//初始化边{coutcin>>s1>>s2>>height;arc[convert(s1)][convert(s2)]=height;arc[convert(s2)][convert(s1)]=arc[convert(s1)][convert(s2)];//采用无向图带权值的邻接矩阵}coutfor(k=0;kfor(i=0;i{if(arc[k][i]==-1)coutelsecout//打印邻接矩阵的格式}cout}cout北京邮电大学信息与通信工程学院有构造可知，初始化时其时间复杂度：O(n2)二．深度优先便利DFS:1.关键算法①从某顶点v出发并访问②访问v的第一个未访问的邻接点w，访问w的第一个未访问的邻接点u，……③若当前顶点的所有邻接点都被访问过，则回溯，从上一级顶点的下一个未访问过的顶点开始深度优先遍历④直到所有和v路径相通的顶点都被访问到；2.代码图解：深度优先遍历示意图3.代码详解：templatevoidGraph::DFS(intv){coutfor(intj=0;j//连通图if((visited[j]==0)&&(arc[v][j]>=1))DFS(j);//当存在回路时，则连通深一层遍历}4