第8章图a.ppt

《第8章图a.ppt》由会员分享，可在线阅读，更多相关《第8章图a.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章 图图的基本概念图的基本概念图的存储结构图的存储结构图的遍历图的遍历最小生成树的概念(简单介绍)最小路径的概念(简单介绍)Chapter 8 Graph1/30/2023软件基础教案（第八章 图）8.1 图的基本概念1.1.图定义图定义图定义图定义 图是由结点集合图是由结点集合图是由结点集合图是由结点集合(vertex)及结点间的关系集合及结点间的关系集合及结点间的关系集合及结点间的关系集合组成的一种数据结构组成的一种数据结构组成的一种数据结构组成的一种数据结构：GraphGraph(V V,E E)其中其中其中其中 V V=x x|x x 某个数据元素集合某个数据元素集合某个数据元素集

2、合某个数据元素集合 是结点的有穷非空集合；是结点的有穷非空集合；是结点的有穷非空集合；是结点的有穷非空集合；E E=(=(x x,y y)|)|x x,y y V V 或或或或 E E=y|x x,y y V V&PathPath(x x,y y)是结点之间关系的有穷集合，也叫做边是结点之间关系的有穷集合，也叫做边是结点之间关系的有穷集合，也叫做边是结点之间关系的有穷集合，也叫做边(edge)(edge)集合。集合。集合。集合。PathPath(x x,y y)表示从表示从表示从表示从 x x 到到到到 y y 的一条单向通路的一条单向通路的一条单向通路的一条单向通路,它是有方向它是有方向它是

3、有方向它是有方向的。的。的。的。1/30/2023软件基础教案（第八章 图）有向图与无向图有向图与无向图 在有向图中，结点对在有向图中，结点对是是有序的。在无向图中，结点对有序的。在无向图中，结点对(x,y)是无序的。是无序的。子图子图 设有两个图设有两个图 G(V,E)和和 G(V,E)。若若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。邻接结点邻接结点 如果如果如果如果 (u u,v v)是是是是 E E(G)(G)中的一条边，则称中的一条边，则称中的一条边，则称中的一条边，则称 u u 与与与与 v v 互为邻接结点互为邻接结点互为邻接结点互为邻接结点。1/30

4、/2023软件基础教案（第八章 图）无无向图向图 G2ABCDEABDEAABCDABCDE无向图无向图G2的子图的子图ABCDAACDACABCD有向图有向图G1的子图的子图有向图有向图 G1有向图无向图及其子图：1/30/2023软件基础教案（第八章 图）n n权权 某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为权。这种称之为权。这种带权图叫做带权图叫做网络网络。完全图完全图 若有若有 n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 条边条边,则此图为完全无向图。则此图为完全无向图。有有 n 个顶点的有向图有个顶点的有向图有n(n-1)条边条边,则此图为完全有向图。则

