数据结构:图的概念及基本术语

图(graph)是由边(edge)连接的项的集合。每一个项被称为一个定点(vertex)或节点(node)。图中两个顶点之间的连接称为边。

图是一种数据结构的简称,有很多场景可以表示为图。比如:员工组织图,料表(BOM,bills of materials),道路系统等等。

为了更明确的限定图的类型,首先需要认识和它相关的一些术语(或称为属性):

有向:有向图(digraph)中边的两个顶点有方向或顺序。比如在奶茶店的产品BOM图中,奶茶中包含牛奶,但反之则不然。在该图中,顶点/项对(奶茶,牛奶)之间有一条边(包含关系),但牛奶,奶茶对之间没有边。

以下是有向图

有向图

无向:无向图中的没条边仅连接两个顶点,没有特定方向。比如道路系统图中上海到南京的道路。

以下是无向图

无向图

无环:无环图是指不包含循环的图,即没有在同一个顶点开始和结束的路径,比如,员工组织图。有项无环图也被称为DAG。如果包含在同一顶点开始和结束的路径,则改图就不是无环的。比如交通系统就存在许多这种路径。

连通:没对顶点都存在路径的图称为联通图。比如员工组织图。

如若转载,请注明出处:http://www.codingwhy.com/view/812.html

联系我们

在线咨询: 点击这里给我发消息

邮件:731000228@qq.com