数据结构java第07章图

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

2、作实现。掌握图的存储结构和操作实现。 重点：重点：图的两种存储结构，遍历算法，最小生成图的两种存储结构，遍历算法，最小生成 树，最短路径。树，最短路径。 难点：难点：图的存储和操作实现，最小生成树，最短图的存储和操作实现，最小生成树，最短 路径。路径。数据结构（java版）（第2版）7.1 图及其抽象数据类型图及其抽象数据类型 7.1.1 图的基本概念图的基本概念1.图的定义和术语图的定义和术语 g=(v, e) v=a | a某个数据元素集合某个数据元素集合 e=(a, b) | a, bv 无向图无向图 有向图有向图 数据结构（java版）（第2版）完全图完全图带权图带权图 邻接顶点邻接顶

3、点 数据结构（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 we

4、ight); /插入边插入边 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 图的邻接矩

5、阵表示图的邻接矩阵表示1.邻接矩阵邻接矩阵 不带权图的邻接矩阵不带权图的邻接矩阵带权图的邻接矩阵带权图的邻接矩阵 1若(v ,v )或v ,v0若(v ,v )或v ,vijijijijijeeaee数据结构（java版）（第2版）2.邻接矩阵表示的带权图类邻接矩阵表示的带权图类 邻接矩阵表示的带权图类的声明及构造方法邻接矩阵表示的带权图类的声明及构造方法 n顶点集合a,b,c,d,e; n边集合 (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), (

6、3,4,9), (4,2,3), (4,3,9);图的插入操作图的插入操作数据结构（java版）（第2版）图的删除操作图的删除操作 带权值的边类带权值的边类 邻接矩阵表示的带权图类邻接矩阵表示的带权图类 数据结构（java版）（第2版）7.2.2 图的邻接表表示图的邻接表表示1.邻接表邻接表无向图的邻接表表示无向图的邻接表表示 数据结构（java版）（第2版）有向图的邻接表表示有向图的邻接表表示 数据结构（java版）（第2版）2.邻接表表示的带权图类邻接表表示的带权图类 顶点表元素类顶点表元素类邻接表表示的带权图类的声明及构造方法邻接表表示的带权图类的声明及构造方法图的插入操作图的插入操作

7、数据结构（java版）（第2版）图的删除操作图的删除操作 邻接表表示的图类邻接表表示的图类cadebc2567893(a) 在g3的邻接表存储结构中删除顶点c删除顶点及边单链表adeb2569(b) 删除顶点c之后未删除的边结点更改某些顶点序号adbe01234052717380216233936432849111222333344153200daeb0123050216292639112223152200数据结构（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 生成树生成树1.树树2.生成树和生成森林生成树和生成森林 3.最小生成树最小生成树 数据结构（java版）（第2版）7.4.2 最小