5、此图为完全有向图。结点的度结点的度 一个顶点一个顶点v的度是与它相关联的边的条数。的度是与它相关联的边的条数。记作记作TD(v)。在有向图中在有向图中,顶点的度等于该顶点的入度顶点的度等于该顶点的入度(ID(v)与出度与出度(OD(v)之和。之和。TD(TD(v v)=ID(v)+OD(v)=ID(v)+OD(v)1/30/2023软件基础教案（第八章 图）例子例子例子例子1 1：162543abcdefTD(1)=3 TD(2)=3TD(3)=3 TD(4)=2TD(5)=2 TD(6)=1ID(a)=1 OD(a)=2 TD(a)=3 ID(b)=1 OD(b)=2 TD(b)=3ID(c

6、)=2 OD(c)=0 TD(c)=2 ID(d)=1 OD(d)=1 TD(d)=2ID(e)=0 OD(e)=1 TD(e)=1 ID(f)=1 OD(f)=0 TD(f)=11/30/2023软件基础教案（第八章 图）12356874107966712315163045ABDCE6035804075网网 络络例子例子例子例子2 2：1/30/2023软件基础教案（第八章 图）n n路径路径 在图在图 G(V,E)中中,若从顶点若从顶点 vi 出发出发,沿一沿一些边经过一些结点些边经过一些结点 vp1,vp2,vpm，到达顶点到达顶点vj。则称顶点序列则称顶点序列(vi vp1 vp2.v

7、pm vj)为从顶点为从顶点vi 到顶到顶点点 vj 的路径。的路径。它经过的边它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是属于应是属于E的边。的边。n n路径长度路径长度 uu非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。uu带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。1/30/2023软件基础教案（第八章 图）n n简单路径简单路径 若路径上各顶点若路径上各顶点 v1,v2,.,vm 均均不互相重复不互相重复,则称这样的路径为简单路径。则称这样的路径为简单路径。n n回路回路 若路径上第一个顶

8、点若路径上第一个顶点 v1 与最后一个顶与最后一个顶点点vm 重合重合,则称这样的路径为回路或环。则称这样的路径为回路或环。1/30/2023软件基础教案（第八章 图）n n连通图连通图在无向图中在无向图中,若从顶点若从顶点v1到顶点到顶点v2有路径有路径,则则称顶点称顶点v1与与v2是连通的。如果图中任意一对顶点都是是连通的。如果图中任意一对顶点都是连通的连通的,则称此图是则称此图是连通图连通图。n n强连通图强连通图在有向图中在有向图中,若对于每一对顶点若对于每一对顶点vi和和vj,都都存在一条从存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是强连则称此图是强连通图。通图

9、。1/30/2023软件基础教案（第八章 图）1345213452V=1,2,3,4,5E=(1,2),(1,3),(1,4),(2,4),(4,5)V=1,2,3,4,5E=,无向图无向图有向图有向图连通图连通图非连通图非连通图1345267H1连通分量H2连通分量例子例子例子例子3 3：1/30/2023软件基础教案（第八章 图）132强连通图非强连通图5134213425强连通分量H1强连通分量H2例子例子例子例子4 4：1/30/2023软件基础教案（第八章 图）n n生成树生成树 一个连通图的生成树是它的极小连通子图，一个连通图的生成树是它的极小连通子图，在在n个顶点的情形下，有个顶

10、点的情形下，有n-1条边。但有向图则可能得条边。但有向图则可能得到它的由若干有向树组成的生成森林。到它的由若干有向树组成的生成森林。n n本章不予讨论的图本章不予讨论的图1/30/2023软件基础教案（第八章 图）8.2 图的存储结构图的四种常用的存储形式：图的四种常用的存储形式：邻接矩阵和加权邻接矩阵（邻接矩阵和加权邻接矩阵（labeled adjacency matrix）邻接表邻接表十字链表十字链表(不讲不讲)邻接多重表（不讲）邻接多重表（不讲）一、邻接矩阵（静态存储方法）先决条件：若图G=（V，E）有确定个数的顶点！存储方法：顶点一维数组(V表示)邻接关系矩阵(A表示)1/30/202

11、3软件基础教案（第八章 图）n n设图设图 A=(V,E)是一个有是一个有 n 个顶点的图，则图的个顶点的图，则图的邻接矩阵是一个二维数组邻接矩阵是一个二维数组 A.edgenn，定义：定义：n n无向图的邻接矩阵是对称的，有向图的邻接矩无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。阵可能是不对称的。1/30/2023软件基础教案（第八章 图）1).无权值的无向图的邻接矩阵无权值的无向图的邻接矩阵 设无向图具有设无向图具有 n 个结点，则用个结点，则用 n 行行 n 列的布尔矩阵列的布尔矩阵 A 表示该无向图；表示该无向图；并且并且 Ai,j =1,如果如果i 至至 j 有一条无向

12、边；有一条无向边；AI,j=0如果如果 i 至至 j 没有一条无向边没有一条无向边。注意：注意：Ai,i =0。i结点的度结点的度:i行或行或i列之和。上三角矩阵或下三角矩阵列之和。上三角矩阵或下三角矩阵存储存储。表示成右图矩阵表示成右图矩阵ABCDEABCDE0 1 1 0 01 0 0 1 11 0 0 0 10 1 0 0 10 1 1 1 0A B C D E1/30/2023软件基础教案（第八章 图）ABCD2).无权值的有向图的邻接矩阵无权值的有向图的邻接矩阵 设有向图具有设有向图具有 n 个结点，则用个结点，则用 n 行行 n 列的布尔矩阵列的布尔矩阵 A 表示该有表示该有向图；

13、向图；如果如果i 至至 j 有一条有向边有一条有向边,Ai,j =1 ；如果；如果 i 至至 j 没有一条有向没有一条有向边边,Ai,j=0.注意：注意：Ai,i =0。出度出度:i行之和。入度行之和。入度:j列之和。列之和。表示成右图矩阵表示成右图矩阵0 1 1 00 0 0 00 0 0 11 0 0 0A B C DABCD1/30/2023软件基础教案（第八章 图）3).网络的邻接矩阵网络的邻接矩阵网络的邻接矩阵网络的邻接矩阵 ),(,),(.jijiEjiEjijijiWjiEdge=!=),(,),(.EjiEjijiWjiEdge 01/30/2023软件基础教案（第八章 图）0

14、123A.Edge=01324567A.Edge=V=0,1,2,3V=0,1,2,3,4,5,6,7例例1：1/30/2023软件基础教案（第八章 图）例例2：A B C D EABCDEVBEDCA208010704050例例3：1/30/2023软件基础教案（第八章 图）3.在无向图中在无向图中,统计第统计第 i i 行行(列列)1)1 的个的个数可得顶点数可得顶点i i 的度的度。4.4.在有向图中在有向图中,统计第统计第 i i 行行 1 1 的个数可得的个数可得顶点顶点 i i 的出度，统计第的出度，统计第 j j 列列 1 1 的个数可的个数可得顶点得顶点 j j 的入度。的入度

