数据结构的图存储框架
发布时间:2022-07-08 18:06:22 所属栏目:语言 来源:互联网
导读:我们知道,数据之间的关系有 3 种,分别是 一对一、一对多 和 多对多,前两种关系的数据可分别用线性表和树结构存储,本节学习存储具有多对多逻辑关系数据的结构图存储结构。 图存储结构基本常识 弧头和弧尾 有向图中,无箭头一端的顶点通常被称为初始点或弧
我们知道,数据之间的关系有 3 种,分别是 "一对一"、"一对多" 和 "多对多",前两种关系的数据可分别用线性表和树结构存储,本节学习存储具有"多对多"逻辑关系数据的结构——图存储结构。 图存储结构基本常识 弧头和弧尾 有向图中,无箭头一端的顶点通常被称为"初始点"或"弧尾",箭头直线的顶点被称为"终端点"或"弧头"。 入度和出度 对于有向图中的一个顶点 V 来说,箭头指向 V 的弧的数量为 V 的入度(InDegree,记为 ID(V));箭头远离 V 的弧的数量为 V 的出度(OutDegree,记为OD(V))。拿图 2 中的顶点 V1来说,该顶点的入度为 1,出度为 2(该顶点的度为 3)。 (V1,V2) 和 <V1,V2> 的区别 无向图中描述两顶点(V1 和 V2)之间的关系可以用 (V1,V2) 来表示,而有向图中描述从 V1 到 V2 的"单向"关系用 <V1,V2> 来表示。 由于图存储结构中顶点之间的关系是用线来表示的,因此 (V1,V2) 还可以用来表示无向图中连接 V1 和 V2 的线,又称为边;同样,<V1,V2> 也可用来表示有向图中从 V1 到 V2 带方向的线,又称为弧。 集合 VR 的含义 并且,图中习惯用 VR 表示图中所有顶点之间关系的集合。例如,图 1 中无向图的集合 VR={(v1,v2),(v1,v4),(v1,v3),(v3,v4)},图 2 中有向图的集合 VR={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。 路径和回路 无论是无向图还是有向图,从一个顶点到另一顶点途径的所有顶点组成的序列(包含这两个顶点),称为一条路径。如果路径中第一个顶点和最后一个顶点相同,则此路径称为"回路"(或"环")。 并且,若路径中各顶点都不重复,此路径又被称为"简单路径";同样,若回路中的顶点互不重复,此回路被称为"简单回路"(或简单环)。 拿图 1 来说,从 V1 存在一条路径还可以回到 V1,此路径为 {V1,V3,V4,V1},这是一个回路(环),而且还是一个简单回路(简单环)。 在有向图中,每条路径或回路都是有方向的。 (编辑:航空爱好网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
站长推荐