数据结构java第07章.ppt

叶核亚,数据结构（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 最短路径目的：理解图结构。要求：掌握图的存储结构和操作实现。重点：图的两种存储结构，遍历算法，最小生成 树，最短路径。难点：图的存储和操作实现，最小生成树，最短 路径。,数据结构（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 vertexCount();/返回顶点数 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 图的表示和实现,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);图的插入操作,数据结构（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版）,