《数据结构第5章刘震图文.pptx》由会员分享，可在线阅读，更多相关《数据结构第5章刘震图文.pptx（111页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、$5.1图图的基本概念1有向图无向图第1页/共111页$4.1图图的基本概念1有向图 G=G=（V V，AA）其中，其中，V V为顶点的有穷非空集合为顶点的有穷非空集合AA为顶点之间的关系集合为顶点之间的关系集合G1=G1=（V V，AA）V=v1,v2,v3,v4V=v1,v2,v3,v4A=,A=,其中其中表示从表示从x x到到y y的一条弧（的一条弧（arcarc），），A A为弧集合，为弧集合，x x为弧尾为弧尾（tailtail），），y y为弧头（为弧头（head)head)G1第2页/共111页$5.1图图的基本概念1无向图 G=G=（V V，EE）其中其中,V,V同有向图，同有
2、向图，EE为顶点之间的关系集合，为顶点之间的关系集合，E E为边集合为边集合G2=G2=（V V，AA）V=v1,v2,v3,v4,v5V=v1,v2,v3,v4,v5E=(v1,v2),(v1,v4),v2,v3),(v3,v4),(v2,v5),(v3,v5)E=(v1,v2),(v1,v4),v2,v3),(v3,v4),(v2,v5),(v3,v5)其中，其中，(x,y)(x,y)表示表示x x与与y y之间的一条连线，称为边（之间的一条连线，称为边（edgeedge）G2 第3页/共111页$5.1图图的基本概念1图的顶点数为n,边数为e,请找出n与e的关系设设设设n n n n为顶
3、点数，为顶点数，为顶点数，为顶点数，e e e e为边或弧的条数为边或弧的条数为边或弧的条数为边或弧的条数对对对对无向图无向图无向图无向图有：有：有：有：0=e=n(n-1)/20=e=n(n-1)/20=e=n(n-1)/20=e=n(n-1)/2有向图有向图有向图有向图有：有：有：有：0=e=n(n-1)0=e=n(n-1)0=e=n(n-1)0=e=n(n-1)第4页/共111页$5.1图图的基本概念2完全图完全图完全图完全图:边达到最大的图边达到最大的图边达到最大的图边达到最大的图 无向完全图：边数为无向完全图：边数为无向完全图：边数为无向完全图：边数为n(n-1)/2n(n-1)/2
4、n(n-1)/2n(n-1)/2的无向图的无向图的无向图的无向图 有向完全图：弧数为有向完全图：弧数为有向完全图：弧数为有向完全图：弧数为n(n-1)n(n-1)n(n-1)n(n-1)的有向图的有向图的有向图的有向图 权：与图的边或弧相关的数权：与图的边或弧相关的数权：与图的边或弧相关的数权：与图的边或弧相关的数 网：边或弧上带有权值的图网：边或弧上带有权值的图网：边或弧上带有权值的图网：边或弧上带有权值的图第5页/共111页$5.1图图的基本概念3顶点的度顶点的度 TDTD（V V）无向图：无向图：无向图：无向图：为依附于顶点为依附于顶点为依附于顶点为依附于顶点V V V V的边数的边数的
5、边数的边数有向图：有向图：有向图：有向图：等于以顶点等于以顶点等于以顶点等于以顶点V V V V为弧头的弧数（称为为弧头的弧数（称为为弧头的弧数（称为为弧头的弧数（称为V V V V的入度，记为的入度，记为的入度，记为的入度，记为IDIDIDID（V V V V）与以顶点与以顶点与以顶点与以顶点V V V V为弧尾的弧的出度，记为为弧尾的弧的出度，记为为弧尾的弧的出度，记为为弧尾的弧的出度，记为ODODODOD（V V V V）之和。即：）之和。即：）之和。即：）之和。即：TDTDTDTD（V V V V）=ID=ID=ID=ID（V V V V）+OD+OD+OD+OD（V V V V）无向
6、图无向图无向图无向图 e=1/2e=1/2（TD(vTD(vi i)）i=1i=1结论：结论：有向图有向图有向图有向图 n nn n e=e=ID(vID(vi i)=)=OD(vOD(vi i)i=1 i=1i=1 i=1无向图的度数为依附于顶点无向图的度数为依附于顶点v v的边数；有向图的度数等于以的边数；有向图的度数等于以顶点顶点v v 为弧头的弧数与以顶点为弧头的弧数与以顶点v v为弧尾的弧数之和为弧尾的弧数之和第6页/共111页$5.1图图的基本概念4-路径无向图：无向图：无向图：无向图：顶点顶点顶点顶点v v v v到到到到v v v v 的路径是一个顶点序列（的路径是一个顶点序列
7、（的路径是一个顶点序列（的路径是一个顶点序列（v=vv=vv=vv=vi0i0i0i0,v,v,v,vi1i1i1i1,v,v,v,vimimimim=v=v=v=v）其中，（其中，（其中，（其中，（v v v vij-1ij-1ij-1ij-1,v,v,v,vij ij ij ij）E,1=j=mE,1=j=mE,1=j=mE,1=j=m有向图：有向图：有向图：有向图：顶点顶点顶点顶点v v v v 到到到到v v v v 的路径是有向的顶点序列的路径是有向的顶点序列的路径是有向的顶点序列的路径是有向的顶点序列（v=vv=vv=vv=vi0i0i0i0,v,v,v,vi1i1i1i1,v,v
8、,v,vim=im=im=im=v v v v）其中，其中，其中，其中，vvvA,1=jA,1=jA,1=jA,1=j=m几个概念：几个概念：几个概念：几个概念：路径长度：路径上边或弧的数目路径长度：路径上边或弧的数目路径长度：路径上边或弧的数目路径长度：路径上边或弧的数目回路或环：首尾顶点相同的路径，称为回路或环。即：回路或环：首尾顶点相同的路径，称为回路或环。即：回路或环：首尾顶点相同的路径，称为回路或环。即：回路或环：首尾顶点相同的路径，称为回路或环。即：（v=vv=vv=vv=vi0i0i0i0,v,v,v,vi1i1i1i1,v,v,v,vimimimim=v=v=v=v=v=v=v
9、=v）简单路径：路径中不含相同顶点的路径简单路径：路径中不含相同顶点的路径简单路径：路径中不含相同顶点的路径简单路径：路径中不含相同顶点的路径简单回路：除首尾顶点外，路径中不含相同顶点的回路简单回路：除首尾顶点外，路径中不含相同顶点的回路简单回路：除首尾顶点外，路径中不含相同顶点的回路简单回路：除首尾顶点外，路径中不含相同顶点的回路第7页/共111页$5.1图图的基本概念5-连通顶点连通顶点连通顶点连通顶点连通：若顶点若顶点若顶点若顶点v v v v到顶点到顶点到顶点到顶点v v v v 有路径，则称顶点有路径，则称顶点有路径，则称顶点有路径，则称顶点v v v v与与与与v v v v 是连
10、通的是连通的是连通的是连通的连连连连 通通通通 图图图图 ：包括无向连通图和有向连通图包括无向连通图和有向连通图包括无向连通图和有向连通图包括无向连通图和有向连通图 无向图无向图无向图无向图：若图中任意两个顶点若图中任意两个顶点若图中任意两个顶点若图中任意两个顶点v v v vi i i i,v,v,v,vj j j j都是连通的，则称该图是连通图都是连通的，则称该图是连通图都是连通的，则称该图是连通图都是连通的，则称该图是连通图(v v v vi i i ivvvvj j j j)有向图：若图中任意两个顶点有向图：若图中任意两个顶点有向图：若图中任意两个顶点有向图：若图中任意两个顶点v v
11、v vi i i i,v,v,v,vj j j j，都存在从，都存在从，都存在从，都存在从vivivivi到到到到vjvjvjvj和从和从和从和从v v v vj j j j到到到到v v v vi i i i的路径，的路径，的路径，的路径，则称该有向图为强连通图则称该有向图为强连通图则称该有向图为强连通图则称该有向图为强连通图(v v v vi i i ivvvvj j j j)连通分量：连通分量：连通分量：连通分量：无向图：无向图中极大连通子图，称为连通分量无向图：无向图中极大连通子图，称为连通分量无向图：无向图中极大连通子图，称为连通分量无向图：无向图中极大连通子图，称为连通分量 有向图
12、：有向图中极大强连通子图，称为强连通分量有向图：有向图中极大强连通子图，称为强连通分量有向图：有向图中极大强连通子图，称为强连通分量有向图：有向图中极大强连通子图，称为强连通分量第8页/共111页G1G1有两个强连通分量有两个强连通分量有两个强连通分量有两个强连通分量G1$5.1图图的基本概念5-连通第9页/共111页定义：定义：定义：定义：设无向图设无向图设无向图设无向图G G G G是含有是含有是含有是含有n n n n个顶点的连通图，个顶点的连通图，个顶点的连通图，个顶点的连通图，则图则图则图则图G G G G的生成树是含有的生成树是含有的生成树是含有的生成树是含有n n n n 个顶点
13、，且只有个顶点，且只有个顶点，且只有个顶点，且只有n-1n-1n-1n-1条边的连通子图条边的连通子图条边的连通子图条边的连通子图 三要素：三要素：三要素：三要素：n n n n个顶点个顶点个顶点个顶点 n-1n-1n-1n-1条边条边条边条边 连通连通连通连通 生成树生成树生成树生成树n-1n-1n-1n-1条边条边条边条边$5.1图图的基本概念6-生成树第10页/共111页$5.1图图的基本概念7-子图子图是图的一部分，它本身也是一子图是图的一部分，它本身也是一个图。如果有图个图。如果有图G=(VG=(V，E)E)和和G=(V,E)G=(V,E)，且且VV是是V V的子集，的子集，EE是是
14、E E的子集，则的子集，则称称GG是是G G的子图。图的子图。图4-14-1实际上是中国实际上是中国铁路交通图的一个子图。铁路交通图的一个子图。第11页/共111页$5.1图图的基本概念8-邻接顶点 邻接顶点邻接顶点 在无向图中，若两个顶点之间有边连接，则这两个顶在无向图中，若两个顶点之间有边连接，则这两个顶点互为邻接顶点点互为邻接顶点 第12页/共111页$4.2图图的存储回忆:天然气管道铺设问题中,需要存储社区房屋和商店信息,相互之间是否有通路及管道长度三个信息.即使部分问题不牵涉管道长度(图的权值),也至少需要存储图的顶点和边的两方面信息,如何存储?仍然有顺序存储和链式存储仍然有顺序存储
15、和链式存储2 2种方法种方法!第13页/共111页$4.2图图的存储1-邻接矩阵一、数组表示法（邻接矩阵）一、数组表示法（邻接矩阵）一、数组表示法（邻接矩阵）一、数组表示法（邻接矩阵）设图设图G=G=（V V，EE）有）有n n个顶点，则个顶点，则G G的邻接矩阵定义为的邻接矩阵定义为n n阶方阵阶方阵A A。其中：其中：例如：例如：例如：例如：G1G1G1G1、G2G2G2G2的邻接矩阵的邻接矩阵的邻接矩阵的邻接矩阵第14页/共111页邻接矩阵的特点：邻接矩阵的特点：邻接矩阵的特点：邻接矩阵的特点：1.1.1.1.判定两个顶点判定两个顶点判定两个顶点判定两个顶点ViViViVi与与与与VjV
16、jVjVj是否关联是否关联是否关联是否关联,只需判只需判只需判只需判Ai,jAi,jAi,jAi,j是否为是否为是否为是否为1 1 1 1；2.2.2.2.求顶点的度容易求顶点的度容易求顶点的度容易求顶点的度容易:有向图中：有向图中：有向图中：有向图中：TD(Vi)=OD(Vi)+ID(Vi)TD(Vi)=OD(Vi)+ID(Vi)n nn n =Ai,j+Ai,j+Aj,iAj,i j j=1 j=11 j=1 n nn n 无向图中：无向图中：无向图中：无向图中：TD(Vi)=TD(Vi)=Ai,j=Ai,j=Aj,iAj,i j j=1 =1 j j=1=1 即顶点即顶点即顶点即顶点Vi
17、ViViVi的度等于邻接矩阵中第的度等于邻接矩阵中第的度等于邻接矩阵中第的度等于邻接矩阵中第i i i i行（或第行（或第行（或第行（或第i i i i列）的元素之和（非列）的元素之和（非列）的元素之和（非列）的元素之和（非0 0 0 0元素个数）。元素个数）。元素个数）。元素个数）。即顶点即顶点即顶点即顶点ViViViVi的出度为邻接矩阵中第的出度为邻接矩阵中第的出度为邻接矩阵中第的出度为邻接矩阵中第i i i i行元素之和行元素之和行元素之和行元素之和 顶点顶点顶点顶点ViViViVi的入度为邻接矩阵中第的入度为邻接矩阵中第的入度为邻接矩阵中第的入度为邻接矩阵中第i i i i列元素之和列
18、元素之和列元素之和列元素之和第15页/共111页$4.2图图的存储1-邻接矩阵如果如果G G是带权图，是带权图，w wijij是边（是边（v vi i,v,vj j）或）或v 的权，则其邻接的权，则其邻接矩阵定义为：矩阵定义为：第16页/共111页$4.2图图的存储1-邻接矩阵请采用邻接矩阵存储右图数据答:设G=房屋1,房屋2,房屋3,商场14个顶点,则邻接矩阵为第17页/共111页$4.2图图的存储2-邻接表1.1.1.1.无向图邻接表无向图邻接表无向图邻接表无向图邻接表对图中每个顶点对图中每个顶点对图中每个顶点对图中每个顶点ViViViVi建立一个单链表，链表中的结点表示依附于顶点建立一个
19、单链表，链表中的结点表示依附于顶点建立一个单链表，链表中的结点表示依附于顶点建立一个单链表，链表中的结点表示依附于顶点ViViViVi的的的的边，每个链表结点为两个域：边，每个链表结点为两个域：边，每个链表结点为两个域：边，每个链表结点为两个域：其中：邻接点域（其中：邻接点域（其中：邻接点域（其中：邻接点域（adjvexadjvexadjvexadjvex）记载与顶点）记载与顶点）记载与顶点）记载与顶点ViViViVi邻接的顶点信息；邻接的顶点信息；邻接的顶点信息；邻接的顶点信息；链域（链域（链域（链域（nextarcnextarcnextarcnextarc）指向下一个与顶点）指向下一个与顶
20、点）指向下一个与顶点）指向下一个与顶点ViViViVi邻接的链表结点邻接的链表结点邻接的链表结点邻接的链表结点每个链表附设一个头结点，头结点结构为：每个链表附设一个头结点，头结点结构为：每个链表附设一个头结点，头结点结构为：每个链表附设一个头结点，头结点结构为：vexdatafirstarc其中：其中：其中：其中：vexdatavexdatavexdatavexdata存放顶点信息（姓名、编号等）存放顶点信息（姓名、编号等）存放顶点信息（姓名、编号等）存放顶点信息（姓名、编号等）；fristarcfristarcfristarcfristarc指向链表的第一个结点。指向链表的第一个结点。指向链
21、表的第一个结点。指向链表的第一个结点。adjvexnextarc第18页/共111页$4.2图图的存储2-邻接表如图如图如图如图G2G2G2G2的邻接表为：的邻接表为：的邻接表为：的邻接表为：1234525341543533412212无向图邻接表特点：无向图邻接表特点：1.n1.n个顶点，个顶点，e e条条边边的的无无向图，向图，需需n n个头结点和个头结点和2e2e个链表结点个链表结点2.2.顶点顶点ViVi的度的度 TDTD（ViVi）=链表链表i i中的链表结点数中的链表结点数G2 第19页/共111页2.2.2.2.有向图邻接表有向图邻接表有向图邻接表有向图邻接表与无向图的邻接表结构
22、一样。只是在第与无向图的邻接表结构一样。只是在第与无向图的邻接表结构一样。只是在第与无向图的邻接表结构一样。只是在第i i i i条链表上的结点是以条链表上的结点是以条链表上的结点是以条链表上的结点是以ViViViVi为为为为弧尾的各个弧头顶点弧尾的各个弧头顶点弧尾的各个弧头顶点弧尾的各个弧头顶点123423414312有向图邻接表特点：有向图邻接表特点：1.n1.n个顶点，个顶点，e e条弧的有向图，需条弧的有向图，需n n个表头结点，个表头结点，e e 个链表结点个链表结点2.2.第第i i条链表上的链表结点数，为条链表上的链表结点数，为ViVi的出度的出度(求顶点的出度求顶点的出度 易，
23、求入度难）易，求入度难）G1G1G1G1的邻接表的邻接表的邻接表的邻接表G1G1G1G1$4.2图图的存储2-邻接表第20页/共111页3.3.3.3.有向图逆邻接表有向图逆邻接表有向图逆邻接表有向图逆邻接表与无向图的邻接表结构一样。只是在第与无向图的邻接表结构一样。只是在第与无向图的邻接表结构一样。只是在第与无向图的邻接表结构一样。只是在第i i i i条链表上的结点是以条链表上的结点是以条链表上的结点是以条链表上的结点是以ViViViVi为为为为弧头的各个弧尾顶点弧头的各个弧尾顶点弧头的各个弧尾顶点弧头的各个弧尾顶点12342341143此时，第此时，第i i条链表上的结点数，为条链表上的
24、结点数，为ViVi的入度的入度G1G1G1G1的逆邻接表的逆邻接表的逆邻接表的逆邻接表G1G1G1G1$4.2图图的存储2-邻接表第21页/共111页$4.2图图的存储3十字链表（orthogonal list）十字链表是将有向图的邻接表和逆邻接表结合起来的一种十字链表是将有向图的邻接表和逆邻接表结合起来的一种十字链表是将有向图的邻接表和逆邻接表结合起来的一种十字链表是将有向图的邻接表和逆邻接表结合起来的一种有向图链式存储结构有向图链式存储结构有向图链式存储结构有向图链式存储结构有向图的每一条弧有一个弧结点，每一个顶点有一个顶点结点，有向图的每一条弧有一个弧结点，每一个顶点有一个顶点结点，有向
25、图的每一条弧有一个弧结点，每一个顶点有一个顶点结点，有向图的每一条弧有一个弧结点，每一个顶点有一个顶点结点，其结构为：其结构为：其结构为：其结构为：data:data:存放顶点的有关信息存放顶点的有关信息 (如顶点的名称，或位置）如顶点的名称，或位置）firstin:firstin:指向以该顶点为弧头的指向以该顶点为弧头的 第一个弧结点；第一个弧结点；firstout:firstout:指向以该顶点为弧尾指向以该顶点为弧尾 的第一个弧结点。的第一个弧结点。顶点结点顶点结点弧结点弧结点tailvex headvex hlinktlinkdatafirstin firstouttailvex:ta
26、ilvex:指示该弧的弧尾顶点；指示该弧的弧尾顶点；headvex:headvex:指示该弧的弧头顶点；指示该弧的弧头顶点；hlink:hlink:指向弧头相同的下一条弧；指向弧头相同的下一条弧；tlink:tlink:指向弧尾相同的下一条弧指向弧尾相同的下一条弧第22页/共111页2.2.2.2.整体结构整体结构整体结构整体结构 通过通过通过通过hlinkhlinkhlinkhlink将将将将弧头相同弧头相同弧头相同弧头相同的弧连在一个链表上；的弧连在一个链表上；的弧连在一个链表上；的弧连在一个链表上；通过通过通过通过tlinktlinktlinktlink将将将将弧尾相同弧尾相同弧尾相同弧
27、尾相同的弧连在一个链表上的弧连在一个链表上的弧连在一个链表上的弧连在一个链表上 而而而而hlinkhlinkhlinkhlink链和链和链和链和tlinktlinktlinktlink链的头结点就是链的头结点就是链的头结点就是链的头结点就是顶点结点顶点结点顶点结点顶点结点e34e41e13e12123412134134G1G1G1G1$4.2图图的存储3十字链表（orthogonal list）第23页/共111页$4.2图图的存储3十字链表（orthogonal list）4.4.十字链表的特点：十字链表的特点：顶点结点数顶点结点数=顶点数顶点数 弧结点数弧结点数=弧的条数弧的条数 求入度：
28、从顶点求入度：从顶点ViVi的的firstinfirstin出发，沿着弧结点中的出发，沿着弧结点中的hlinkhlink所所经过的弧结点数。经过的弧结点数。求出度：从顶点求出度：从顶点ViVi的的firstoutfirstout出发，沿着弧结点中的出发，沿着弧结点中的tlinktlink所经过的弧结点数。所经过的弧结点数。第24页/共111页$4.2图图的存储4-邻接多重表邻接多重表是无向图的另一种链式存储结构。邻接多重表是无向图的另一种链式存储结构。图的每一条边有一个边结点，边结点的结构为：图的每一条边有一个边结点，边结点的结构为：ivexilink jvexjlink每一个顶点有一个顶点结
29、点，顶点结点结构为：每一个顶点有一个顶点结点，顶点结点结构为：datafirstedge其中：其中：ivex ivex 和和jvexjvex为该边所依附的两个顶点。为该边所依附的两个顶点。ilinkilink指向下一条依附于顶点指向下一条依附于顶点ivexivex的边。的边。jlinkjlink指向下一条依附于顶点指向下一条依附于顶点jvex jvex 的边。的边。datadata存放顶点的信息。存放顶点的信息。firstedgefirstedge指向第一条依附于该顶点的边结点。指向第一条依附于该顶点的边结点。第25页/共111页$4.2图图的存储4-邻接多重表如图如图如图如图G2G2G2G2
30、的邻接多重表的邻接多重表的邻接多重表的邻接多重表:G2 25341123252143435邻接多重表特点：邻接多重表特点：1.1.顶点结点数为顶点结点数为n n，边结点数为，边结点数为e e2.2.对需要得到边的两个顶点的一类操作很方便对需要得到边的两个顶点的一类操作很方便 （如删除一条边，判一条边是否已访问）（如删除一条边，判一条边是否已访问）第26页/共111页$4.3图图的遍历 怎么知道图的顶点都被访问了怎么知道图的顶点都被访问了?怎么知道没有重复访问怎么知道没有重复访问?第27页/共111页$4.3图图的遍历从图中某个顶点出发，沿路径使图中从图中某个顶点出发，沿路径使图中每个顶点被每个
31、顶点被访问且仅被访问一次访问且仅被访问一次的过程，称为的过程，称为遍历图遍历图。两种常用遍历图的方法两种常用遍历图的方法两种常用遍历图的方法两种常用遍历图的方法 深度优先搜索深度优先搜索广度优先搜索广度优先搜索第28页/共111页$4.3图图的遍历一、深度优先搜索（一、深度优先搜索（depth-first-search)depth-first-search)1.1.深度优先搜索法遍历图的过程为：深度优先搜索法遍历图的过程为：1).1).访问指定的某顶点访问指定的某顶点V V，将，将V V作为当前顶点作为当前顶点2).2).访问当前顶点的下一未被访问过的邻接点，并将该顶点作为当前顶点访问当前顶点
32、的下一未被访问过的邻接点，并将该顶点作为当前顶点3).3).重复重复2 2，直到当前顶点的所有邻接点都被访问过，直到当前顶点的所有邻接点都被访问过4).4).沿搜索路径回退，退到尚有邻接点未被访问过的某结点，将该结点沿搜索路径回退，退到尚有邻接点未被访问过的某结点，将该结点作为当前结点，重复作为当前结点，重复2 2，直到所有顶点被访问过的为止，直到所有顶点被访问过的为止第29页/共111页$4.3图图的遍历如图如图如图如图G4G4G4G4：V1V1V2V2V3V3V4V4V5V5V6V6V7V7V8V8深到底深到底回退回退深到底深到底V1V2V4V8V5（V2V8V2V8均已访问）均已访问）深
33、到底深到底V3V6V7V3V6V7回退回退访问访问第30页/共111页$4.3图图的遍历 怎么写程序实现深度优先遍历怎么写程序实现深度优先遍历?可以采用递归和非递归可以采用递归和非递归2 2种方法种方法 实现相同的深度优先遍历算法实现相同的深度优先遍历算法!第31页/共111页$4.3图图的遍历算法算法4.1 4.1 从顶点从顶点v0v0出发深度优先遍历出发深度优先遍历g g中能访问的各个顶点中能访问的各个顶点void dfs(int v0)void dfs(int v0)visitedv0=1;/*visitedv0=1;/*访问标志置为访问标志置为 1 1，表示已被访问，表示已被访问*/w
34、=firstadj(g,v0);/*w w=firstadj(g,v0);/*w是是vovo的第一个邻接点的第一个邻接点*/while(w!=0)while(w!=0)if(visitedw=0)dfs(w);/*if(visitedw=0)dfs(w);/*顶点未被访问，则递归的进行深度遍历顶点未被访问，则递归的进行深度遍历*/w=nextadj(g,v0,w)/*w=nextadj(g,v0,w)/*顶点已访问，则取顶点顶点已访问，则取顶点v0v0在在w w后面的下一个邻接点后面的下一个邻接点*/深度优先遍历的递归算法深度优先遍历的递归算法:第32页/共111页$4.3图图的遍历几点说明：
35、几点说明：几点说明：几点说明：1.visited1.n1.visited1.n是一个辅助数组，记载顶点是否被访问过是一个辅助数组，记载顶点是否被访问过visitedVi=visitedVi=1,1,已访问过已访问过0,0,未访问过（初值）未访问过（初值）2.2.firstadj(g,V0)firstadj(g,V0)和和nextadj(g,V0,w)nextadj(g,V0,w)两个两个函数的实现与图的具体函数的实现与图的具体存储结构有关存储结构有关第33页/共111页$4.3图图的遍历算法算法4.2 4.2 图的深度优先遍历算法图的深度优先遍历算法void travergraph(g)/*v
36、oid travergraph(g)/*对图对图g g进行深度优先遍历进行深度优先遍历*/for(i=1;i=n;i+)visitedi=0;/*for(i=1;i=n;i+)visitedi=0;/*标志数组初始化标志数组初始化*/for(i=1;i=n;i+)for(i=1;i=n;i+)if(visitedi=0)dfs(i);/*if(visitedi=0)dfs(i);/*深度优先遍历时调深度优先遍历时调 用用dfs(i)*/dfs(i)*/思考：思考：travergraphtravergraph调用调用 dfsdfs的次数的次数由什么决定？由什么决定？图若采用邻接矩阵存储图若采用邻
37、接矩阵存储,编写相应的编写相应的firstadj(g,V0)firstadj(g,V0)和和nextadj(g,V0,w)nextadj(g,V0,w)算法算法4.1 4.1 从顶点从顶点v0v0出发深度优先遍历出发深度优先遍历g g中能访问的各个顶点中能访问的各个顶点void dfs(int v0)void dfs(int v0)visitedv0=1;/*visitedv0=1;/*访问标志置为访问标志置为 1 1，表示已被访问，表示已被访问*/w=firstadj(g,v0);/*w w=firstadj(g,v0);/*w是是vovo的第一个邻接点的第一个邻接点*/while(w!=0
38、)while(w!=0)if(visitedw=0)dfs(w);/*if(visitedw=0)dfs(w);/*顶点未被访问，则递归的进行深度遍历顶点未被访问，则递归的进行深度遍历*/w=nextadj(g,v0,w)/*w=nextadj(g,v0,w)/*顶点已访问，则取顶点顶点已访问，则取顶点v0v0在在w w后面的下一个邻接点后面的下一个邻接点*/第34页/共111页$4.3图图的遍历如何实现非递归算法?当然是栈了!第35页/共111页$4.3图图的遍历二、广度优先搜索（二、广度优先搜索（breadth-first-search)breadth-first-search)首先访问指
39、定顶点首先访问指定顶点v0v0，将，将v0v0作为当前顶点作为当前顶点;访问当前顶点的所有未访问过的邻接点，访问当前顶点的所有未访问过的邻接点，并依次将访问的这些邻接点作为当前顶点并依次将访问的这些邻接点作为当前顶点;重复重复2 2，直到所有顶点被访问为止。直到所有顶点被访问为止。对右图广度优先搜索，访问顶点序列为：对右图广度优先搜索，访问顶点序列为：V1 V2 V3 V4 V5 V6 V7 V8V1 V2 V3 V4 V5 V6 V7 V8V1V1V2V2V3V3V4V4V5V5V6V6V7V7V8V8第36页/共111页S$4.3图图的遍历广度优先遍历的非递归算法怎么实现?对每一个当前访问
40、顶点,一次性访问其所有的邻接点,您认为采用什么数据结构可以实现非递归算法?队列!Smarter!第37页/共111页S$4.3图图的遍历算法算法4.3 4.3 从顶点从顶点v v0 0出发广度优先遍历出发广度优先遍历g g中能访问的各个顶点中能访问的各个顶点Void bfs(Graph g,int vVoid bfs(Graph g,int v0 0)/*)/*从从v v0 0出发广度优先遍历图出发广度优先遍历图g */g */visitedv visitedv0 0=1;=1;Enqueue(Q,v Enqueue(Q,v0 0););While(!Empty(Q)While(!Empty(
41、Q)v=Dlqueue(Q);/*v=Dlqueue(Q);/*取队头元素取队头元素v */v */w=Firstadj(g,v);/*w=Firstadj(g,v);/*求求v v的第一个邻接点的第一个邻接点*/while(w!=0)while(w!=0)if(visitedw=0)if(visitedw=0)visitedw=1;visitedw=1;Enqueue(Q,w);Enqueue(Q,w);w=Nextadj(g,v,w);/*w=Nextadj(g,v,w);/*求下一个邻接点求下一个邻接点 */第38页/共111页$4.4图图的应用-最小生成树右图为一个新兴小镇右图为一个新
42、兴小镇.其中其中6个个红色小块为社区房屋红色小块为社区房屋,2个白色个白色小块为商店小块为商店.现在要铺设天然现在要铺设天然气管道气管道,造价和天然气管长度造价和天然气管长度成正比成正比.如何铺设管道使得所如何铺设管道使得所有房屋和商店都通气且造价最有房屋和商店都通气且造价最低低?第39页/共111页$4.4图图的应用-最小生成树Idea:实质是求图的包含所有顶点的具有最少边数的连通图,且边权值和最小.Target:1.求出图的具有最少边数的连通子图 2.求出上述子图图中边取值和最小的连通子图第40页/共111页$4.4图图的应用-最小生成树一、最小生成树概念一、最小生成树概念1.1.设无向连
43、通图设无向连通图G=G=（V V，EE），），其子图其子图G G=（V V，TT）满足：满足：V(GV(G)=V(G)n)=V(G)n个顶点个顶点 G G是连通的是连通的 G G中无回路中无回路则则G G是是G G的生成树的生成树第41页/共111页$4.4图图的应用-最小生成树具有具有n n个顶点的无向连通图个顶点的无向连通图G G 其任一生成子图其任一生成子图G G恰好含恰好含n-1n-1条边条边 生成树不一定唯一生成树不一定唯一4 4 4 4个顶点选择个顶点选择个顶点选择个顶点选择3 3 3 3条边有条边有条边有条边有如下如下如下如下5 5 5 5种形状种形状种形状种形状(54=20(5
44、4=20(54=20(54=20种种种种):):):):其中其中其中其中16161616种为生成树种为生成树种为生成树种为生成树,（保证了连通）（保证了连通）（保证了连通）（保证了连通）第42页/共111页$4.4图图的应用-最小生成树生成树代价生成树代价对图中每条边赋于一个权值（代价），则构成一个网，对图中每条边赋于一个权值（代价），则构成一个网，网的生成树网的生成树G G=(V=(V，T)T)的的代价代价是是T T中各边的权值之和，中各边的权值之和，最小生成树就是网上所有可能的生成树中，代价最小的一类生最小生成树就是网上所有可能的生成树中，代价最小的一类生成树。成树。最小生成树也不一定唯一
45、。最小生成树也不一定唯一。第43页/共111页$4.4图图的应用-最小生成树您能够想出更多采用您能够想出更多采用最小生成树解决问题的实例吗最小生成树解决问题的实例吗?第44页/共111页$4.4图图的应用-最小生成树例例例例1 1 1 1：N N N N台计算机之间建立通讯网台计算机之间建立通讯网台计算机之间建立通讯网台计算机之间建立通讯网顶点表示顶点表示顶点表示顶点表示computercomputercomputercomputer边表示通讯线边表示通讯线边表示通讯线边表示通讯线权值表示通讯线的代价（通讯权值表示通讯线的代价（通讯权值表示通讯线的代价（通讯权值表示通讯线的代价（通讯线长度，线
46、长度，线长度，线长度，computercomputercomputercomputer间距离等）间距离等）间距离等）间距离等）要求：要求：要求：要求：n n n n台计算机中的任何两台能通过网进行通讯；台计算机中的任何两台能通过网进行通讯；台计算机中的任何两台能通过网进行通讯；台计算机中的任何两台能通过网进行通讯；使总的代价最小。使总的代价最小。使总的代价最小。使总的代价最小。-求最小生成树求最小生成树求最小生成树求最小生成树TTTT第45页/共111页$4.4图图的应用-最小生成树例例例例2 2：邮递员送信线路邮递员送信线路邮递员送信线路邮递员送信线路TT顶点表示投递点顶点表示投递点顶点表示
47、投递点顶点表示投递点边表示街道边表示街道边表示街道边表示街道权值表示街道的长度权值表示街道的长度权值表示街道的长度权值表示街道的长度要求：要求：要求：要求：完成完成完成完成n n n n个投递点的投递；个投递点的投递；个投递点的投递；个投递点的投递；使总路径长度最短使总路径长度最短使总路径长度最短使总路径长度最短,即求最小生成树即求最小生成树即求最小生成树即求最小生成树TTTT第46页/共111页$4.4图图的应用-最小生成树Problem:如何求解带权图的最小生成树如何求解带权图的最小生成树?第47页/共111页$4.4图图的应用-最小生成树二、最小生成树性质二、最小生成树性质MSTMST设
48、设N=N=（V V，EE）是一个连通网，）是一个连通网，U U是顶点集是顶点集V V的一个非空子集。的一个非空子集。若（若（u u，v v）是一条具有最小权值的边，其中）是一条具有最小权值的边，其中uU,vV-U,uU,vV-U,即（即（u u，v v）=Mincost(x,y)|xU,yV-U=Mincost(x,y)|xU,yV-U则必存在一棵包含边（则必存在一棵包含边（u u，v v）的最小生成树。）的最小生成树。uv-uuvuv含义：将顶点分为两个不相交的集合含义：将顶点分为两个不相交的集合含义：将顶点分为两个不相交的集合含义：将顶点分为两个不相交的集合U U U U和和和和V-UV-
49、UV-UV-U，若边（若边（若边（若边（u u u u，v v v v）是连接这两个顶点集的最小权值边，）是连接这两个顶点集的最小权值边，）是连接这两个顶点集的最小权值边，）是连接这两个顶点集的最小权值边，则边（则边（则边（则边（u u u u，v v v v）必然是某最小生成树的边。）必然是某最小生成树的边。）必然是某最小生成树的边。）必然是某最小生成树的边。第48页/共111页$4.4图图的应用-最小生成树基本思想：基本思想：取图中任意一个顶点取图中任意一个顶点 v v 作为生成树的根，之后往生成树上添加新的作为生成树的根，之后往生成树上添加新的顶点顶点 w w。在添加的顶点在添加的顶点
50、w w 和已经在生成树上的顶点和已经在生成树上的顶点u u 之间必定存在之间必定存在一条边，并且该边的权值在所有连通顶点一条边，并且该边的权值在所有连通顶点 u u 和和 w w 之间的边中取值之间的边中取值最小最小。之后继续往生成树上添加顶点，直至生成树上含有。之后继续往生成树上添加顶点，直至生成树上含有 n n个顶点个顶点为止。为止。普里姆（普里姆（PrimPrim）最小生成树算法）最小生成树算法第49页/共111页$4.4 图图的应用-最小生成树a ab bc cd de eg gf f例如例如:19195 514141818272716168 821213 3a ae e1212d d