图的基本概念及基本操作.pptVIP

*数据结构与算法---第十八讲北方民族大学计算机科学与工程学院王伦津研究员图的基本概念及基本操作图的基本概念、图的基本操作，以及图的对象抽象模型掌握图的定义、结点、边、弧、邻接、关联、度、权、路径、子图、连通等有关术语及其图的检索、插入、删除、求邻接点、关联边、图的遍历等基本操作，了解图结点抽象模型、图的边对象抽象模型和图对象的抽象模型目录*011图结构022图的基本概念032.1图的概念042.2图的基本操作053图的对象抽象模型063.1图结点抽象模型073.2图的边对象抽象模型083.3图抽象对象模型18.1图结构*这里的图，有时也称网络，是指由若干个结点与若干条边构成的结构，其中每个结点可有多个前趋和多个后继，结点是一些具体对象的抽象，而边是对象间的关系的抽象。值得注意的是，与一般意义下的图不同，这里的图只涉及图的拓扑结构，与图的几何性质无关。图论重点讨论图的数学性质，而这里的重点是图结点间的关系以及图的存贮结构与基本操作的实现。图是一种复杂的非线性结构，它有极强的表达能力，现实世界中许多问题均可用图结构描述。18.2图的基本概念*18.2.1图的概念1．图图(Graph)是由若干个结点和若干条边构成的结构，每个结点具有任意多个前驱和后继。这种结构的含意为：结点集合V：结点代表对象Vertex边集合R：两结点之间的边表示它们代表的对象之间的关系形式化地讲，图是形为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存在问题世界中的关系。?在具体应用中，结点与边要被赋予具体的含意。如结点代表城市，而边代表城市之间的行程。2有向/无向图*若二元关系VR中的每个型如x，y的成员中的x与y是次序无关的，则称该图为无向图(undirecyedgraph)，否则称为有向图(directedgraph)。无向图也可以看作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)。在讨论图中，为了方便，一般给结点编号，用它们的编号代表它们。结点编号一般用自然数。12543abcd(a)有向图(b)无向图图18?1图示例例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)}显然，它们不满足线性结构、广义表和树的定义，而满足图的定义。12543abcd对任一结点x，称以它为头的弧的个数为它的入度(Indegree)；称以它为尾的弧的个数为它的出度(outdegree)；称它的入度与出度之和为它的度(degree)。对无向图，无出度入度之分，直接称与它关联的边的个数为它的度。例如，图6-1(a)中的结点1的出度与入度都为2，结点3的出度入度分别为1和0，(b)中的结点a、b、度均为2，而d的度为3，c的度为1。?度邻接、关联对图中任意结点x与y，若它们之间存在边（即有x,y，或y,x），则称x与y邻接(adjacent)，它们互为邻接点。同时称x或y与边x,y（或y,x或(x,y)）关联(