数据结构（数据结构（Java版）版）叶核亚叶核亚1数据结构（数据结构（Java版）版）第1章 绪论第2章 线性表第3章 排序第4章 栈与队列第5章 数组和广义表第6章 树和二叉树第7章 查找第8章 图第9章 综合应用设计2第8章 图8.1 图的基本知识8.2 图的存储结构8.3 图的遍历8.4 最小代价生成树8.5 最短路径38.1 图的基本知识n8.1.1 图的定义n8.1.2 结点的度n8.1.3 子图n8.1.4 路径、回路及连通性4数据结构（Java版）叶核亚8.1.1 图的定义n图（graph）是由结点集合及结点间的关系集合组成的一种数据结构。图中的结点又称为顶点，结点之间的关系称为边（edge）。一个图G记作G=(V, E)n其中，V是结点x的有限集合，E是边的有限集合。即V=x|x某个数据元素集合E=(x,y)|x,yV 或 E=x,y|x,yV n其中，(x,y)表示从结点x到y的一条双向通路，即(x,y)没有方向；x,y表示从结点x到y的一条单向通路，即x,y是有方向的。 5数据结构（Java版）叶核亚6数据结构（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, v37数据结构（Java版）叶核亚3完全图8数据结构（Java版）叶核亚4带权图5相邻结点9数据结构（Java版）叶核亚8.1.2 结点的度1度、入度、出度n图中与结点v相关联的边的数目称为结点的度（degree），记作TD(v)。 2度与边的关系10数据结构（Java版）叶核亚8.1.3 子图n1子图、真子图n2生成子图n如果G是G的子图，且V=V，称图G是G的生成子图。11数据结构（Java版）叶核亚8.1.4 路径、回路及连通性n1路径、路径长度、回路n2有根的图、图的根n3连通图n4强连通图12数据结构（Java版）叶核亚8.2 图的存储结构n8.2.1 邻接矩阵n8.2.2 邻接表13数据结构（Java版）叶核亚8.2.1 邻接矩阵1邻接矩阵的定义2邻接矩阵与结点的度14数据结构（Java版）叶核亚3带权图的邻接矩阵15数据结构（Java版）叶核亚4声明以邻接矩阵存储的图类public class Graph1 protected int n; /图的结点个数 protected int mat; /二维数组存储图的邻接矩阵16数据结构（Java版）叶核亚8.2.2 邻接表n1无向图的邻接表17数据结构（Java版）叶核亚2有向图的邻接表18数据结构（Java版）叶核亚3声明以邻接表存储的图类nimport ds_java.OnelinkNode; /单向链表的结点类npublic class Graph2 /以邻接表存储的图类nn private OnelinkNode table; /图的邻接表n19数据结构（Java版）叶核亚8.3 图的遍历n8.3.1 深度优先遍历n8.3.2 广度优先遍历20数据结构（Java版）叶核亚8.3.1 深度优先遍历n1深度优先遍历算法描述21数据结构（Java版）叶核亚2以邻接矩阵存储的图的深度优先遍历算法实现22数据结构（Java版）叶核亚【例8.1】 以邻接矩阵表示的图的深度优先遍历算法测试。23数据结构（Java版）叶核亚3以邻接表存储的图的深度优先遍历算法实现24数据结构（Java版）叶核亚8.3.2 广度优先遍历1广度优先遍历算法描述25数据结构（Java版）叶核亚2以邻接矩阵存储的图的广度优先遍历算法实现26数据结构（Java版）叶核亚3以邻接表存储的图的广度优先遍历算法实现27数据结构（Java版）叶核亚8.4 最小代价生成树n8.4.1 树与图n8.4.2 生成树n8.4.3 最小代价生成树28数据结构（Java版）叶核亚8.4.1 树与图图8.11 树、森林与图29数据结构（Java版）叶核亚【例8.2】 以树结构描述测试假币的称重策略。30数据结构（Java版）叶核亚8.4.2 生成树n1生成树的定义n如果图T是无向图G的生成子图且T是树，则图T称为图G的生成树。31数据结构（Java版）叶核亚n2生成森林n3带权图的生成树32数据结构（Java版）叶核亚8.4.3 最小代价生成树n设G是一个连通的带权图，w(e)为边e上的权，T为G的生成树，那么T中各边权之和为n上式称为生成树T的权，也称为生成树的代价（cost）。权最小的生成树称为最小生成树或最小代价生成树。33数据结构（Java版）叶核亚1克鲁斯卡尔算法34数据结构（Java版）叶核亚2普里姆算法35数据结构（Java版）叶核亚8.5 最短路径n1单源最短路径源 点终 点路 径路径长度最短路径v1v2(v1, v2)2(v1, v3, v2)12v 3(v1, v3)4(v1, v2, v3)10v 4(v1, v4)5(v1, v3, v4)10v 5(v1, v2, v5)11(v1, v3, v5)7(v1, v4, v5)1236数据结构（Java版）叶核亚2所有结点之间的最短路径表8.2 最短路径表源 点终 点最短路径路径长度v1v2(v1, v2)2v3(v1, v3)4v4(v1, v4)5v5(v1, v3, v5)7v2v3(v2, v1, v3)6v4(v2, v1, v4)7v5(v2, v5)9v3v4(v3, v4)6v5(v3, v5)3v4v5(v4, v5)737数据结构（Java版）叶核亚实习8n1实习目的：掌握图的概念、存储与遍历。n2题意：以邻接表存储带权图，并对图进行遍历。38数据结构（Java版）叶核亚