第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={<x,y> | 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，若有 <x,y>∈VR，则必有<y,x>∈VR），则称图G是 无向图，否则称有向图。对无向图，我们用 (x,y)表示<x,y>。 1 2 5 4 3 a b c d
§6.1.1图的概念 ·3.结点、边、弧 4 图中的数据元素称为结点(或顶点) 有时为了强调,对有向图,称<x,y>为弧,x与y分别为弧尾与弧 头, 称x与y分别为<x,y>的始点与终点, 称y为x的出点/可达邻接点, 称x为y的入点,称〈x,y>为x的出边/出弧,<x,y>为y的入边/入 弧 对无向图,称<x,y>为边。 在讨论图中,一般用自然数串给结点编号 b
5 §6.1.1 图的概念 • 3．结点、边、弧 • 图中的数据元素称为结点（或顶点） • 有时为了强调，对有向图，称<x,y>为弧，x与y分别为弧尾与弧 头， • 称x与y分别为<x,y>的始点与终点， • 称y为x的出点/可达邻接点， • 称x为y的入点，称<x, y>为x的出边/出弧，<x, y>为y的入边/入 弧。 • 对无向图，称<x,y>为边。 • 在讨论图中，一般用自然数串给结点编号。 1 2 5 4 3 a b c d