这许许多多地铁站所组成的交通网络,也可以认为是数据结构当中的图。
图,是一种比树更为复杂的数据结构。树的节点之间是一对多的关系,并且存在父与子的层级划分;而图的顶点(注意,这里不叫节点)之间是多对多的关系,并且所有顶点都是平等的,无所谓谁是父谁是子。
图的术语下面我们来介绍一下图的基本术语:
在图中,最基本的单元是顶点(vertex),相当于树中的节点。顶点之间的关联关系,被称为边(edge)。
在有些图中,每一条边并不是完全等同的。比如刚才地铁线路的例子,从A站到B站的距离是3公里,从B站到C站的距离是5公里......这样就引入一个新概念:边的权重(Weight)。涉及到权重的图,被称为带权图(Weighted Graph)。
还有一种图,顶点之间的关联并不是完全对称的。还拿微信来举例,你的好友列表里有我,但我的好友列表里未必有你。