关于1000顶点稀疏与稠密图邻接表存储值的疑问求解

嘿，咱把这俩数儿拆开唠明白哈！

关于稀疏图的2997个存储值 #

你说的树是最极端的稀疏图，n个节点的树确实只有n-1条无向边，邻接表里每条边存两次，所以1000个节点的树就是2×999=1998个存储值，这个完全没错～

但原回答里的稀疏图可不是树哦！稀疏图的定义是边数远小于完全图，覆盖范围比树大得多。那2997的由来大概率是这两种情况：

• 如果是有向稀疏图：假设999个顶点各有3条出边，剩下1个顶点没有出边，总出边数就是999×3=2997。有向图的邻接表每条边只存一次（仅在起点的邻接列表里记录终点），所以存储的数值数量就是2997。
• 要是硬套无向图的话，2997是奇数，不符合无向图总度数必为偶数的规则，所以更可能是有向图场景，或是原回答做了近似调整（比如把1000个顶点平均3条边的3000，减去3个冗余条目得到2997）。

关于稠密图的3000000个存储值 #

这个就好理解啦，稠密图一般指接近完全图的图。1000个顶点的完全无向图总边数是(1000×999)/2=499500条，每条边在邻接表里存两次，基础条目数是499500×2=999000。

那300万怎么来？这是因为邻接表的存储通常不止记录邻接节点的索引，还会附带边的额外信息（比如权重、流量、标记值等）。假设每条边的每个存储条目包含3个值（比如起点索引、终点索引、边权重），那总存储值就是999000×3=2997000，近似后就是3000000（3百万）。

要是换成完全有向图，总边数是1000×999=999000条，每条边存一次，同样每条条目带3个值的话，结果也是约300万，逻辑完全通顺。

内容的提问来源于stack exchange，提问作者cosmos713