15、。5.5.属于静态存储方法。不易扩充。属于静态存储方法。不易扩充。6.6.与顶点个数有关，与边（弧）无关。会出与顶点个数有关，与边（弧）无关。会出 现稀疏矩阵。现稀疏矩阵。1.无向图的邻接矩阵是对称的，无向图的邻接矩阵是对称的，2.有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。邻接矩阵的特点：邻接矩阵的特点：1/30/2023软件基础教案（第八章 图）二.邻接表(Adjacency List)（动态存储方法）1 1）无向图的邻接表）无向图的邻接表）无向图的邻接表）无向图的邻接表 把同一个顶点发出的边链接在同一个边链表中，链把同一个顶点发出的边链接在同一个边链表中，链把同一个顶

16、点发出的边链接在同一个边链表中，链把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保表的每一个结点代表一条边，叫做边结点，结点中保表的每一个结点代表一条边，叫做边结点，结点中保表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点下标存有与该边相关联的另一顶点的顶点下标存有与该边相关联的另一顶点的顶点下标存有与该边相关联的另一顶点的顶点下标 destdest 和指向和指向和指向和指向同一链表中下一个边结点的指针同一链表中下一个边结点的指针同一链表中下一个边结点的指针同一链表中下一个边结点的指针 linklink。01231/30/

17、2023软件基础教案（第八章 图）2)2)有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表FF在有向图的邻接表中，第在有向图的邻接表中，第在有向图的邻接表中，第在有向图的邻接表中，第 i i 个边链表链接的边都是个边链表链接的边都是个边链表链接的边都是个边链表链接的边都是顶点顶点顶点顶点 i i 发发发发出的边出的边出的边出的边。也叫做。也叫做。也叫做。也叫做出边表出边表出边表出边表。FF在有向图的逆邻接表中，第在有向图的逆邻接表中，第在有向图的逆邻接表中，第在有向图的逆邻接表中，第 i i 个边链表链接的边都是个边链表链接的边都是个边链表链接的

18、边都是个边链表链接的边都是进入顶进入顶进入顶进入顶点点点点 i i 的边的边的边的边。也叫做。也叫做。也叫做。也叫做入边表入边表入边表入边表。1/30/2023软件基础教案（第八章 图）n n带权图的边结点中多保存该边上的权值带权图的边结点中多保存该边上的权值 cost。n n顶点顶点 i 的边链表的表头指针的边链表的表头指针 adj 在顶点表的下标为在顶点表的下标为 i 的顶点记录中，该记录还保存了该顶点的其它信息。的顶点记录中，该记录还保存了该顶点的其它信息。n n在邻接表的边链表中，在邻接表的边链表中，各个边结点的链入顺序任意，各个边结点的链入顺序任意，视边结点输入次序而定。视边结点输入

