数据结构图PPT学习教案.pptx
《数据结构图PPT学习教案.pptx》由会员分享,可在线阅读,更多相关《数据结构图PPT学习教案.pptx(183页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、会计学1数据结构数据结构(sh j ji u)图图第一页,共183页。揭安全(nqun)江西省高等学校(godngxuxio)精品课程江西师范大学计算机信息工程学院江西师范大学计算机信息工程学院第1页/共183页第二页,共183页。第章图图的基本概念 图的基本(jbn)运算 生成(shn chn)树与最小生成(shn chn)树 拓扑(tu p)排序 图的基本存储结构 最短路径关键路径 图的遍历第2页/共183页第三页,共183页。8.1 8.1 图的基本概念图的基本概念图的基本概念图的基本概念一、图的定义(dngy)图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边(或弧)集合组成的一
2、种数据结构,它可以形式化地表示图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边(或弧)集合组成的一种数据结构,它可以形式化地表示(biosh)(biosh)为:为:图(图(V V,E E)其中其中V=x|xV=x|x某个数据对象集某个数据对象集,它是顶点的有穷非空集合;,它是顶点的有穷非空集合;E=E=(x x,y y)|x|x,y yVV或或E=xE=|xy|x,y yV V且且P P(x x,y y),它是顶点之间关系的有穷集合,也叫做边集合,它是顶点之间关系的有穷集合,也叫做边集合,P P(x x,y y)表示)表示(biosh)(biosh)从从x x到到y y的一条单向通路。
3、的一条单向通路。第3页/共183页第四页,共183页。图的应用举例例1 交通图(公路、铁路(til))顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示;V0 V4 V3 V1 V2 V0 V1 V2 V3例2电路图顶点:元件(yunjin)边:连接元件(yunjin)之间的线路例3通讯线路图顶点(dngdin):地点边:地点间的连线第4页/共183页第五页,共183页。通常,也将图通常,也将图GG的顶点集和边集分别记为的顶点集和边集分别记为V V(GG)和)和E E(GG)。)。E E(GG)可以)可以(ky)(ky)是空集,若是空集,若E E(GG)为空,则
4、图)为空,则图GG只有顶点而没有边。只有顶点而没有边。若图若图GG中的每条边都是有方向中的每条边都是有方向(fngxing)(fngxing)的,则称的,则称GG为有向图。在有向图中,一条有向边是由两个顶点组成的有序对,有序对通常用尖括号表示。例如,有序对为有向图。在有向图中,一条有向边是由两个顶点组成的有序对,有序对通常用尖括号表示。例如,有序对vivj表示一条由表示一条由vivi到到vjvj的有向边。有向边又称为弧,弧的始点称为弧尾,弧的终点称为弧头。若图的有向边。有向边又称为弧,弧的始点称为弧尾,弧的终点称为弧头。若图GG中的每条边都是没有方向中的每条边都是没有方向(fngxing)(f
5、ngxing)的,则称的,则称GG为无向图。无向图中的边均是顶点的无序对,无序对通常用圆括号表示。为无向图。无向图中的边均是顶点的无序对,无序对通常用圆括号表示。第5页/共183页第六页,共183页。图8-1v1v2v3v4v1v2v4v5v3(a)有向图G1(b)无向图G2图图8.18.1(a a)表示)表示(biosh)(biosh)的是有向图的是有向图G1G1,该图的顶点集和边集分别为:,该图的顶点集和边集分别为:V V(G1G1)=v1=v1,v2v2,v3v3,v4v4E E(G1G1)=v1=v2,v1v3,v2v4,v3v2例例有序对:用以为(ywi)vi起点、以vj为终点的有向
6、线段表示,称为有向边或弧;第6页/共183页第七页,共183页。例:图8-1v1v2v3v4v1v2v4v5v3(a)有向图G1(b)无向图G2图图8.18.1(b b)表示的是无向图)表示的是无向图G2G2,该图的顶点,该图的顶点(dngdin)(dngdin)集和边集分别为:集和边集分别为:V V(G2G2)=v1=v1,v2v2,v3v3,v4v4,v5v5E E(G2G2)=(vlvl,v2v2),(),(v1v1,v3v3),(),(v1v1,v4v4),(),(v2v2,v3v3),(),(v2v2,v5v5),(),(v4v4,v5v5)无序对(vi,vj):用连接顶点(dngd
7、in)vi、vj的线段表示,称为无向边;第7页/共183页第八页,共183页。在以后的讨论中,我们(wmen)约定:(1)一条边中涉及的两个顶点必须不相同,即:若(vi,vj)或是E(G)中的一条边,则要求vivj;(2)一对顶点间不能有相同方向的两条有向边;(3)一对顶点间不能有两条无向边,即只讨论简单的图。第8页/共183页第九页,共183页。若用若用n n表示图中顶点的数目,用表示图中顶点的数目,用e e表示图中边的数目,按照上述规定,容易得到下述结论:对于一个表示图中边的数目,按照上述规定,容易得到下述结论:对于一个(y)(y)具有具有n n个顶点的无向图,其边数个顶点的无向图,其边数
8、e e小于等于小于等于n n(n-1n-1)/2/2,边数恰好等于,边数恰好等于n n(n-1n-1)/2/2的无向图称为无向完全图;对于一个的无向图称为无向完全图;对于一个(y)(y)具有具有n n个顶点的有向图,其边数个顶点的有向图,其边数e e小于等于小于等于n n(n-1n-1),边数恰好等于),边数恰好等于n n(n-1n-1)的有向图称为有向完全图。也就是说完全图具有最多的边数,任意一对顶点间均有边相连。)的有向图称为有向完全图。也就是说完全图具有最多的边数,任意一对顶点间均有边相连。二、完全(wnqun)图第9页/共183页第十页,共183页。例:图8-2v1v2v3v4v1v2
9、v3v4(a)无向完全图G3(b)有向完全图G4图图8.28.2所示的所示的G3G3与与G4G4分别是具有分别是具有4 4个顶点的无向完全个顶点的无向完全(wnqun)(wnqun)图和有向完全图和有向完全(wnqun)(wnqun)图。图图。图G3G3共有共有4 4个顶点个顶点6 6条边;图条边;图G4G4共有共有4 4个顶点个顶点1212条边。条边。若(若(vivi,vjvj)是一条无向边,则称顶点)是一条无向边,则称顶点(dngdin)vi(dngdin)vi和和vjvj互为邻接点互为邻接点。第10页/共183页第十一页,共183页。若若vivj是一条有向边,则称是一条有向边,则称vi
10、vi邻接邻接(lnji)(lnji)到到vj vj,vj vj邻接邻接(lnji)(lnji)于于vi vi,并称有向边,并称有向边vivj关联于关联于vi vi与与vj vj,或称有向边,或称有向边vivj与顶点与顶点vi vi和和vj vj相关联。相关联。三、度、入度、出度在图中,一个在图中,一个(y)(y)顶点的度就是与该顶点相关联的边的数目,顶点顶点的度就是与该顶点相关联的边的数目,顶点v v的度记为的度记为D D(v v)。例如在图)。例如在图8.28.2(a a)所示的无向图)所示的无向图G3G3中,各顶点的度均为中,各顶点的度均为3 3。若若GG为有向图,则把以顶点为有向图,则把
11、以顶点v v为终点的边的数目称为顶点为终点的边的数目称为顶点v v的入度,记为的入度,记为IDID(v v);把以顶点);把以顶点v v为始点的边的数目称为为始点的边的数目称为v v的出度,记为的出度,记为ODOD(v v),有向图中顶点的度数等于顶点的入度与出度之和,即),有向图中顶点的度数等于顶点的入度与出度之和,即D D(v v)=ID=ID(v v)+OD+OD(v v)。)。第11页/共183页第十二页,共183页。无论有向图还是无向图,图中的每条边均关联于两个顶点,因此,顶点数n、边数e和度数(dshu)之间有如下关系:e=e=.(式8-1)四、子图给定两个图给定两个图GiGi和和
12、GjGj,其中,其中(qzhng)Gi=(qzhng)Gi=(ViVi,EiEi),),Gj=Gj=(VjVj,EjEj),若满足),若满足ViViVjVj,EiEiEjEj,则称,则称GiGi是是GjGj的子图。的子图。第12页/共183页第十三页,共183页。v1v2v4v2v3v4v1v2v3v4v1v4v2v3v4v1v1v3v2v4子图示例(shl)(a)无向(wxin)图G3的部分子图(b)有向图G4的部分(bfen)子图第13页/共183页第十四页,共183页。五、路径(ljng)无向图无向图GG中若存在着一个顶点序列中若存在着一个顶点序列v v、v1v1、v2v2、vmvm、u
13、 u,且(,且(v v,v1v1)、()、(v1v1,v2v2)、)、(、(vmvm,u u)均属于)均属于E E(GG),则称该顶点序列为顶点),则称该顶点序列为顶点v v到顶点到顶点u u的一条路径,相应地,顶点序列的一条路径,相应地,顶点序列u u、vmvm、vm-1vm-1、v1v1、v v是顶点是顶点u u到顶点到顶点v v的一条路径。的一条路径。如果如果GG是有向图,路径也是有向的,它由是有向图,路径也是有向的,它由E E(GG)中的有向边)中的有向边vv1、v1v2、vmu组成组成(zchn)(zchn)。路径长度是该路径上边或弧的数目。路径长度是该路径上边或弧的数目。第14页/
14、共183页第十五页,共183页。如果一条路径上除了起点如果一条路径上除了起点v v和终点和终点u u相同相同(xintn)(xintn)外,其余顶点均不相同外,其余顶点均不相同(xintn)(xintn),则称此路径为一条简单路径。起点和终点相同,则称此路径为一条简单路径。起点和终点相同(xintn)(xintn)(v=uv=u)的简单路径称为简单回路或简单环。)的简单路径称为简单回路或简单环。第15页/共183页第十六页,共183页。六、连通(lintng)图与强连通(lintng)图在无向图在无向图GG中,若从顶点中,若从顶点(dngdin)vi(dngdin)vi到顶点到顶点(dngdi
15、n)vj(dngdin)vj有路径,则称有路径,则称vi vi与与vj vj是连通的。若是连通的。若V V(GG)中任意两个不同的顶点)中任意两个不同的顶点(dngdin)vi(dngdin)vi和和vj vj都连通(即有路径),则称都连通(即有路径),则称GG为连通图。例如,图为连通图。例如,图8.18.1(b b)所示的无向图)所示的无向图G2G2、图、图8.28.2(a a)所示的无向图)所示的无向图G3G3是都是连通图。是都是连通图。无向图无向图GG的极大的极大(jd)(jd)连通子图称为连通子图称为GG的连通分量。根据连通分量的定义,可知任何连通图的连通分量是其自身,非连通的无向图有
16、多个连通分量。的连通分量。根据连通分量的定义,可知任何连通图的连通分量是其自身,非连通的无向图有多个连通分量。第16页/共183页第十七页,共183页。例:非连通图及其连通分量(fnling)示例(a)非连通图G5(b)G5的两个(lin)连通分量H1和H2在有向图在有向图GG中,若对于中,若对于(duy)V(duy)V(GG)中任意两个不同的顶点)中任意两个不同的顶点vi vi和和vj vj,都存在从,都存在从vi vi到到vj vj以及从以及从vj vj到到vi vi的路径,则称的路径,则称GG是强连通图。是强连通图。V V1 1V V2 2V V4 4V V5 5V V3 3V V1 1
17、V V2 2V V4 4V V5 5V V3 3第17页/共183页第十八页,共183页。有向图的极大强连通子图称为有向图的极大强连通子图称为GG的强连通分量。根据强连通图的定义,可知强连通图的唯一强连通分量是其自身,而非强连通的有向图有多个强连分量。例如,图的强连通分量。根据强连通图的定义,可知强连通图的唯一强连通分量是其自身,而非强连通的有向图有多个强连分量。例如,图8.28.2(b b)所示的有向图)所示的有向图G4G4是一个具有是一个具有4 4个顶点个顶点(dngdin)(dngdin)的强连通图,图的强连通图,图8.58.5(a a)所示的有向图)所示的有向图G6G6不是强连通图(不
18、是强连通图(v2v2、v3v3、v4v4没有到达没有到达v1v1的路径),它的两个强连通分量的路径),它的两个强连通分量H3H3与与H4H4如图如图8.58.5(b b)所示。)所示。v1v2v3v4v1v2v3v4(a)非强连通图G6(b)G6的两个强连通分量H3和H4第18页/共183页第十九页,共183页。七、网络(wnglu)有时在图的每条边上附上相关有时在图的每条边上附上相关(xinggun)(xinggun)的数值,这种与图的边相关的数值,这种与图的边相关(xinggun)(xinggun)的数值叫权。的数值叫权。权可以表示两个顶点之间的距离权可以表示两个顶点之间的距离(jl)(j
19、l)、耗费等具有某种意义的数。若将图的每条边都赋上一个权,则称这种带权图为网络。、耗费等具有某种意义的数。若将图的每条边都赋上一个权,则称这种带权图为网络。V0V1V3V234567825V0V2V1455064(a)无向网络G7(b)有向网络G8第19页/共183页第二十页,共183页。8.2图的基本(jbn)运算图是一种复杂数据结构,由图的定义及图的一组基本操作构成了图的抽象数据类型。图是一种复杂数据结构,由图的定义及图的一组基本操作构成了图的抽象数据类型。ADTGraphADTGraph 数据对象数据对象V V:VV是具有相同特性是具有相同特性(txng)(txng)的数据元素的集合,称
20、为顶点集。的数据元素的集合,称为顶点集。数据关系数据关系R R:R=vR=|vw|v,w wV V且且P P(v v,w w),),P P(v v,w w)定义了边()定义了边(v v,w w)的信息)的信息 第20页/共183页第二十一页,共183页。图的基本操作如下:(1)Creat(n)创建一个具有n个顶点,没有(miyu)边的图;(2)Exist(i,j)如果存在边(i,j)则返回1,否则返回0;(3)Edges()返回图中边的数目;(4)Vertices()返回图中顶点的数目;(5)Add(i,j)向图中添加边(i,j);(6)Delete(i,j)删除边(i,j);(7)Degre
21、e(i)返回顶点i的度;(8)InDegree(i)返回顶点i的入度;(9)OutDegree(i)返回顶点i的出度;ADTGraph第21页/共183页第二十二页,共183页。8.3 8.3 图的基本图的基本图的基本图的基本(jbn)(jbn)存储结构存储结构存储结构存储结构 图的邻接矩阵存储(cnch)表示法图的邻接(lnji)多重表表示法图的邻接表表示法第22页/共183页第二十三页,共183页。8.3 8.3 图的基本存储图的基本存储图的基本存储图的基本存储(cn ch(cn ch)结构结构结构结构 图的存储结构至少要保存两类信息图的存储结构至少要保存两类信息(xnx)(xnx):1)
22、1)顶点的数据顶点的数据 2)2)顶点间的关系顶点间的关系约定(yudng):G=是图,V=v0,v1,v2,vn-1,设顶点的 角标为它的编号 如何表示顶点间的关系?V0 V4 V3 V1 V2 V0 V1 V2 V3第23页/共183页第二十四页,共183页。邻接矩阵及其实现(shxin)给定图给定图G=G=(V V,E E),其中),其中(qzhng)V(qzhng)V(GG)=v0=v0,vivi,vn-1vn-1,GG的邻接矩阵(的邻接矩阵(AdacencyMatrixAdacencyMatrix)是具有如下性质的)是具有如下性质的n n阶方阵:阶方阵:无向图的邻接矩阵是对称无向图的
23、邻接矩阵是对称(duchn)(duchn)的,有向图的邻接矩阵可能是不对称的,有向图的邻接矩阵可能是不对称(duchn)(duchn)的。的。一、非网络的邻接矩阵第24页/共183页第二十五页,共183页。v0v1v3v2v3v1v0v2图的邻接矩阵示例(shl)01111010110110100100101011000100A1=A2=图8.7 无向图G9及有向图G10的邻接矩阵表示 第25页/共183页第二十六页,共183页。用邻接矩阵表示图,很容易判定任意两个顶点之间是否有边相连,并求得各个顶点的度数。对于无向用邻接矩阵表示图,很容易判定任意两个顶点之间是否有边相连,并求得各个顶点的度数
24、。对于无向(wxin)(wxin)图,顶点图,顶点vivi的度数是邻接矩阵中第的度数是邻接矩阵中第i i行或第行或第i i列值为列值为1 1的元素个数,即:的元素个数,即:DD(v vii)=(8-28-2)对于对于(duy)(duy)有向图,邻接矩阵中第有向图,邻接矩阵中第i i行值为行值为1 1的元素个数为顶点的元素个数为顶点vivi的出度,第的出度,第i i列值为列值为1 1的元素的个数为顶点的元素的个数为顶点vivi的入度,即:的入度,即:ODOD(v vii)=;ID=;ID(v vii)=(8-38-3)第26页/共183页第二十七页,共183页。二、网络(wnglu)的邻接矩阵当
25、G=(V,E)是一个(y)网络时,G的邻接矩阵是具有如下性质的n阶方阵:Wij当(vi,vj)或E(G)0当(vi,vj)或E(G)且i=j当(vi,vj)或E(G)且ijAi,j=其中Wij表示边上的权值;表示一个计算机允许(ynx)的、大于所有边上权值的数。第27页/共183页第二十八页,共183页。V0V1V3V234567825V0V2V1455064网络(wnglu)的邻接矩阵示例05634785603402578250050045640A3=A4=(a)G7的邻接矩阵(b)G8的邻接矩阵图8.8网络邻接矩阵示例第28页/共183页第二十九页,共183页。邻接矩阵存储(cnch)结构
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 结构图 PPT 学习 教案
限制150内