数据结构:图,邻接表中,无向图的每个顶点的单链表平均长度为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

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com

数据结构:图,邻接表中,无向图的每个顶点的单链表平均长度为2e&#47;n，怎么算出来的？

数据结构:图,邻接表中,无向图的每个顶点的单链表平均长度为2e/n，怎么算出来的？