数据结构:图,邻接表中,无向图的每个顶点的单链表平均长度为2e/n,怎么算出来的?
发布网友
发布时间:2022-03-27 09:48
我来回答
共1个回答
热心网友
时间:2022-03-27 11:17
这是一个大致粗略的结果。
首先要明确无向图邻接表是如何存储的,那就是以每一个顶点为头结点建立n个单链表,每个链表中的节点(称为边节点)是依附于这一顶点的边,这样每一条边被储存了2次!
给你举一个最简单的例子:图 2——3,,我们把它们中间的边命名为a,则邻接表如下
2——a
3——a
所以粗略算共有2*e个边节点,n个链表,所以平均表长为2e/n
若算上头结点也可以为(2e+n)/n