有向图的邻接表表示

Question

给定有向图的邻接表表示,计算每个顶点的出度需要多长时间？计算学位需要多长时间？

谢谢

Answer 1

有向图的邻接表表示:

每个顶点的出度

1. 顶点u的图形出度等于Adj [u]的长度.

2. Adj中所有邻接列表的长度之和为| E |.

3. 因此,计算每个顶点的出度的时间是Θ(V + E)

每个顶点的入度

1. 顶点u的入度等于它在Adj中的所有列表中出现的次数.

2. 如果我们搜索每个顶点的所有列表,计算每个顶点的入度的时间是Θ(VE)

3. 或者,我们可以分配一个大小为| V |的数组T. 并将其条目初始化为零.

4. 我们只需要在Adj中扫描一次列表,当我们在列表中看到'u'时递增T [u].

5. T中的值将是每个顶点的in-degrees.

6. 这可以在Θ(V + E)时间内进行,其中Θ(V)附加存储.

Answer 2

两者都是O(m + n)在那里m是边缘的数量，n是顶点的数目。

启动一组计数器，每个顶点一个，内向度一个，外向度一个。

扫描边缘。对于每个边的外顶点，向该顶点的外度计数器添加一个。对于每个边的顶点，向该顶点的度内计数器添加一个。这是O(m)操作。

输出每个顶点的出度和入度计数器，即O(n)。

那就是你得到的O(m + n)。