第6章图结构 若干个结点与若干条边构成的结构 结点是一些具体对象的抽象 边是对象间的关系 图是一种复杂的非线性结构,它有极强的表达 能力 ·图中结点可有多个前趋和多个后继 这里着重讨论图的存贮结构与基本操作的实现
1 第 6 章 图结构 • 若干个结点与若干条边构成的结构 –结点是一些具体对象的抽象 –边是对象间的关系 • 图是一种复杂的非线性结构，它有极强的表达 能力 • 图中结点可有多个前趋和多个后继 • 这里着重讨论图的存贮结构与基本操作的实现
§6.1图的基本概念 §6.1.1图的概念 图是由若干个结点和若干条边构成的结构,每个结点 具有任意多个前驱和后继 结点集合:结点代表对象 边集合:两结点之间的边表示它们代表的对象之间的关系 在具体应用中,结点与边要被赋予具体的含意,如 结点代表城市 边代表城市之间的行程。 2 4
2 §6.1 图的基本概念 §6.1.1 图的概念 1．图 • 图是由若干个结点和若干条边构成的结构，每个结点 具有任意多个前驱和后继。 – 结点集合：结点代表对象 –边集合：两结点之间的边表示它们代表的对象之间的关系 • 在具体应用中，结点与边要被赋予具体的含意,如 –结点代表城市 –边代表城市之间的行程。 1 2 5 4 3 a b c d
§6.1.1图的概念 图 图是形为 图的形式化 G=(V,R) 定义 的数据结构,其中, V={xx属于数据对象} REVRS VR={x,y>|p(xy)∧x∈v∧y∈Ⅴ} 这里,p(Xy)是V上的一个谓词,p(xy)为真当且仅当x与y 存在问题世界中的关系
3 §6.1.1 图的概念 1．图 图是形为 G=(V, R) 的数据结构，其中， V={x|x属于数据对象} R={VR} VR={ | p(x,y)∧x∈V∧y∈V} 这里，p(x,y)是V上的一个谓词，p(x,y)为真当且仅当x与y 存在问题世界中的关系。 图的形式化 定义
§6.1.1图的概念 2.有向/无向图 若二元关系ⅤR是对称的(即对任意x与y,若有 xxy>∈VR,则必有yx>∈VR),则称图G是 无向图,否则称有向图。对无向图,我们用 (xy)麦表示xy>
4 §6.1.1 图的概念 2．有向/无向图 若二元关系VR是对称的（即对任意x与y，若有 ∈VR，则必有∈VR），则称图G是 无向图，否则称有向图。对无向图，我们用 (x,y)表示。 1 2 5 4 3 a b c d
§6.1.1图的概念 ·3.结点、边、弧 4 图中的数据元素称为结点(或顶点) 有时为了强调,对有向图,称为弧,x与y分别为弧尾与弧 头, 称x与y分别为的始点与终点, 称y为x的出点/可达邻接点, 称x为y的入点,称〈x,y>为x的出边/出弧,为y的入边/入 弧 对无向图,称为边。 在讨论图中,一般用自然数串给结点编号 b
5 §6.1.1 图的概念 • 3．结点、边、弧 • 图中的数据元素称为结点（或顶点） • 有时为了强调，对有向图，称为弧，x与y分别为弧尾与弧 头， • 称x与y分别为的始点与终点， • 称y为x的出点/可达邻接点， • 称x为y的入点，称为x的出边/出弧，为y的入边/入 弧。 • 对无向图，称为边。 • 在讨论图中，一般用自然数串给结点编号。 1 2 5 4 3 a b c d
【例6-1】设有两个二元组G1=(V1R1)与G2=(V2R2),其中, V1={1,2,3,4,5} R1={VR1} VR1={,,,,, R2=iVRy VR2={(ab),(a,d)2(b,d),(d,c)} (a)有向图 (a)无向图 【图-】图示例
6 【例 6-1】设有两个二元组G1=(V1 ,R1 )与G2=(V2 , R2 )，其中， V1={1, 2, 3, 4, 5} R1={VR1 } VR1={, , , , , } V2={a, b, c, d} R2={VR2 } VR2={(a,b), (a, d), (b, d), (d, c)} 1 2 5 4 3 a b c d (a) 有向图 (a) 无向图 【图 -】图示例
§6.1.1图的概念 4.邻接、关联 ·对图中任意结点x与y,若它们之间存在边的关 系(即有,或y,x〉),则称x与y邻接, 们互为邻接点。同时称x或y与边或(x,y))关联
7 §6.1.1 图的概念 4．邻接、关联 • 对图中任意结点x与y，若它们之间存在边的关 系（即有，或），则称x与y邻接， 它们互为邻接点。同时称x或y与边（或 或(x,y)）关联。 1 2 5 4 3 a b c d
§6.1.1图的概念 5.度 对任一结点x,称以它为头的弧的个数为它的入度 称以它为尾的弧的个数为它的出度 称它的入度与出度之和为它的度 对无向图,无出度入度之分,直接称与它关联的边的 个数为它的度
8 §6.1.1 图的概念 5．度 • 对任一结点x，称以它为头的弧的个数为它的入度 • 称以它为尾的弧的个数为它的出度 • 称它的入度与出度之和为它的度。 • 对无向图，无出度入度之分，直接称与它关联的边的 个数为它的度。 1 2 5 4 3 a b c d
§6.1.1图的概念 6.权 权是一个数值量,是某些信息的数字化抽象。 权分边权与结点权,分别是边与结点的问题世界所关 心的信息的数值化表示 例如,若结点代表城市,则边权可代表城市之间的交 通费用。 200 70 60
9 §6.1.1 图的概念 6．权 • 权是一个数值量，是某些信息的数字化抽象。 • 权分边权与结点权，分别是边与结点的问题世界所关 心的信息的数值化表示。 • 例如，若结点代表城市，则边权可代表城市之间的交 通费用。 1 2 5 4 3 60 70 200 170 70 90
§6.1.1图的概念 7.路径(通路) 对有向图,若存在弧序列 X1,X2> 且n≥l,则称从x到x有通路(路径)。上列序列称为 x到x的路径。该路径也可表示为 2
10 §6.1.1 图的概念 7．路径（通路） • 对有向图，若存在弧序列 ，，…， 且n≥1，则称从x0到xn有通路（路径）。上列序列称为 x0到xn的路径。该路径也可表示为 (x0 , x1 , … ,xn ) 1 2 5 4 3