计算图平方的复杂性分析

Question

我和我的朋友正在尝试解决 CLRS 问题，但我们对答案感到困惑，更具体地说是最佳算法的时间复杂度：

问题：

有向图 G = (V, E) 的 2 路径是图 G^2 = (V, E^2)，它在节点 (u, v) 之间提供边，当且仅当原始图 G 包含u 和 v 之间最多有两条边的路径。提出一种在给定邻接列表的情况下从 G 计算 G^2 的有效算法。

我的方法：

该算法是一个简单的强力算法（我想不出其他的，简单地添加边缘至少需要这么多步骤）。迭代所有节点及其所有边，并为每个邻居将其所有邻居添加到相关节点的邻接列表中。对所有节点重复此操作。

我知道运行时间是 T = V + E + 所有向量的（以度数 * 出度数）之和。我只是不知道如何描述最后一项的复杂性。我知道这是正确的，因为在考虑 n 的直接邻居时，以及当节点 n 本身被视为直接邻居（可以通过入度来测量）时，每个节点 n 的邻居都会被访问，并且所有出度节点都将被访问每次都添加到相应的邻接表中。因此，运行时间是（入度 + 1）* 出度所有节点的总和。这可以简化如下：

SUM over nodes (in(v) + 1) * out(v)
SUM in(v) * out(v) + out(v)
SUM in(v) * out(v) + SUM out(v)
SUM in(v) * out(v) + E (since SUM in(v) = SUM out(v) = E for any graph)

因此总复杂度为 V + E + SUM in(v) * out(v)。

有没有办法简化最后一项？

无法量化，我采取了不同的方法，得到了 O(VE + V) ~ O(VE)，其中涉及将一个节点添加到源节点转置的邻接表中。 ChatGPT 坚持认为它是 O(V+E) 但拒绝强调原因。

Answer 1

这需要 O(EV) 时间，扫描邻接列表需要 O(E) 时间并为可到达顶点保留一个哈希表，因此对于每条边 u->v 我们检查 v 的邻接列表，需要 O(V) 时间，添加新术语。