【精品数据结构】图结构.PPTVIP

第 6 章 图结构 若干个结点与若干条边构成的结构 结点是一些具体对象的抽象 边是对象间的关系 图是一种复杂的非线性结构，它有极强的表达能力 图中结点可有多个前趋和多个后继 这里着重讨论图的存贮结构与基本操作的实现 §6.1 图的基本概念§6.1.1 图的概念 1．图 图是由若干个结点和若干条边构成的结构，每个结点具有任意多个前驱和后继。 结点集合：结点代表对象 边集合：两结点之间的边表示它们代表的对象之间的关系 在具体应用中，结点与边要被赋予具体的含意,如 结点代表城市 边代表城市之间的行程。 §6.1.1 图的概念 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存在问题世界中的关系。 §6.1.1 图的概念 2．有向/无向图 若二元关系VR是对称的（即对任意x与y，若有x,y∈VR，则必有y,x∈VR），则称图G是无向图，否则称有向图。对无向图，我们用(x,y)表示x,y。 §6.1.1 图的概念 3．结点、边、弧 图中的数据元素称为结点（或顶点） 有时为了强调，对有向图，称x,y为弧，x与y分别为弧尾与弧头， 称x与y分别为x,y的始点与终点， 称y为x的出点/可达邻接点， 称x为y的入点，称x, y为x的出边/出弧，x, y为y的入边/入弧。 对无向图，称x,y为边。 在讨论图中，一般用自然数串给结点编号。 【例 6?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)} §6.1.1 图的概念 4．邻接、关联 对图中任意结点x与y，若它们之间存在边的关系（即有x,y，或y,x），则称x与y邻接，它们互为邻接点。同时称x或y与边x,y（或y,x或(x,y)）关联。 §6.1.1 图的概念 5．度 对任一结点x，称以它为头的弧的个数为它的入度 称以它为尾的弧的个数为它的出度 称它的入度与出度之和为它的度。 对无向图，无出度入度之分，直接称与它关联的边的个数为它的度。 §6.1.1 图的概念 6．权 权是一个数值量，是某些信息的数字化抽象。 权分边权与结点权，分别是边与结点的问题世界所关心的信息的数值化表示。 例如，若结点代表城市，则边权可代表城市之间的交通费用。 §6.1.1 图的概念 7．路径（通路） 对有向图，若存在弧序列 　　　　x0,x1，x1,x2，…，xn-1,xn 且n≥1，则称从x0到xn有通路（路径）。上列序列称为x0到xn的路径。该路径也可表示为 (x0, x1, … ,xn) §6.1.1 图的概念 7．路径（通路）（续） 对无向图，若有边序列 　　　　　(x0,x1)，(x1,x2)，…，(xn-1,xn) 且n≥1，则称x0与xn之间有路径（通路），该路径可用上列边序列表示，亦可用下列结点序列表示 (x0, x1, … ,xn) §6.1.1 图的概念 7．路径（通路）（续） 路径中边的数目称为路径长。 若x0=xn，则称相应的路径为回路/环路。 若在路径(x0, x1, … ,xn)中，除x0与xn外，任意其它结点均不相同，则称该路径为简单路径。起点与终点重合的简单路径称为简单回路。 §6.1.1 图的概念 8．子图/生成图 若某图G的结点集合与边集合分别是另一图的G的结点集合和边集合的子集，则称G为G的子图。 设有两个图G与G，若它们的结点集合相同，但G的边集合是G的边集合的子集，则称G是G的生成图。 显然，生成图一定是子图，但反之未必。 §6.1.1 图的概念 9．连通 若图中任意两结点间均有通路（x到y与y到x），则称该图是（强）连通的。 若图中某子图是连通的，则称该子图为一个连通分量。 若G的某子图G是连通的，并且，若有G的另一子图G包含图G，则G必不连通, 则称G是极大连通分量。 §6.1.1 图的概念 9．连通（续） 对于有向图，若任意两结点间至少有单向通路，但有些结点无双向通路，则称该图为弱连图。 类似地，也有弱连通分量的概念。 §6.1.1 图的概念 10．生成树 无回路的连通的无向图的生成图，称为该无向图的生成树。 【定理 6?1】生成树中边的个数为结点个数减1. §6.1.2 图的基本操作 ①检索： 　　·按结点（编号或内容）检索结点（位置）