algorithm - 有向图的邻接表表示

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 中的值将是每个顶点的入度。

6. 这可以在 Θ(V + E) 时间内通过 Θ(V) 额外存储完成。