19、次序而定。n n设图中有设图中有 n 个顶点，个顶点，e 条边，则条边，则用邻接表表示无向图用邻接表表示无向图时时，需要，需要 n 个顶点结点，个顶点结点，2e 个边结点；用个边结点；用邻接表表示邻接表表示有向图时有向图时，若不考虑逆邻接表，只需，若不考虑逆邻接表，只需 n 个顶点结点，个顶点结点，e 个边结点。个边结点。1/30/2023软件基础教案（第八章 图）3)网络的邻接表BEDCA208010704050ABCDE012341 200 204503 702 800 800 703402101404100 501/30/2023软件基础教案（第八章 图）8.3 图的遍历图的两种常见的遍

20、历形式：图的两种常见的遍历形式：深度优先搜索深度优先搜索广度优先搜索广度优先搜索遍历的定义遍历的定义:从已给的连通图中某一顶点出发，沿从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做访问一次，就叫做图的遍历图的遍历(Graph Traversal)。1/30/2023软件基础教案（第八章 图）遍历遍历 的方法的方法:DFS DFS 在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点 v v 后，由后，由后，由后，由 v v 出发，访问出发，访问出发，访问出发，访问它的任

21、一邻接顶点它的任一邻接顶点它的任一邻接顶点它的任一邻接顶点 w w1 1；再从再从再从再从 w w1 1 出发，访问与出发，访问与出发，访问与出发，访问与 w w1 1邻邻邻邻 接但还接但还接但还接但还没有访问过的顶点没有访问过的顶点没有访问过的顶点没有访问过的顶点 w w2 2；然后再从然后再从然后再从然后再从 w w2 2 出发，进行类似的访出发，进行类似的访出发，进行类似的访出发，进行类似的访问，问，问，问，如此进行下去，直至到达所有的邻接顶点都被访问如此进行下去，直至到达所有的邻接顶点都被访问如此进行下去，直至到达所有的邻接顶点都被访问如此进行下去，直至到达所有的邻接顶点都被访问过的顶

22、点过的顶点过的顶点过的顶点 u u 为止。接着，退回一步，退到前一次刚访问过为止。接着，退回一步，退到前一次刚访问过为止。接着，退回一步，退到前一次刚访问过为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，的顶点，看是否还有其它没有被访问的邻接顶点。如果有，的顶点，看是否还有其它没有被访问的邻接顶点。如果有，的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的则访问此顶点，之后再从此顶点出发，进行与前述类似的则访问此顶点，之后再从此顶点出发，进行与前述类似的则访问此顶点，之后再从此顶点出发，进行与前述类

23、似的访问；如果没有，就再退回一步进行搜索。重复上述过程，访问；如果没有，就再退回一步进行搜索。重复上述过程，访问；如果没有，就再退回一步进行搜索。重复上述过程，访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。直到连通图中所有顶点都被访问过为止。直到连通图中所有顶点都被访问过为止。直到连通图中所有顶点都被访问过为止。1、深度优先搜索、深度优先搜索DFS(Depth First Search)1/30/2023软件基础教案（第八章 图）vv深度优先搜索的示例深度优先搜索的示例深度优先搜索的示例深度优先搜索的示例1 1 深度优先搜索过程深度优先搜索过程深度优先

24、搜索过程深度优先搜索过程 深度优先生成树深度优先生成树深度优先生成树深度优先生成树vv深度优先搜索的示例深度优先搜索的示例深度优先搜索的示例深度优先搜索的示例2 2 有向图的实例有向图的实例：为了说明问题，邻接结点的访问次序以序号：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。如：结点为准。序号小的先访问。如：结点 5 的邻接结点有两个的邻接结点有两个 6、7，则先访问结点则先访问结点 6，再访问结点，再访问结点 7。1/30/2023软件基础教案（第八章 图）56724135672314从结点从结点 出发的搜索序列：出发的搜索序列：5、6、2、3、1、4、7适用的数据结构：适用

