图的定义和术语课件

第七章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第七章图1学习目标熟练掌握图中常用的术语和概念。熟练掌握图的邻接矩阵和邻接表的存储方式并能熟练运用这两种存储方法建立图的存储结构。■熟练掌握图的深度优先遍历和广度优先遍历的方法和算法。熟练掌握最小生成树的概念和算法。掌握拓扑排序并能求出拓扑序列。掌握最短路径算法并能求岀最短路径。学习目标27.1图的定义和术语■图(Graph)是一种网状数据结构,其形式化定义为Graph=(V,R),其中V=xxEDataObject);R=IVRIVR={v,wv,w∈V且P(v,w),<V,W表示从v到w的弧,谓词P(v,w)定义了弧<v,w的意义或信息}Data0bject为个集合,该集合中的所有元素具有相同的特性。V中的数据元素通常称为顶点(vertex),VR是两个顶点之间关系的集合。P(x,y)表示x和y之间有特定的关联属性P。7.1图的定义和术语3若<v,w∈VR,则<v,w>表示从顶点v到顶点w的一条弧(arc),并称v为弧尾(tai1)或起始点,称w为弧头(head)或终端点,此时图中的边是有方向的。若图中的关系均为弧,则称这样的图为有向图。例若<v,w∈VR,则<v,w>表示从顶点v到顶点w的一条弧4若<v,w>∈VR,必有<w,ⅴ>∈VR,VR是对称关系,这时以无序对(v,w)来代替两个有序对<v,w和<W,v>,表示x和y之间的一条边(edge)。若图中的关系均为边的关系,则此时的图称为无向图。若<v,w>∈VR,必有<w,ⅴ>∈VR,VR是对称关系,这5图的基本操作■{结构初始化}aCreateGraph(&G,V,vR)初始条件:V是图的顶点集,VR是图中弧的集合。供结1按y和的定x构造图6■DestroyGraph(&G)■初始条件:图G存在■操作结果:销毁图G图的基本操作6图的定义和术语课件7图的表示1.逻辑图表示:如图G1和G2G3有向图G4无向图图的表示8图的定义和术语课件9G2G2=(V,E)V(G2)={1,2,3,4,56,7}E(Gl)={(1,2),(1,3),(2,3),(2,4),(25),(5,6),(5,7)G210图的定义和术语课件11图的定义和术语课件12图的定义和术语课件13图的定义和术语课件14图的定义和术语课件15图的定义和术语课件16图的定义和术语课件17图的定义和术语课件18图的定义和术语课件19图的定义和术语课件20图的定义和术语课件21图的定义和术语课件22图的定义和术语课件23图的定义和术语课件24图的定义和术语课件25图的定义和术语课件26图的定义和术语课件27图的定义和术语课件28图的定义和术语课件29图的定义和术语课件30图的定义和术语课件31图的定义和术语课件32图的定义和术语课件33图的定义和术语课件34图的定义和术语课件35图的定义和术语课件36图的定义和术语课件37图的定义和术语课件38图的定义和术语课件39图的定义和术语课件40图的定义和术语课件41图的定义和术语课件42图的定义和术语课件43图的定义和术语课件44图的定义和术语课件45图的定义和术语课件46图的定义和术语课件47图的定义和术语课件48图的定义和术语课件49图的定义和术语课件50图的定义和术语课件51图的定义和术语课件52图的定义和术语课件53图的定义和术语课件54图的定义和术语课件55图的定义和术语课件56图的定义和术语课件57图的定义和术语课件58图的定义和术语课件59图的定义和术语课件60图的定义和术语课件61图的定义和术语课件62图的定义和术语课件63图的定义和术语课件64图的定义和术语课件65图的定义和术语课件66图的定义和术语课件67图的定义和术语课件68图的定义和术语课件69图的定义和术语课件70第七章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第七章图71学习目标熟练掌握图中常用的术语和概念。熟练掌握图的邻接矩阵和邻接表的存储方式并能熟练运用这两种存储方法建立图的存储结构。■熟练掌握图的深度优先遍历和广度优先遍历的方法和算法。熟练掌握最小生成树的概念和算法。掌握拓扑排序并能求出拓扑序列。掌握最短路径算法并能求岀最短路径。学习目标727.1图的定义和术语■图(Graph)是一种网状数据结构,其形式化定义为Graph=(V,R),其中V=xxEDataObject);R=IVRIVR={v,wv,w∈V且P(v,w),<V,W表示从v到w的弧,谓词P(v,w)定义了弧<v,w的意义或信息}Data0bject为个集合,该集合中的所有元素具有相同的特性。V中的数据元素通常称为顶点(vertex),VR是两个顶点之间关系的集合。P(x,y)表示x和y之间有特定的关联属性P。7.1图的定义和术语73若<v,w∈VR,则<v,w>表示从顶点v到顶点w的一条弧(arc),并称v为弧尾(tai1)或起始点,称w为弧头(head)或终端点,此时图中的边是有方向的。若图中的关系均为弧,则称这样的图为有向图。例若<v,w∈VR,则<v,w>表示从顶点v到顶点w的一条弧74若<v,w>∈VR,必有<w,ⅴ>∈VR,VR是对称关系,这时以无序对(v,w)来代替两个有序对<v,w和<W,v>,表示x和y之间的一条边(edge)。若图中的关系均为边的关系,则此时的图称为无向图。若<v,w>∈VR,必有<w,ⅴ>∈VR,VR是对称关系,这75图的基本操作■{结构初始化}aCreateGraph(&G,V,vR)初始条件:V是图的顶点集,VR是图中弧的集合。供结1按y和的定x构造图6■DestroyGraph(&G)■初始条件:图G存在■操作结果:销毁图G图的基本操作76图的定义和术语课件77图的表示1.逻辑图表示:如图G1和G2G3有向图G4无向图图的表示78图的定义和术语课件79G2G2=(V,E)V(G2)={1,2,3,4,56,7}E(Gl)={(1,2),(1,3),(2,3),(2,4),(25),(5,6),(5,7)G280图的定义和术语课件81图的定义和术语课件82图的定义和术语课件83图的定义和术语课件84图的定义和术语课件85图的定义和术语课件86图的定义和术语课件87图的定义和术语课件88图的定义和术语课件89图的定义和术语课件90图的定义和术语课件91图的定义和术语课件92图的定义和术语课件93图的定义和术语课件94图的定义和术语课件95图的定义和术语课件96图的定义和术语课件97图的定义和术语课件98图的定义和术语课件99图的定义和术语课件100图的定义和术语课件101图的定义和术语课件102图的定义和术语课件103图的定义和术语课件104图的定义和术语课件105图的定义和术语课件106图的定义和术语课件107图的定义和术语课件108图的定义和术语课件109图的定义和术语课件110图的定义和术语课件111图的定义和术语课件112图的定义和术语课件113图的定义和术语课件114图的定义和术语课件115图的定义和术语课件116图的定义和术语课件117图的定义和术语课件118图的定义和术语课件119图的定义和术语课件120图的定义和术语课件121图的定义和术语课件122图的定义和术语课件123图的定义和术语课件124图的定义和术语课件125图的定义和术语课件126图的定义和术语课件127