第八章 图(精品).ppt

《第八章 图(精品).ppt》由会员分享，可在线阅读，更多相关《第八章 图(精品).ppt（38页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第八章图第八章图8.1 概述概述8.2 图的存储结构图的存储结构8.3 邻接矩阵图类邻接矩阵图类8.4 图的遍历图的遍历8.5 最小生成树最小生成树8.6 最短路径最短路径本章主要知识点：本章主要知识点：图的基本概念图的基本概念图的存储结构，主要是邻接矩阵存储结构和邻图的存储结构，主要是邻接矩阵存储结构和邻接表存接表存 储结构储结构图的遍历，主要是深度优先算法和广度优先遍图的遍历，主要是深度优先算法和广度优先遍历算法历算法最小生成树的基本概念，以及普里姆算法和克最小生成树的基本概念，以及普里姆算法和克鲁斯卡尔算法鲁斯卡尔算法最短路径的基本概念，狄克斯特拉算法思想最短路径的基本概念，狄克斯特拉算

2、法思想 8.1 概述概述8.1.1 图的基本概念图的基本概念 图图 是由结点集合及结点间的关系集合组成是由结点集合及结点间的关系集合组成的一种数据结构。的一种数据结构。结点和边结点和边 图中的顶点称作结点，图中的第图中的顶点称作结点，图中的第i个结点记做个结点记做vi。有向图有向图 在有向图中，结点对在有向图中，结点对x,y是有是有序的，结点对序的，结点对x,y称为从结点称为从结点x到结点到结点y的一的一条有向边，因此，条有向边，因此，x,y与与y,x是两条不是两条不同的边。有向图中的结点对同的边。有向图中的结点对x,y用一对尖括用一对尖括号括起来，号括起来，x是有向边的始点，是有向边的始点，

3、y是有向边的终是有向边的终点，有向图中的边也称作弧点，有向图中的边也称作弧.无向图无向图 在无向图中，结点对（在无向图中，结点对（x,y）是无序）是无序的，结点对（的，结点对（x,y）称为与结点）称为与结点x和结点和结点y相关联相关联的一条边。（的一条边。（x,y）等价于）等价于x,y和和y,x。完全图完全图 在有在有n个结点的无向图中，若有个结点的无向图中，若有n(n-1)/2条边，即任意两个结点之间有且只有一条边，则称此条边，即任意两个结点之间有且只有一条边，则称此图为无向完全图。在有图为无向完全图。在有n个结点的有向图中，若有个结点的有向图中，若有n(n-1)条边，即任意两个结点之间有且

4、只有方向相反的两条边，即任意两个结点之间有且只有方向相反的两条边，则称此图为有向完全图。条边，则称此图为有向完全图。邻接结点邻接结点 在无向图在无向图G中，若（中，若（u,v）是）是E(G)中的一条边，则称中的一条边，则称u和和v互为邻接结点，并称边互为邻接结点，并称边（u,v）依附于结点）依附于结点u和和v。在有向图在有向图G中，若中，若u,v是是E(G)中的一条边，则称结点中的一条边，则称结点u邻接到结邻接到结点点v，结点，结点v邻接自结点邻接自结点u，并称边，并称边u,v和结和结点点u和结点和结点v相关联。相关联。结点的度结点的度 结点结点v的度是与它相关联的边的的度是与它相关联的边的条

5、数，记作条数，记作TD(v)。路径路径 在图在图G=(V,E)中，若从结点中，若从结点vi出发有一出发有一组边使可到达结点组边使可到达结点vj，则称结点，则称结点vi到结点到结点vj的的结点序列为从结点结点序列为从结点vi到结点到结点vj的路径的路径 权权 有些图的边附带有数据信息，这些附带的数据信息有些图的边附带有数据信息，这些附带的数据信息称为权。第称为权。第i条边的权用符号条边的权用符号wi表示。表示。路径长度路径长度 对于不带权的图，一条路径的路径长度是指该对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是路径上的边的条数；对于带权的图，一条路

6、径的路径长度是指该路径上各个边权值的总指该路径上各个边权值的总和和。子图子图 设有图设有图G1=V1,E1和图和图G2=V2,E2，若，若V2V1且且E2E1，则称图，则称图G2是图是图G1的子图。的子图。连通图和强连通图连通图和强连通图 在无向图中，若从结点在无向图中，若从结点vi到结点到结点vj有路径，有路径，则称结点则称结点vi和结点和结点vj是连通的。如果图中任意一对结点都是连通是连通的。如果图中任意一对结点都是连通的，则称该图是连通图。在有向图中，若对于任意一对结点的，则称该图是连通图。在有向图中，若对于任意一对结点vi和结点和结点vj（vivj）都存在路径，则称图）都存在路径，则称

