java数据结构第8章图.ppt
数据结构（Java版）,叶核亚,数据结构（Java版）,第1章 绪论第2章 线性表第3章 排序第4章 栈与队列第5章 数组和广义表第6章 树和二叉树第7章 查找第8章 图第9章 综合应用设计,第8章 图,8.1 图的基本知识8.2 图的存储结构8.3 图的遍历8.4 最小代价生成树8.5 最短路径,数据结构（Java版）叶核亚,8.1 图的基本知识,8.1.1 图的定义8.1.2 结点的度8.1.3 子图8.1.4 路径、回路及连通性,数据结构（Java版）叶核亚,8.1.1 图的定义,图（graph）是由结点集合及结点间的关系集合组成的一种数据结构。图中的结点又称为顶点，结点之间的关系称为边（edge）。一个图G记作G=(V,E)其中，V是结点x的有限集合，E是边的有限集合。即V=x|x某个数据元素集合E=(x,y)|x,yV 或 E=x,y|x,yV 其中，(x,y)表示从结点x到y的一条双向通路，即(x,y)没有方向；x,y表示从结点x到y的一条单向通路，即x,y是有方向的。,数据结构（Java版）叶核亚,数据结构（Java版）叶核亚,1无向图G1V(G1)=A,B,C,DE(G1)=(C,A),(C,A),(A,D),(A,D),(A,B),(C,B),(B,D)2有向图G2V(G3)=v1,v2,v3E(G3)=v1,v2,v2,v1,v2,v3,v3,v3,数据结构（Java版）叶核亚,3完全图,数据结构（Java版）叶核亚,4带权图5相邻结点,数据结构（Java版）叶核亚,8.1.2 结点的度,1度、入度、出度图中与结点v相关联的边的数目称为结点的度（degree），记作TD(v)。2度与边的关系,数据结构（Java版）叶核亚,8.1.3 子图,1子图、真子图2生成子图如果G是G的子图，且V=V，称图G是G的生成子图。,数据结构（Java版）叶核亚,8.1.4 路径、回路及连通性,1路径、路径长度、回路2有根的图、图的根3连通图4强连通图,数据结构（Java版）叶核亚,8.2 图的存储结构,8.2.1 邻接矩阵8.2.2 邻接表,数据结构（Java版）叶核亚,8.2.1 邻接矩阵,1邻接矩阵的定义2邻接矩阵与结点的度,数据结构（Java版）叶核亚,3带权图的邻接矩阵,数据结构（Java版）叶核亚,4声明以邻接矩阵存储的图类,public class Graph1 protected int n;/图的结点个数 protected int mat;/二维数组存储图的邻接矩阵,数据结构（Java版）叶核亚,8.2.2 邻接表,1无向图的邻接表,数据结构（Java版）叶核亚,2有向图的邻接表,数据结构（Java版）叶核亚,3声明以邻接表存储的图类,import ds_java.OnelinkNode;/单向链表的结点类public class Graph2/以邻接表存储的图类 private OnelinkNode table;/图的邻接表,数据结构（Java版）叶核亚,8.3 图的遍历,8.3.1 深度优先遍历8.3.2 广度优先遍历,数据结构（Java版）叶核亚,8.3.1 深度优先遍历,1深度优先遍历算法描述,数据结构（Java版）叶核亚,2以邻接矩阵存储的图的深度优先遍历算法实现,数据结构（Java版）叶核亚,【例8.1】以邻接矩阵表示的图的深度优先遍历算法测试。,数据结构（Java版）叶核亚,3以邻接表存储的图的深度优先遍历算法实现,数据结构（Java版）叶核亚,8.3.2 广度优先遍历,1广度优先遍历算法描述,数据结构（Java版）叶核亚,2以邻接矩阵存储的图的广度优先遍历算法实现,数据结构（Java版）叶核亚,3以邻接表存储的图的广度优先遍历算法实现,数据结构（Java版）叶核亚,8.4 最小代价生成树,8.4.1 树与图8.4.2 生成树8.4.3 最小代价生成树,数据结构（Java版）叶核亚,8.4.1 树与图,图8.11 树、森林与图,数据结构（Java版）叶核亚,【例8.2】以树结构描述测试假币的称重策略。,数据结构（Java版）叶核亚,8.4.2 生成树,1生成树的定义如果图T是无向图G的生成子图且T是树，则图T称为图G的生成树。,数据结构（Java版）叶核亚,2生成森林3带权图的生成树,数据结构（Java版）叶核亚,8.4.3 最小代价生成树,设G是一个连通的带权图，w(e)为边e上的权，T为G的生成树，那么T中各边权之和为上式称为生成树T的权，也称为生成树的代价（cost）。权最小的生成树称为最小生成树或最小代价生成树。,数据结构（Java版）叶核亚,1克鲁斯卡尔算法,数据结构（Java版）叶核亚,2普里姆算法,数据结构（Java版）叶核亚,8.5 最短路径,1单源最短路径,数据结构（Java版）叶核亚,2所有结点之间的最短路径,表8.2 最短路径表,数据结构（Java版）叶核亚,实习8,1实习目的：掌握图的概念、存储与遍历。2题意：以邻接表存储带权图，并对图进行遍历。,
