图形从邻接表中的入度计算 [英] Graph In-degree Calculation from Adjacency-list

问题描述

 <$ 
 
 
我遇到了这个问题，它需要根据邻接列表表示计算图的每个节点的入度。 （i，u）∈E
 in-degree [u] + = 1 $ b $，对于每个Adj [i]其中i！= u 
每个u 
 b  

现在根据它的时间复杂度应该是 O（| V || E | + | V | ^ 2），但我提到的解决方案却将它描述为等于 O（| V || E |）。 p>

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

解决方案

O（| V || E |），计算不一致的复杂度为O（| E |）。让我们考虑下面的伪代码来计算每个节点的不完整性：对于每个u
indegree [u] = 0，

  ; 
 
每个u 
每个v \in Adj [u] 
 indegree [v] ++; 
  

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

I came across this question in which it was required to calculate in-degree of each node of a graph from its adjacency list representation.

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

Now according to me its time complexity should be O(|V||E|+|V|^2) but the solution I referred instead described it to be equal to O(|V||E|).

Please help and tell me which one is correct.

解决方案

Rather than O(|V||E|), the complexity of computing indegrees is O(|E|). Let us consider the following pseudocode for computing indegrees of each node:

for each u
  indegree[u] = 0;

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

First loop has linear complexity O(|V|). For the second part: for each v, the innermost loop executes at most |E| times, while the outermost loop executes |V| times. Therefore the second part appears to have complexity O(|V||E|). In fact, the code executes an operation once for each edge, so a more accurate complexity is O(|E|).

这篇关于图形从邻接表中的入度计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！