图的表示

2019-10-15  本文已影响0人  TomGui

如何理解“图”?

图中的元素我们就叫作顶点(vertex)。图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫作边(edge)。

无向图

我们就拿微信举例子吧。我们可以把每个用户看作一个顶点。如果两个用户之间互加好友,那就在两者之间建立一条边。所以,整个微信的好友关系就可以用一张图来表示。其中,每个用户有多少个好友,对应到图中,就叫作顶点的度(degree),就是跟顶点相连接的边的条数。

有向图

无向图中有“度”这个概念,表示一个顶点有多少条边。在有向图中,我们把度分为入度(In-degree)和出度(Out-degree)。

带权图

在带权图中,每条边都有一个权重(weight),我们可以通过这个权重来表示QQ好友间的亲密度。

邻接矩阵存储方法

邻接矩阵(Adjacency Matrix)

邻接表(Adjacency List)

邻接矩阵存储起来比较浪费空间,但是使用起来比较节省时间。相反,邻接表存储起来比较节省空间,但是使用起来就比较耗时间。

上一篇 下一篇

猜你喜欢

热点阅读