7、图G是强连通图。是强连通图。生成树生成树 一个连通图的最小连通子图称作该一个连通图的最小连通子图称作该图的生成树。有图的生成树。有n个结点的连通图的生成树有个结点的连通图的生成树有n个结点和个结点和n-1条边。条边。简单路径和回路简单路径和回路 若路径上各结点若路径上各结点v1,v2,vm,互不重复，则称这样的路径为简单互不重复，则称这样的路径为简单路径；若路径上第一个结点路径；若路径上第一个结点v1与最后一个结点与最后一个结点vm重合，则称这样的路径为回路或环。重合，则称这样的路径为回路或环。8.1.2 8.1.2 图的抽象数据类型图的抽象数据类型 数据集合数据集合：由一组结点集合：由一组结

8、点集合vi和一组边和一组边ej集合组成。当集合组成。当为带权图时每条边上权为带权图时每条边上权wj还构成权集合还构成权集合wj。操作集合操作集合：（1）初始化）初始化initiate(n)：（2）插入结点）插入结点 insertVertex(vertex)：（3）插入边）插入边insertEdge(v1,v2,weight)：（4）删除边）删除边deleteEdge(v1,v2)：（5）删除结点）删除结点deleteVertex(vertex)：（6）第一个邻接结点）第一个邻接结点getFirstVex(v)：（7）下一个邻接结点）下一个邻接结点getNextVex(int v1,v2)：（8

9、）遍历）遍历depthFirstSearch(vs)：8.2 图的存储结构图的存储结构8.2.1 图的邻接矩阵存储结构图的邻接矩阵存储结构 假设图假设图G=(V,E)有有n个结点，即个结点，即V=v0,v1,vn-1，E可用可用如下形式的矩阵如下形式的矩阵A描述，对于描述，对于A中的每一个元素中的每一个元素aij，满，满足：足：由于矩阵由于矩阵A中的元素中的元素aij表示了结点表示了结点vi和结点和结点vj之间边的之间边的关系，或者说，关系，或者说，A中的元素中的元素aij表示了结点表示了结点vi和结点和结点vj（0jn-1）的邻接关系，所以矩阵）的邻接关系，所以矩阵A称作称作邻接矩阵邻接矩阵

10、。无向图及其邻接矩阵无向图及其邻接矩阵 有向图及其邻接矩阵有向图及其邻接矩阵带权图及其邻接矩阵带权图及其邻接矩阵 8.2.2 图的邻接表存储结构图的邻接表存储结构 图的邻接矩阵存储结构的主要特点是把图的边信息存图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个储在一个nn矩阵中，其中矩阵中，其中n为图中的结点个数。为图中的结点个数。有向图的邻接表存储结构有向图的邻接表存储结构 8.3 邻接矩阵图类邻接矩阵图类 1邻接矩阵图类邻接矩阵图类AdjMWGraph的设计的设计2邻接矩阵图类邻接矩阵图类AdjMWGraph的测试的测试 8.4 图的遍历图的遍历 8.4.1 图的深度和广度优先遍历算法

11、图的深度和广度优先遍历算法 图的遍历算法设计需要考虑三个问题：图的遍历算法设计需要考虑三个问题：（1）图的特点是没有首尾之分，所以算法的参数要指）图的特点是没有首尾之分，所以算法的参数要指定访问的第一个结点；定访问的第一个结点；（2）对图的遍历路径有可能构成一个回路，从而造成）对图的遍历路径有可能构成一个回路，从而造成死循环，所以算法设计要考虑遍历路径可能出现的死死循环，所以算法设计要考虑遍历路径可能出现的死循环问题；循环问题；（3）一个结点可能和若干个结点都是邻接结点，要使）一个结点可能和若干个结点都是邻接结点，要使一个结点的所有邻接结点按照某种次序被访问。一个结点的所有邻接结点按照某种次序