25、的数据结构：栈栈51243从结点从结点 出发的搜索序列：出发的搜索序列：1、2、3、4没有搜索没有搜索 到所有的结点，必到所有的结点，必 须另选图中未访须另选图中未访 问过的结点，问过的结点，继续进行继续进行 搜索。搜索。11/30/2023软件基础教案（第八章 图）2.广度优先搜索广度优先搜索BFS(Breadth First Search)vv使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点 v 之后，之后，由由 v 出发，依次访问出发，依次访问 v 的各个未曾被访问过的的各个未曾被访问过的邻接顶点邻接顶点 w1,w2,wt，然后再顺序访问，然后再顺序访问 w1,w2,wt

26、 的所有还未被访问过的邻接顶点。的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，有还未被访问过的邻接顶点，如此做下去，如此做下去，直到图中所有顶点都被访问到为止。直到图中所有顶点都被访问到为止。1/30/2023软件基础教案（第八章 图）2.广度优先搜索广度优先搜索BFS(Breadth First Search)vv 广度优先搜索的示例广度优先搜索的示例广度优先搜索的示例广度优先搜索的示例1 1 广度优先搜索过程广度优先搜索过程广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树广度优先生成树广

27、度优先生成树1/30/2023软件基础教案（第八章 图）广度优先搜索是一种分层的搜索过程，每向前走一步广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，的情况。因此，广度优先搜索不是一个递归的过程，其算法也其算法也不是递归不是递归的。的。1/30/2023软件基础教案（第八章 图）vv广度优先搜索的示例广度优先搜索的示例广度优先搜索的示例广度优先搜索的示例2 2 无向图的实例：为了说明问题，邻接结点的访问次序以序号为无向图的实例：为了说明问题，邻接结点的访问次序

28、以序号为准。序号小的先访问。如：结点准。序号小的先访问。如：结点 1 的邻接结点有三个的邻接结点有三个 2、12、11，则先访问结点，则先访问结点 2、11，再访问结点，再访问结点 12。121211367104589121211367104589图的广度优先的访问次序：图的广度优先的访问次序：1、2、11、12、3、6、7、10、4、5、8、9 适用的数据结构：适用的数据结构：队列队列1/30/2023软件基础教案（第八章 图）8.3最小生成树(minimum cost spanning tree)使用使用使用使用不同的遍历图的方法不同的遍历图的方法不同的遍历图的方法不同的遍历图的方法，可以

29、得到，可以得到，可以得到，可以得到不同的生成树不同的生成树不同的生成树不同的生成树；从；从；从；从不同的顶点出发不同的顶点出发不同的顶点出发不同的顶点出发，也可能得到，也可能得到，也可能得到，也可能得到不同的生成树不同的生成树不同的生成树不同的生成树。按照生成树的定义，按照生成树的定义，按照生成树的定义，按照生成树的定义，n n 个顶点的连通网络的生成树有个顶点的连通网络的生成树有个顶点的连通网络的生成树有个顶点的连通网络的生成树有 n n 个顶点、个顶点、个顶点、个顶点、n-n-1 1 条边。条边。条边。条边。构造最小生成树的构造最小生成树的构造最小生成树的构造最小生成树的准则准则准则准则:

30、必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；必须使用且仅使用必须使用且仅使用必须使用且仅使用必须使用且仅使用 n n-1 1 条边来联结网络中的条边来联结网络中的条边来联结网络中的条边来联结网络中的 n n 个顶点；个顶点；个顶点；个顶点；不能使用产生回路的边。不能使用产生回路的边。不能使用产生回路的边。不能使用产生回路的边。最小生成树：最小生成树：所有生成树中，边的权值总和最小。所有生成树中，边的权值总和最小。1/30/2023软件基础教案（第八章 图）8.4最短路径(Shortest Path)最短路径问题最短路径问题(概念概念)：如果从图中某一顶如果从图中某一顶点点(称为源点称为源点)到达另一顶点到达另一顶点(称为终点称为终点)的的路径可能不止一条，如何找到一条路径使路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。得沿此路径上各边上的权值总和达到最小。1/30/2023软件基础教案（第八章 图）