数据结构之图论课件

数据结构之图论数据结构之图论1第四章图结构困的基本概念的存储困的追历第四章图结构2图的定义、术语4.I图的定义和术语■图是由非空的顶点组成的有限集和边的有限集组成。■二元组G=(V,E)·V:顶点集合·E;边的集合,即顶点间的关系■图结构中的美系可以是任意的,甚至可以是空集·图是一种对结点的前驱和后继个教不加限制的教据结构图的定义、术语3图的术语1)有向图与无向图>由有向边组成的图,称为有向图>有向边以<Ⅹ,Y>表示,又称为弧·X:弧尾·Y:孤头>有向边<X,Y>与<Y,X>不是同一条边由无向边组成的图,称为无向图无向边以(X,Y)表示无向边(X,Y)与(Y,Ⅹ)是同一条边图的术语4图的术语2)权与网图中边或弧所具有的相关数称为权般用于表明从一个顶点到另一个顶点的源离或耗费13带权的图称为网3)邻接与顶点的度对于(X,Y)∈E则Ⅹ,Y互为邻接对于<X,Y>∈E则Y是Ⅹ的邻接结点图的术语5图的术语出度:以该顶点为弧尾的弧数顶点图:入度:以该顶点为弧头的弧数和顶点度为无向图:顶点的边数总边数-1各顶点度之和-1∑D(Ⅵ·给出以下顶点的度图的术语6图的术语4)路径与回路■路径:图中沿着各条边,从X到Y所经历的顶点序列称为路径·路径:X,b,a,Y■环:第一顶点与最后一个顶点相同的路径环环:X,a,Y,b,X回路序列中不出现重复的路径称为筒单路径·有重复的路径称为回路回路:X,a,b,a,Y图的术语7图的术语5)连通、连通图与连通分量■连通;在图中若X与Y之间有路径,则称X,Y是连通的■连通图:任意两个顶点都连通的图称为连通图■没有孤立顶点■连通分量:指无向图中极大连通子图,即有多少个连通子图88◎图的术语8x图的存储接矩阵4.2图的存储4.2.1邻接矩阵法(1)给顶点编号1(22立年接(关表示弧<b,j>000+91:表示有弧;0:表示无弧1023410010110任意顶点的出度是该行元素之和任意顶点的入度是该列元素之和x图的存储接矩阵9图的存储郐接矩阵4.21邻接矩阵法12341011021011101无向图的邻接矩阵是对称的40110■若边<<顶点则邻接矩阵为稀疏矩阵。■邻接矩阵的优点:增减边的操作简单■邻接矩阵的缺点:增减顶点的操作需要搬移大量的元素,≯浪费存储空间图的存储郐接矩阵10图的存储邹接矩阵的实现pedar解越智陆elemtypenodeMAxNUM顶点集合intarcsMAXNU№IAXNUM∶边的邻接矩阵igraphm二维数组图的存储邹接矩阵的实现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数据结构之图论课件3956、书不仅是生活，而且是现在、过去和未来文化生活的源泉。——库法耶夫

57、生命不可能有两次，但许多人连一次也不善于度过。——吕凯特

58、问渠哪得清如许，为有源头活水来。——朱熹

59、我的努力求学没有得到别的好处，只不过是愈来愈发