数据结构实验一图剖析.doc

《数据结构实验一图剖析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验二——图学生姓名：佘晨阳班级：班内序号：20学号：日期：2015年12月05日1．实验要求根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小生成树7、求指定顶点到其他各顶点的最短路径8、其他：比如连通性判断等自定义操作编写测试main()函数测试图的正确性2.程序分析本实验要求掌握图基本操作的实现方

2、法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念，学习使用图解决实际问题的能力。2.1存储结构存储结构：1.不带权值的无向图邻接矩阵2.带权值的无向图邻接矩阵3.带权值的有向图邻接矩阵1．不带权值的无向图邻接矩阵第17页北京邮电大学信息与通信工程学院2带权值的无向图邻接矩阵.3.带权值的有向图邻接矩阵[备注]：1.在使用打印元素、BFS、DFS采用无权值的无向图邻接矩阵存储方式2.在使用PRIM、KRUSKAL、3.在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式2.2关键算

3、法分析第17页北京邮电大学信息与通信工程学院一．图的邻接矩阵构造函数：1.关键算法：templateGraph::Graph(fa[],intn,inte)//带权值的图的构造函数{inti,j,k,height;fs1,s2;vnum=n;arcnum=e;for(k=0;k

4、权值的大小}visited[k]=0;}cout<>s1>>s2>>height;arc[convert(s1)][convert(s2)]=height;arc[convert(s2)][convert(s1)]=arc[convert(s1)][convert(s2)];//采用无向图带权值的邻接矩阵}cout<

5、++){for(i=0;i

6、的下一个未访问过的顶点开始深度优先遍历④直到所有和v路径相通的顶点都被访问到；2.代码图解：深度优先遍历示意图3.代码详解：templatevoidGraph::DFS(intv){cout<=1))DFS(j);//当存在回路时，则连通深一层遍历}4.时间复杂度时间复杂度：O(n2)空间复杂度：栈的深度O(n)辅助空

7、间O(n)第17页北京邮电大学信息与通信工程学院三．广度遍历BFS1.关键算法①访问顶点v②依次访问v的所有未被访问的邻接点v1,v2,v3…③分别从v1,v2,v3…出发依次访问它们未被访问的邻接点④反复①②③，直到所有和v路径相通的顶点都被访问到；2.代码图解3.代码详解1.初始化队列Q2.访问顶点v，visited[v]=13.while(队列非空)3.1v=队头元素出队3.2访问队头元素的所有未访问的邻接点4.时间复杂度时间复杂度：O(n2)空间复杂度：辅助空间O(n)四.最小生成树——普里姆

8、算法1,关键思路一般情况下，假设n个顶点分成两个集合：U(包含已落在生成树上的结点)和V-U(尚未落在生成树上的顶点)，则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。主数据结构：邻接矩阵辅助数据结构：intadjvex[MAXSIZE];//U集中的顶点序号第17页北京邮电大学信息与通信工程学院intlowcost[MAXSIZE];//Uà(V-U)的最小权值边2.代码图解第17页北京邮电大学信息与通信工程学院第17页北京邮电大学信息与通信