资源描述:
《数据结构java第07章 图.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、叶核亚数据结构(Java版)(第2版)数据结构(Java版)(第2版)第0章Java程序设计基础第1章绪论第2章线性表第3章栈与队列第4章串第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章排序第10章综合应用设计第11章Java开发运行环境第7章图7.1图及其抽象数据类型7.2图的表示和实现7.3图的遍历7.4最小生成树7.5最短路径目的:理解图结构。要求:掌握图的存储结构和操作实现。重点:图的两种存储结构,遍历算法,最小生成树,最短路径。难点:图的存储和操作实现,最小生成树,最短路径
2、。《数据结构(Java版)(第2版)》7.1图及其抽象数据类型7.1.1图的基本概念图的定义和术语G=(V,E)V={A
3、A∈某个数据元素集合}E={(A,B)
4、A,B∈V}无向图有向图《数据结构(Java版)(第2版)》完全图带权图邻接顶点《数据结构(Java版)(第2版)》2.顶点的度deg(A)=indeg(A)+outdeg(A)3.子图《数据结构(Java版)(第2版)》4.路径5.连通性《数据结构(Java版)(第2版)》7.1.2图抽象数据类型publicinterfaceGGra
5、ph{//图接口intvertexCount();//返回顶点数Eget(inti);//返回顶点vi元素booleaninsertVertex(Evertex);//插入顶点booleaninsertEdge(inti,intj,intweight);//插入边booleanremoveVertex(intv);//删除顶点booleanremoveEdge(inti,intj);//删除边intgetFirstNeighbor(intv);//返回邻接顶点序号intgetNextNei
6、ghbor(intv,intw);//返回下一个邻接顶点}《数据结构(Java版)(第2版)》7.2图的表示和实现7.2.1图的邻接矩阵表示7.2.2图的邻接表表示《数据结构(Java版)(第2版)》7.2.1图的邻接矩阵表示邻接矩阵不带权图的邻接矩阵带权图的邻接矩阵《数据结构(Java版)(第2版)》2.邻接矩阵表示的带权图类邻接矩阵表示的带权图类的声明及构造方法顶点集合{"A","B","C","D","E"};边集合{(0,1,5),(0,3,2),(1,0,5),(1,2,7),(1,3
7、,6),(2,1,7),(2,3,8),(2,4,3),(3,0,2),(3,1,6),(3,2,8),(3,4,9),(4,2,3),(4,3,9)};图的插入操作《数据结构(Java版)(第2版)》图的删除操作带权值的边类邻接矩阵表示的带权图类《数据结构(Java版)(第2版)》7.2.2图的邻接表表示邻接表无向图的邻接表表示《数据结构(Java版)(第2版)》有向图的邻接表表示《数据结构(Java版)(第2版)》2.邻接表表示的带权图类顶点表元素类邻接表表示的带权图类的声明及构造方法图的插
8、入操作《数据结构(Java版)(第2版)》图的删除操作邻接表表示的图类《数据结构(Java版)(第2版)》7.3图的遍历7.3.1图的深度优先搜索遍历7.3.2图的广度优先搜索遍历《数据结构(Java版)(第2版)》7.3.1图的深度优先搜索遍历《数据结构(Java版)(第2版)》7.3.2图的广度优先搜索遍历《数据结构(Java版)(第2版)》7.4最小生成树7.4.1生成树树生成树和生成森林最小生成树《数据结构(Java版)(第2版)》7.4.2最小生成树的构造算法Prim算法《数据结构(J
9、ava版)(第2版)》《数据结构(Java版)(第2版)》2.Kruskal算法《数据结构(Java版)(第2版)》7.5最短路径《数据结构(Java版)(第2版)》《数据结构(Java版)(第2版)》