12、被访问。1 图的深度优先遍历算法图的深度优先遍历算法 连通图的深度优先遍历递归算法为：连通图的深度优先遍历递归算法为：（1）访问结点）访问结点v并标记结点并标记结点v为已访问；为已访问；（2）查找结点）查找结点v的第一个邻接结点的第一个邻接结点w；（3）若结点）若结点v的邻接结点的邻接结点w存在，则继续执行，否则算法存在，则继续执行，否则算法结束；结束；（4）若结点）若结点w尚未被访问则深度优先搜索递归访问结点尚未被访问则深度优先搜索递归访问结点w；（5）查找结点）查找结点v的的w邻接结点的下一个邻接结点邻接结点的下一个邻接结点w，转到，转到步骤（步骤（3）。）。2 图的广度优先遍历算法图的广

13、度优先遍历算法 连通图的广度优先遍历算法为：连通图的广度优先遍历算法为：（1）访问初始结点）访问初始结点v并标记结点并标记结点v为已访问；为已访问；（2）结点）结点v入队列；入队列；（3）当队列非空时则继续执行，否则算法结束；）当队列非空时则继续执行，否则算法结束；（4）出队列取得队头结点）出队列取得队头结点u；（5）查找结点）查找结点u的第一个邻接结点的第一个邻接结点w；（6）若结点）若结点u的邻接结点的邻接结点w不存在，则转到步骤（不存在，则转到步骤（3），否则循环执），否则循环执行，行，（6.1）若结点）若结点w尚未被访问，则访问结点尚未被访问，则访问结点w，并标记结点，并标记结点w为已

14、访为已访问；问；（6.2）结点）结点w入队列；入队列；（6.3）查找结点）查找结点u的的w邻接结点后的下一个邻接结点邻接结点后的下一个邻接结点w，转到步骤，转到步骤（6）。）。3 非连通图的遍历非连通图的遍历 对于连通图，从图的任意一个结点开始深度或广度优对于连通图，从图的任意一个结点开始深度或广度优先遍历，一定可以访问图中的所有结点。但对于非连先遍历，一定可以访问图中的所有结点。但对于非连通图，从图的任意一个结点开始深度或广度优先遍历，通图，从图的任意一个结点开始深度或广度优先遍历，并不能访问图中的所有结点。对于非连通图，从图的并不能访问图中的所有结点。对于非连通图，从图的任意一个结点开始深

15、度或广度优先遍历只能访问和初任意一个结点开始深度或广度优先遍历只能访问和初始结点连通的所有结点。始结点连通的所有结点。8.4.2 图的深度和广度优先遍历成员函数设计图的深度和广度优先遍历成员函数设计1 访问结点访问结点2 深度和广度优先遍历成员函数设计深度和广度优先遍历成员函数设计3 测试程序测试程序8.5 最小生成树最小生成树8.5.1 最小生成树的基本概念最小生成树的基本概念 一个有一个有n个结点的连通图的个结点的连通图的生成树生成树是原图的极小连通子是原图的极小连通子图，它包含原图中的所有图，它包含原图中的所有n个结点，并且有保持图连通个结点，并且有保持图连通的最少的边。的最少的边。如果

16、无向连通图是一个带权图，那么它的所有生成树如果无向连通图是一个带权图，那么它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵中必有一棵边的权值总和最小的生成树，我们称这棵生成树为生成树为最小代价生成树最小代价生成树，简称，简称最小生成树最小生成树。无向图和它的不同的生成树无向图和它的不同的生成树 从最小生成树的定义可知，构造有从最小生成树的定义可知，构造有n个结点的无向连通个结点的无向连通带权图的最小生成树带权图的最小生成树,必须满足以下三条：必须满足以下三条：（1）构造的最小生成树必须包括）构造的最小生成树必须包括n个结点；个结点；（2）构造的最小生成树中有且只有）构造的最小生成树

17、中有且只有n-1条边；条边；（3）构造的最小生成树中不存在回路。）构造的最小生成树中不存在回路。构造最小生成树的方法有许多种，典型的构造方法有构造最小生成树的方法有许多种，典型的构造方法有两种，一种称作两种，一种称作普里姆普里姆（Prim）算法，另一种称作）算法，另一种称作克克鲁斯卡尔鲁斯卡尔（Kruskal）算法。）算法。8.5.2普里姆算法普里姆算法1 普里姆算法思想普里姆算法思想 假设假设G=(V,E)为一个带权图，其中为一个带权图，其中V为带权图中结点的集合，为带权图中结点的集合，E为带权图中边的权值集合。设置两个新的集合为带权图中边的权值集合。设置两个新的集合U和和T，其中，其中U用

