数据结构java第07章图ppt课件

1、叶核亚叶核亚数据结构数据结构Java版）版）（第（第2版）版）数据结构数据结构Java版）（第版）（第2版）版）第0章 Java程序设计基础第1章 绪论第2章 线性表第3章 栈与队列第4章 串第5章 数组和广义表第6章 树和二叉树第7章 图第8章 查找第9章 排序第10章 综合应用设计第11章 Java开发运行环境第第7章章 图图l7.1 图及其抽象数据类型图及其抽象数据类型l7.2 图的表示和实现图的表示和实现l7.3 图的遍历图的遍历l7.4 最小生成树最小生成树l7.5 最短路径最短路径l目的：理解图结构。目的：理解图结构。l要求：掌握图的存储结构和操作实现。要求：掌握图的存储结构和操作

2、实现。l重点：图的两种存储结构，遍历算法，最小生成重点：图的两种存储结构，遍历算法，最小生成 树，最短路径。树，最短路径。l难点：图的存储和操作实现，最小生成树，最短难点：图的存储和操作实现，最小生成树，最短 途径。途径。7.1 图及其抽象数据类型图及其抽象数据类型 7.1.1 图的基本概念图的基本概念1.图的定义和术语图的定义和术语 G=(V, E) 2.V=A | A某个数据元素集合某个数据元素集合 3.E=(A, B) | A, BV 4.无向图无向图 5.有向图有向图 n完全图完全图n带权图带权图 n邻接顶点邻接顶点 2.顶点的度顶点的度 deg(A)=indeg(A)outdeg(A

3、)3.子图子图4.途径途径 5.连通性连通性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

4、j); /删除边删除边 int getFirstNeighbor(int v); /返回邻接顶点序号返回邻接顶点序号 int getNextNeighbor(int v, int w); /返回下一个邻接顶返回下一个邻接顶点点7.2 图的表示和实现图的表示和实现7.2.1 图的邻接矩阵表示图的邻接矩阵表示7.2.2 图的邻接表表示图的邻接表表示7.2.1 图的邻接矩阵表示图的邻接矩阵表示1.邻接矩阵邻接矩阵 2.不带权图的邻接矩阵不带权图的邻接矩阵3.带权图的邻接矩阵带权图的邻接矩阵 1若(v ,v )或v ,v0若(v ,v )或v ,vijijijijijEEaEE2.邻接矩阵表示的带权图

5、类邻接矩阵表示的带权图类 邻接矩阵表示的带权图类的声明及构造方法邻接矩阵表示的带权图类的声明及构造方法 顶点集合顶点集合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);图的插入操作图的插入操作n图的删除操作图的删除操作 n带权值的边类带权值的边类 n邻接矩阵表示的带权图类邻接矩阵表示的带权图类 7.2.2 图的邻接表表示图的邻接表表示1.邻接表邻接表2.无向图的

6、邻接表表示无向图的邻接表表示 n有向图的邻接表表示有向图的邻接表表示 2.邻接表表示的带权图类邻接表表示的带权图类 顶点表元素类顶点表元素类邻接表表示的带权图类的声明及构造方法邻接表表示的带权图类的声明及构造方法图的插入操作图的插入操作 n图的删除操作图的删除操作 n邻接表表示的图类邻接表表示的图类CADEBC2567893(a) 在G3的邻接表存储结构中删除顶点C删除顶点及边单链表ADEB2569(b) 删除顶点C之后未删除的边结点更改某些顶点序号ADBE01234052717380216233936432849111222333344153200DAEB01230502162926391122231522007.3 图的遍历图的遍历7.3.1 图的深度优先搜索遍历图的深度优先搜索遍历7.3.2 图的广度优先搜索遍历图的广度优先搜索遍历7.3.1 图的深度优先搜索遍历图的深度优先搜索遍历7.3.2 图的广度优先搜索遍历图的广度优先搜索遍历7.4 最小生成树最小生成树7.4.1 生成树