图的基本概念和基本操作.ppt

数据结构与算法 ---第十八讲;18、图的基本概念、图的基本操作，以及图的对象抽象模型 ;目 录;这里的图，有时也称网络，是指由若干个结点与若干条边构成的结构，其中每个结点可有多个前趋和多个后继，结点是一些具体对象的抽象，而边是对象间的关系的抽象。值得注意的是，与一般意义下的图不同，这里的图只涉及图的拓扑结构，与图的几何性质无关。图论重点讨论图的数学性质，而这里的重点是图结点间的关系以及图的存贮结构与基本操作的实现。图是一种复杂的非线性结构，它有极强的表达能力，现实世界中许多问题均可用图结构描述。 ; 18.2.1 图的概念; 形式化地讲，图是形为 G=(V, R) 的数据结构，其中， V={x|x属于数据对象} R={VR} VR={x,y | p(x,y)∧x∈V∧y∈V} 这里，p(x,y)是V上的一个谓词，p(x,y)为真当且仅当x与y存在问题世界中的关系。 ? ; 若二元关系VR中的每个型如x，y的成员中的x与y是次序无关的，则称该图为无向图(undirecyed graph)，否则称为有向图(directed graph)。无向图也可以看作VR对称的图，即对任意x与y，若有x,y∈VR，则必有y,x∈VR。对无向图，我们用(x,y)表示x,y。 ; 3．结点、边、弧 图中的数据元素称为结点（或顶点）(vertice/node/point)，有时为了强调，对有向图，称x,y为弧(arc)，x与y分别为弧尾与弧头，或始点与终点，称y为x的出点/可达邻接点，称x为y的入点称x, y为x的出边/出弧，x, y 为y的入边/入弧。对无向图， 泛称x,y为边(edge)。在讨论 图中，为了方便，一般给 结点编号，用它们的编号代表 它们。结点编号一般用自然数。 ; 例 18?1设有两个二元组G1=(V1, R1)与G2=(V2, R2)，其中， 　　 V1={1, 2, 3, 4, 5} R1={VR1} VR1={1,2, 1,5, 2,1, 2,4, 3,5, 4,1} V2={a, b, c, d} R2={VR2} VR2={(a,b), (a, d), (b, d), (d, c)} ; 4．邻接、关联 对图中任意结点x与y，若它们之间存在??（即有x,y，或y,x），则称x与y邻接(adjacent)，它们互为邻接点。同时称x或y与边x,y（或y,x或(x,y)）关联(incident)。 5．度 对任一结点x，称以它为头的弧的个数为它的入度(In degree)；称以它为尾的弧的个数为它的出度(out degree)；称它的入度与出度之和为它的度(degree)。对无向图，无出度入度之分，直接称与它关联的边的个数为它的度。例如，图6-1(a)中的结点1的出度与入度都为2，结点3的出度入度分别为1和0，(b)中的结点a、b、度均为2，而d的度为3，c的度为1。? ;6．权 权(Weight)与哈夫曼树中的概念相同，即权是一个数值量，是某些信息的数字化抽象。权分边权与结点权，分别是边与结点的问题世界所关心的信息的数值化表示。例如，若结点代表城市，则边权可代表城市之间的交通费用。 ;对无向图，若有边序列　　 　　 (x0,x1)，(x1,x2)，…，(xn-1,xn) 且n≥1，则称x0与xn之间有路径（通路），该路径可用上列边序列表示，亦可用下列结点序列表示 (x0, x1, … ,xn) 路径中边的数目称为路径长。 若x0=xn，则称相应的路径为回路/环路(loop)。 若在路径(x0, x1, … ,xn)中，除x0与xn外，任意其它结点均不相同，则称该路径为简单路径(Simple Path)。起点与终点重合的简单路径称为简单回路(Simple Loop)。 U???? 显然，简单路径中不含回路。 ; 8．子图/生成图 若某图G的结点集