《数据结构java第07章 图》由会员分享,可在线阅读,更多相关《数据结构java第07章 图(25页珍藏版)》请在金锄头文库上搜索。
1、叶核亚,数据结构(Java版) (第2版),数据结构(Java版)(第2版),第0章 Java程序设计基础 第1章 绪论 第2章 线性表 第3章 栈与队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第8章 查找 第9章 排序 第10章 综合应用设计 第11章 Java开发运行环境,数据结构(Java版)(第2版),第7章 图,7.1 图及其抽象数据类型 7.2 图的表示和实现 7.3 图的遍历 7.4 最小生成树 7.5 最短路径目的:理解图结构。 要求:掌握图的存储结构和操作实现。 重点:图的两种存储结构,遍历算法,最小生成 树,最短路径。 难点:图的存储和操作实现,
2、最小生成树,最短 路径。,数据结构(Java版)(第2版),7.1 图及其抽象数据类型 7.1.1 图的基本概念,图的定义和术语 G=(V, E) V=A | A某个数据元素集合 E=(A, B) | A, BV 无向图 有向图,数据结构(Java版)(第2版),完全图 带权图 邻接顶点,数据结构(Java版)(第2版),2.顶点的度,deg(A)=indeg(A)outdeg(A) 3.子图,数据结构(Java版)(第2版),4.路径 5.连通性,数据结构(Java版)(第2版),7.1.2 图抽象数据类型,public interface GGraph /图接口int vertexCoun
3、t(); /返回顶点数E get(int i); /返回顶点vi元素boolean insertVertex(E vertex); /插入顶点boolean insertEdge(int i, int j, int weight); /插入边boolean removeVertex(int v); /删除顶点boolean removeEdge(int i, int j); /删除边int getFirstNeighbor(int v); /返回邻接顶点序号int getNextNeighbor(int v, int w); /返回下一个邻接顶点 ,数据结构(Java版)(第2版),7.2 图
4、的表示和实现,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,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);图的插入操
5、作,数据结构(Java版)(第2版),图的删除操作 带权值的边类 邻接矩阵表示的带权图类,数据结构(Java版)(第2版),7.2.2 图的邻接表表示,邻接表 无向图的邻接表表示,数据结构(Java版)(第2版),有向图的邻接表表示,数据结构(Java版)(第2版),2.邻接表表示的带权图类,顶点表元素类 邻接表表示的带权图类的声明及构造方法 图的插入操作,数据结构(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算法,数据结构(Java版)(第2版),数据结构(Java版)(第2版),2.Kruskal算法,数据结构(Java版)(第2版),7.5 最短路径,数据结构(Java版)(第2版),