第07章图(Java版)

1、数据结构（Java版）（第3版）第第7章章 图图l7.1 图及其抽象数据类型图及其抽象数据类型l7.2 图的表示和实现图的表示和实现l7.3 图的遍历图的遍历l7.4 最小生成树最小生成树l7.5 最短路径最短路径数据结构（Java版）（第3版）目的和要求目的和要求 目的：目的：学习非线性的复杂数据结构学习非线性的复杂数据结构图。图。 内容：内容：图的概念、抽象数据类型、存储结构；图图的概念、抽象数据类型、存储结构；图 的深度和广度优先搜索遍历；最小生成树；的深度和广度优先搜索遍历；最小生成树； 最短路径。最短路径。 要求：要求：掌握图的存储结构和操作实现。掌握图的存储结构和操作实现。 重点：

2、重点：图的两种存储结构，两种遍历算法，最小图的两种存储结构，两种遍历算法，最小 生成树，最短路径。生成树，最短路径。 难点：难点：图的存储和操作实现，最小生成树，最短图的存储和操作实现，最小生成树，最短 路径。路径。 实验：实验：图的建立与遍历，最小代价生成图的建立与遍历，最小代价生成 树，最短路径。树，最短路径。数据结构（Java版）（第3版）7.1 图及其抽象数据类型图及其抽象数据类型 7.1.1 图的基本概念图的基本概念1. 图的定义和术语图的定义和术语 G=(V, E) V= vi | vi 某个数据元素集合某个数据元素集合E= (vi , vj) | vi ,vjV 或或 E = v

