资源描述：
《java数据结构第8章图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《数据结构（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记
2、作G=(V,E)其中，V是结点x的有限集合，E是边的有限集合。即V={x
3、x∈某个数据元素集合}E={(x,y)
4、x,y∈V}或E={〈x,y〉
5、x,y∈V}其中，(x,y)表示从结点x到y的一条双向通路，即(x,y)没有方向；〈x,y〉表示从结点x到y的一条单向通路，即〈x,y〉是有方向的。《数据结构（Java版）》叶核亚《数据结构（Java版）》叶核亚1．无向图G1V(G1)={A,B,C,D}E(G1)={(C,A),(C,A),(A,D),(A,D),(A,B),(C,B),(B,D)}2．有向图G2V(G3)={v1,v2,v3}E(G3)={〈v1,v2〉,
6、〈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．强连通图《数据结构（Jav
7、a版）》叶核亚8.2图的存储结构8.2.1邻接矩阵8.2.2邻接表《数据结构（Java版）》叶核亚8.2.1邻接矩阵1．邻接矩阵的定义2．邻接矩阵与结点的度《数据结构（Java版）》叶核亚3．带权图的邻接矩阵《数据结构（Java版）》叶核亚4．声明以邻接矩阵存储的图类publicclassGraph1{protectedintn;//图的结点个数protectedintmat[][];//二维数组存储图的邻接矩阵}《数据结构（Java版）》叶核亚8.2.2邻接表1．无向图的邻接表《数据结构（Java版）》叶核亚2．有向图的邻接表《数据结构（Java版）》叶核亚3．声明以
8、邻接表存储的图类importds_java.OnelinkNode;//单向链表的结点类publicclassGraph2//以邻接表存储的图类{privateOnelinkNodetable[];//图的邻接表}《数据结构（Java版）》叶核亚8.3图的遍历8.3.1深度优先遍历8.3.2广度优先遍历《数据结构（Java版）》叶核亚8.3.1深度优先遍历1．深度优先遍历算法描述《数据结构（Java版）》叶核亚2．以邻接矩阵存储的图的深度优先遍历算法实现《数据结构（Java版）》叶核亚【例8.1】以邻接矩阵表示的图的深度优先遍历算法测试。《数据结构（Java版）》叶核亚
9、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．
10、生成树的定义如果图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．单源最短路径源点终点路径
