如何在O(1)时间复杂度下获取邻接表长度以计算图节点度数

绝大多数主流编程语言的内置序列类型（比如Python的list、C++的std::vector、Java的ArrayList）本身已经内置了存储长度的元字段，调用对应的长度获取接口就是原生O(1)时间复杂度，不需要额外改造：

• C中调用std::vector.size()，C11及之后标准明确要求该操作复杂度为常数
• Python中调用len(adj[u])，底层直接取列表维护的ob_size字段，无额外遍历开销
• Java中调用ArrayList.size()，直接返回类内部维护的size变量，O(1)完成查询

如果你的实现场景用的是自定义的邻接表结构（比如手动实现的链表式邻接表，没有内置长度字段），可以根据图的动静态特性选择以下两种方案，都能满足O(1)度数查询要求：

方案1：预计算度数数组（适合静态图，无动态边更新） #

在接收邻接表输入的初始化阶段，遍历一次所有顶点的邻接表，把每个顶点的度数预存在一个独立的degree数组里，后续所有查询直接取degree[u]即可：

// C++示例代码
int n = 邻接表顶点总数;
vector<int> degree(n);
// 预计算仅执行1次，总时间复杂度O(n+m)，m为总边数，属于初始化固定成本，不影响后续算法复杂度统计
for (int u = 0; u < n; u++) {
    degree[u] = adj[u].size();
}
// 后续任意查询度数操作都为O(1)

该方案不需要修改原有邻接表结构，是静态图算法场景下最常用的实现方式，完全符合论文算法复杂度的论证要求。

方案2：邻接表绑定长度字段（适合动态图，需要频繁加/删边） #

如果你研究的是动态图算法，需要支持边的动态插入删除，可以自定义邻接表节点结构，把邻接表和对应的长度字段绑定存储，每次修改邻接表的时候同步更新长度字段：

# Python示例代码
class AdjNode:
    def __init__(self, neighbors):
        self.neighbors = neighbors
        self.degree = len(neighbors) # 初始化时同步计算长度
    
    def add_edge(self, v):
        self.neighbors.append(v)
        self.degree += 1 # 加边同步更新度数
    
    def remove_edge(self, v):
        self.neighbors.remove(v)
        self.degree -= 1 # 删边同步更新度数

后续查询度数直接取adj[u].degree即可，全程O(1)，不需要每次遍历邻接表统计长度。

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