3、i , vj|vi ,vjV且且Path(vi , vj) 无向图无向图 有向图有向图 数据结构（Java版）（第3版）多重图和带自身环的图多重图和带自身环的图 数据结构（Java版）（第3版） 完全图完全图 带权图带权图 邻接顶点邻接顶点 1. 图的定义和术语图的定义和术语 数据结构（Java版）（第3版）2.顶点的度顶点的度 无向图无向图 有向图有向图degree()=indegree()outdegree() niive1)(degree21evvniinii11)(outdegree)(indegreeevvvniiniinii2)(outdegree)(indegree)(degre

4、e111数据结构（Java版）（第3版）3.子图子图数据结构（Java版）（第3版）4.路径路径 5.连通性连通性数据结构（Java版）（第3版）7.1.2 图抽象数据类型图抽象数据类型public interface GGraph /图接口图接口 int vertexCount(); /返回顶点数返回顶点数 T get(int i); /返回顶点返回顶点vi元素元素 int getWeight(int i, int j); /返回边的权值返回边的权值 int insertVertex(T x); /插入顶点插入顶点 void insertEdge(int i, int j, int weig

5、ht);/插入边插入边 void removeVertex(int v); /删除顶点删除顶点 void removeEdge(int i, int j); /删除边删除边 int getNextNeighbor(int v, int w); /返回下一个邻返回下一个邻接顶点接顶点 数据结构（Java版）（第3版）7.2 图的表示和实现图的表示和实现7.2.1 图的邻接矩阵表示和实现图的邻接矩阵表示和实现7.2.2 图的邻接表表示和实现图的邻接表表示和实现7.2.3 图的邻接多重表表示图的邻接多重表表示数据结构（Java版）（第3版）7.2.1 图的邻接矩阵表示和实现图的邻接矩阵表示和实现1.

6、 邻接矩阵邻接矩阵 （1）不带权图的邻接矩阵）不带权图的邻接矩阵EvvEvvEvvEvvajijijijiij,),(0,),(1或若或若EDCBAV0110010111110100110101010A数据结构（Java版）（第3版）（2）带权图的邻接矩阵）带权图的邻接矩阵jijijijijijijiijijvvEvvEvvvvEvvEvvvvwa若或且若或且若0,),(,),(数据结构（Java版）（第3版）2.邻接矩阵表示的带权图类邻接矩阵表示的带权图类（1）带权值的边类）带权值的边类public class Edge implements Comparable public int st

7、art,dest,weight; /边的起点序号、终点序号和权值边的起点序号、终点序号和权值数据结构（Java版）（第3版）（2）邻接矩阵表示的带权图类）邻接矩阵表示的带权图类public class AdjMatrixGraph SeqList vertexlist; /顺序表存储图的顶点集合顺序表存储图的顶点集合 int adjmatrix; /图的邻接矩阵图的邻接矩阵 final int MAX_WEIGHT = 99999; /最大权值（表示无穷大最大权值（表示无穷大）数据结构（Java版）（第3版）（2）邻接矩阵表示的带权图类）邻接矩阵表示的带权图类顶点集合顶点集合A,B,C,D,E

8、; 边集合边集合 (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);数据结构（Java版）（第3版）（3）图的插入操作）图的插入操作数据结构（Java版）（第3版）（4）图的删除操作）图的删除操作例例7.1 带权无向图的邻接矩阵表示及操作。带权无向图的邻接矩阵表示及操作。 数据结构（Java版）（第3版）7.2.2 图的邻接表表示和实现图的邻接表表示和实现1. 邻接表邻接表（1）无向图的邻接表表示）

9、无向图的邻接表表示 数据结构（Java版）（第3版）（2）有向图的邻接表表示）有向图的邻接表表示数据结构（Java版）（第3版）2.邻接表表示的带权图类邻接表表示的带权图类（1）顶点表元素类）顶点表元素类public class Vertex T data; /顶点数据域顶点数据域 SortedSinglyLinkedList adjlink; /该顶点的边单链表该顶点的边单链表（2）邻接表表示的带权图类）邻接表表示的带权图类public class AdjListGraph SeqListVertex vertexlist; /顶点顺序表顶点顺序表数据结构（Java版）（第3版）图图7-20

10、 带权无向图的邻接表存储结构带权无向图的邻接表存储结构 数据结构（Java版）（第3版）（3）图的插入操作）图的插入操作数据结构（Java版）（第3版）（4）图的删除操作）图的删除操作例例7.2 带权有向图的构造、插入及删除操作。带权有向图的构造、插入及删除操作。数据结构（Java版）（第3版）7.2.3 图的邻接多重表表示图的邻接多重表表示 1. 无向图的邻接多重表表示无向图的邻接多重表表示 数据结构（Java版）（第3版）2. 有向图的邻接多重表表示有向图的邻接多重表表示 数据结构（Java版）（第3版）7.3 图的遍历图的遍历7.3.1 图的深度优先搜索遍历图的深度优先搜索遍历7.3.2

11、 图的广度优先搜索遍历图的广度优先搜索遍历数据结构（Java版）（第3版）7.3.1 图的深度优先搜索遍历图的深度优先搜索遍历DFS策略，访问某个顶点策略，访问某个顶点 ，寻找的一个邻接顶点，寻找的一个邻接顶点 访问访问 ，反复执行，走过一条较长路径到达最远顶，反复执行，走过一条较长路径到达最远顶点；若顶点没有未被访问的其他邻接顶点，则退回到点；若顶点没有未被访问的其他邻接顶点，则退回到前一个被访问顶点，再寻找其他访问路径。前一个被访问顶点，再寻找其他访问路径。ivjv数据结构（Java版）（第3版）抽象图类抽象图类 public abstract class AbstractGraph im

12、plements GGraph abstract int vertexCount(); /返回顶点数返回顶点数 abstract T get(int i); /返回顶点的数据域返回顶点的数据域 abstract int getNextNeighbor(int i, int j); void DFSTraverse(int i) /深度优先搜索遍历深度优先搜索遍历 void BFSTraverse(int i) /广度优先搜索遍历广度优先搜索遍历数据结构（Java版）（第3版）图接口、抽象图类和图类的层次图接口、抽象图类和图类的层次关系关系 数据结构（Java版）（第3版）邻接矩阵表示的图的遍历

13、邻接矩阵表示的图的遍历 /邻接矩阵表示的图类，继承抽象图类邻接矩阵表示的图类，继承抽象图类public class AdjMatrixGraph extends AbstractGraph int vertexCount() /返回顶点数，前已实现返回顶点数，前已实现 T get(int i) /返回顶点数据元素返回顶点数据元素 int getNextNeighbor(int i, int j) /返回在后的下一个邻接顶点序号返回在后的下一个邻接顶点序号数据结构（Java版）（第3版）邻接表表示的图的遍历邻接表表示的图的遍历 /邻接表表示的图类，继承抽象图类邻接表表示的图类，继承抽象图类pub

14、lic class AdjListGraph extends AbstractGraph int vertexCount() /返回顶点数，前已实现返回顶点数，前已实现 T get(int i) /返回顶点数据元素返回顶点数据元素 int getNextNeighbor(int i, int j) /返回在后的下一个邻接顶点序号返回在后的下一个邻接顶点序号数据结构（Java版）（第3版）7.3.2 图的广度优先搜索遍历图的广度优先搜索遍历BFS策略，访问某个顶点策略，访问某个顶点 ，接着依次访问所有未被访问，接着依次访问所有未被访问的邻接顶点的邻接顶点 ，再依次访问，再依次访问 顶点的顶点的所

15、有未被访问的其他邻接顶点，如此反复执行，直到访问所有未被访问的其他邻接顶点，如此反复执行，直到访问完图中所有顶点。完图中所有顶点。ivtkjvvv,tkjvvv,数据结构（Java版）（第3版）7.4 最小生成树最小生成树7.4.1 生成树生成树1. 树树 数据结构（Java版）（第3版）2. 生成树和生成森林生成树和生成森林数据结构（Java版）（第3版）3. 最小生成树最小生成树数据结构（Java版）（第3版）7.4.2 最小生成树的构造算法最小生成树的构造算法1. Prim算法算法 数据结构（Java版）（第3版）2.Kruskal算法算法 数据结构（Java版）（第3版）当图中有相同权

16、值的边时，最小当图中有相同权值的边时，最小生成树不唯一生成树不唯一 数据结构（Java版）（第3版）7.5 最短路径最短路径7.5.1 非负权值的单源最短路径非负权值的单源最短路径（Dijkstra算法）算法） 7.5.2 每对顶点间的最短路径每对顶点间的最短路径（Floyd算法）算法）数据结构（Java版）（第3版）7.5.1 非负权值的单源最短路非负权值的单源最短路径（径（Dijkstra算法）算法） 数据结构（Java版）（第3版）表表7-1 求以求以A为源点的最短路径为源点的最短路径 源源点点终终点点最短路径及其长度变化最短路径及其长度变化AB(A,B) 10C (A,B,C) 60

17、(A,D,C) 50D(A,D) 30E(A,E) 99(A,D,E) 90(A,D,C,E) 60数据结构（Java版）（第3版）7.5.2 每对顶点间的最短路径每对顶点间的最短路径（Floyd算法）算法） 1. 最短路径及其长度矩阵最短路径及其长度矩阵 jijijijijiijijvvvvvvvvvvdistd若没有路径到且从顶点若有路径到且从顶点若0其他或且若序号经过的最后一个顶点最短路径1,),(),(EvvEvvvvkvvvvpjijijikjkiij其他或且若序号经过的最后一个顶点最短路径1,),(),(EvvEvvvvkvvvvpjijijikjkiij数据结构（Java版）（第

18、3版）图图7-37 带权有向图及其最短路带权有向图及其最短路径长度矩阵和最短路径矩阵径长度矩阵和最短路径矩阵 DCBAV049382290473120110423627160D1103210321132101P),(),(),(),(),(),(),(),(),(),(),(),(),(),(),(),(DDCBADBADADDCCCBADCADCDCBCBBBADCBDCBACBABAAA 数据结构（Java版）（第3版）2. Floyd算法描述算法描述 D的初值是邻接矩阵；的初值是邻接矩阵； 迭代，每条路径迭代，每条路径 增加一个中间顶点增加一个中间顶点 if ( ) ; /用经过顶点的更

19、短路径长度替换用经过顶点的更短路径长度替换 ; / 经过的最后一个顶点，经过的最后一个顶点，替换为替换为 经过的最后一个顶点经过的最后一个顶点 以图以图G中每个顶点作为其他路径的中间顶点，对每中每个顶点作为其他路径的中间顶点，对每条路径进行上述迭代。条路径进行上述迭代。 ijkjikdddkjikijdddkvkjijpp ),(jivv ),(jkvv kv),(jivv 数据结构（Java版）（第3版）以以A作为其他边的中间顶点，调整作为其他边的中间顶点，调整D和和P矩阵矩阵 7G0793822905539431106557160D1003210211110001P),(),(),(),(),(),(),(),(),(),(),(),(),(),(),(),(DDCADBADADDCCCBACACDBCBBBABDACABAAA数据结构（Java版）（第3版）以以B作为其他边的中间顶点，调整作为其他边的中间顶点，调整D和和P矩阵矩阵 7G0493822905539431105927160D1103210211