18、于存放带权图用于存放带权图G的最小生成树的结点的集合，的最小生成树的结点的集合，T用于存放用于存放带权图带权图G的最小生成树的权值的集合。的最小生成树的权值的集合。普里姆算法思想普里姆算法思想是：令集合是：令集合U的初值为的初值为U=u0（即假设构造（即假设构造最小生成树时从结点最小生成树时从结点u0开始），集合开始），集合T的初值为的初值为T=。从所。从所有结点有结点uU和结点和结点vV-U的带权边中选出具有最小权值的的带权边中选出具有最小权值的边边(u,v)，将结点，将结点v加入集合加入集合U中，将边中，将边(u,v)加入集合加入集合T中。中。如此不断重复，当如此不断重复，当U=V时则最小

19、生成树构造完毕。此时集合时则最小生成树构造完毕。此时集合U中存放着最小生成树结点的集合，集合中存放着最小生成树结点的集合，集合T中存放着最小生中存放着最小生成树边的权值集合。成树边的权值集合。普里姆算法构造最小生成树的过程普里姆算法构造最小生成树的过程2 普里姆函数设计普里姆函数设计 这里我们令当弧头结点等于弧尾结点时权值等于这里我们令当弧头结点等于弧尾结点时权值等于0。函数的参数设计：函数的参数设计：普里姆函数应有两个参数：普里姆函数应有两个参数：一个参数是图一个参数是图g，这里图，这里图g定义为邻接矩阵存储结构图定义为邻接矩阵存储结构图类的对象；类的对象；另一个参数是通过函数得到的最小生成

20、树的结点数据另一个参数是通过函数得到的最小生成树的结点数据和相应结点的边的权值数据和相应结点的边的权值数据closeVertex。普里姆算法运行时数组普里姆算法运行时数组lowCost的变化过程的变化过程 8.5.3 克鲁斯卡尔算法克鲁斯卡尔算法 克鲁斯卡尔克鲁斯卡尔算法是：设无向连通带权图算法是：设无向连通带权图G=(V,E)，其中，其中V为为结点的集合，结点的集合，E为边的集合。设带权图为边的集合。设带权图G的最小生成树的最小生成树T由由结点集合和边的集合构成，其初值为结点集合和边的集合构成，其初值为T=(V,)，即初始时最，即初始时最小生成树小生成树T只由带权图只由带权图G中的结点集合组

21、成，各结点之间没中的结点集合组成，各结点之间没有一条边。这样，最小生成树有一条边。这样，最小生成树T中的各个结点各自构成一个中的各个结点各自构成一个连通分量。然后，按照边的权值递增的顺序考察带权图连通分量。然后，按照边的权值递增的顺序考察带权图G中中的边集合的边集合E中的各条边。若被考察的边的两个结点属于中的各条边。若被考察的边的两个结点属于T的的两个不同的连通分量，则将此边加入到最小生成树两个不同的连通分量，则将此边加入到最小生成树T，同时，同时把两个连通分量连接为一个连通分量；若被考察的边的两把两个连通分量连接为一个连通分量；若被考察的边的两个结点属于个结点属于T的同一个连通分量，则将此边

22、舍去。如此下去，的同一个连通分量，则将此边舍去。如此下去，当当T中的连通分量个数为中的连通分量个数为1时，时，T中的该连通分量即为带权图中的该连通分量即为带权图G的一棵最小生成树。的一棵最小生成树。克鲁斯卡尔算法构造最小生成树的过程克鲁斯卡尔算法构造最小生成树的过程 8.6 最短路径最短路径8.6.1 最短路径的基本概念最短路径的基本概念 在一个图中，若从一个结点到另一个结点在一个图中，若从一个结点到另一个结点存在着路径，定义存在着路径，定义路径长度路径长度为一条路径上所经为一条路径上所经过的边的数目。图中从一个结点到另一个结点过的边的数目。图中从一个结点到另一个结点可能存在着多条路径，我们把

