邻接表中的图入度计算

Question

我看到了这个问题，需要从邻接表表示法中计算每个节点的入度。

for each u
   for each Adj[i] where i!=u
     if (i,u) ∈ E
         in-degree[u]+=1

现在根据我的理解，它的时间复杂度应该是 O(|V||E|+|V|^2)，但我参考的解决方案却说它等于 O(|V||E|)。

请帮忙并告诉我哪个是正确的。

- silentseeker

Answer 1

与O（|V||E|）不同，计算入度的复杂度为O（|E|）。让我们考虑以下伪代码来计算每个节点的入度：

for each u
  indegree[u] = 0;

for each u
  for each v \in Adj[u]
    indegree[v]++;

第一次循环的复杂度为线性复杂度 O(|V|)。对于第二部分：对于每个 v，最内层循环最多执行 |E| 次，而最外层循环执行了 |V| 次。因此，第二部分似乎具有复杂度 O(|V||E|)。实际上，代码对每条边执行一次操作，因此更准确的复杂度是 O(|E|)。

- Corneliu

---

我不是很清楚。第二部分的外层循环必须执行|V|次，我们无法避免，对吗？那么O|VE|如何变成O|E|呢？ - vijayashankard

是的，外层循环将执行|V|次，但内层循环的执行取决于与该顶点相邻的边数..这将小于|E|(不包括完全图情况)。为了形象化地理解这一点，可以将查找入度视为查看所有边缘。因此，如果图中的边数为O（|E|），则复杂度成比例。 - smasher

嗨，认为它应该是O（|E|）的推理似乎很好。但正如你所说，外部循环确实运行了|V|次。因此，在进行复杂度计算时，我们不考虑什么都不发生的循环吗？像for i in (0,n): do nothing这样的循环的复杂度是n还是1？ - Anshul

此外，复杂度应该是 O(|E|) 还是 O(|E| + |V|) 呢？因为我们至少需要访问 Adj(G) 中的所有顶点行。 - Anshul

Answer 2

根据http://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)Graphs.html第4.2节，使用邻接表表示法查找节点u的前驱非常耗费时间，需要在O(n+m)的时间内查看每个节点列表，其中m是边的总数。

因此，在此处使用的符号中，计算节点入度的时间复杂度为O(|V| + |E|)。

然而，这可以通过使用额外的空间来减少成本。维基还指出：

添加一个带有反向边的图形的第二个副本使我们能够在O(d-(u))的时间内找到u的所有前任，其中d-(u)是u的入度。

实现此方法的软件包示例是Python软件包Networkx。正如您可以从用于定向图的DiGraph对象的构造函数中看到的那样，networkx跟踪self._succ和self._pred，它们是分别表示每个节点的后继和前驱的字典。这使得它能够有效地计算每个节点的in_degree。

- Kurt Peek

Answer 3

O(|V|+|E|) 是正确的答案，因为你在 O(|V|) 中访问每个顶点，并且每次访问一部分边缘，所以总共是 O(|E|)，通常也有 |E|>>|V|，所以 O(|E|) 也是正确的。

- Artanox