23、路径长度最短的可能存在着多条路径，我们把路径长度最短的那条路径叫做那条路径叫做最短路径最短路径，其路径长度叫做，其路径长度叫做最短最短路径路径长度或长度或最短距离最短距离.在一个带权图中，若从一个结点到另一个在一个带权图中，若从一个结点到另一个结点存在着一条路径，则称该路径上所经过边结点存在着一条路径，则称该路径上所经过边的权值之和为该路径上的的权值之和为该路径上的带权路径长度带权路径长度。带权。带权图中从一个结点到另一个结点可能存在着多条图中从一个结点到另一个结点可能存在着多条路径，我们把带权路径长度值最小的那条路径路径，我们把带权路径长度值最小的那条路径也叫做也叫做最短路径最短路径，其带权

24、路径长度也叫做，其带权路径长度也叫做最短最短路径长度路径长度或或最短距离最短距离。8.6.2 从一个点到其余各结点的最点路径从一个点到其余各结点的最点路径 1 狄克斯特拉算法思想狄克斯特拉算法思想 狄克斯特拉算法狄克斯特拉算法是：设置两个结点的集合是：设置两个结点的集合S和和T，集合，集合S中存放已找到最短路径的结点，集合中存放已找到最短路径的结点，集合T中存放当前还未找到中存放当前还未找到最短路径的结点。初始状态时，集合最短路径的结点。初始状态时，集合S中只包含源点，设为中只包含源点，设为v0，然后从集合，然后从集合T中选择到源点中选择到源点v0路径长度最短的结点路径长度最短的结点u加加入到

25、集合入到集合S中，集合中，集合S中每加入一个新的结点中每加入一个新的结点u都要修改源点都要修改源点v0到集合到集合T中剩余结点的当前最短路径长度值，集合中剩余结点的当前最短路径长度值，集合T中各中各结点的新的当前最短路径长度值，为原来的当前最短路径结点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过结点长度值与从源点过结点u到达该结点的路径长度中的较小者。到达该结点的路径长度中的较小者。此过程不断重复，直到集合此过程不断重复，直到集合T中的结点全部加入到集合中的结点全部加入到集合S 中中为止。为止。下图为意示例：下图为意示例：8.6.3 每对结点之间的最短路径每对结点之间的最短路

26、径 弗洛伊德算法是：设矩阵弗洛伊德算法是：设矩阵cost用来存放带权有向图用来存放带权有向图G的权值，即矩阵的权值，即矩阵元素元素costij中存放着下标为中存放着下标为i的结点到下标为的结点到下标为j的结点之间的权值，的结点之间的权值，可以通过递推构造一个矩阵序列可以通过递推构造一个矩阵序列A0,A1,A2,AN来求每对结点之来求每对结点之间的最短路径。初始时有，间的最短路径。初始时有，A0ij=costij。当已经求出。当已经求出Ak,要递要递推求解推求解Ak+1时，可分两种情况来考虑：一种情况是该路径不经过下时，可分两种情况来考虑：一种情况是该路径不经过下标为标为k+1的结点，此时该路径

27、长度与从结点的结点，此时该路径长度与从结点vi到结点到结点vj的路径上所经的路径上所经过的结点下标不大于过的结点下标不大于k的最短路径长度相同；另一种情况是该路径的最短路径长度相同；另一种情况是该路径经过下标为经过下标为k+1的结点，此时该路径可分为两段，一段是从结点的结点，此时该路径可分为两段，一段是从结点vi到结点到结点vk+1的最短路径，另一段是从结点的最短路径，另一段是从结点vk+1到结点到结点vj的最短路径，的最短路径，此时的最短路径长度等于这两段最短路径长度之和。这两种情况中此时的最短路径长度等于这两段最短路径长度之和。这两种情况中的路径长度较小者，就是要求的从结点的路径长度较小者

28、，就是要求的从结点vi到结点到结点vj的路径上所经过的路径上所经过的结点下标不大于的结点下标不大于k+1的最短路径长度。的最短路径长度。弗洛伊德算法的算法思想可用如下递推公式描述：弗洛伊德算法的算法思想可用如下递推公式描述：A0ij=costij Ak+1ij=minAkij,Akik+1+Akk+1j （0kn-1）也就是说，初始时，也就是说，初始时，A0ij=costij，然后进行递推，然后进行递推，每递推一次，从结点每递推一次，从结点vi到结点到结点vj的最短路径上就多考虑的最短路径上就多考虑了一个经过的中间结点，这样，经过了一个经过的中间结点，这样，经过n次递推后得到的次递推后得到的Anij就是考虑了经过图中所有结点情况下的从结点就是考虑了经过图中所有结点情况下的从结点vi到结点到结点vj的最短路径长度。的最短路径长度。