给定一个有向图的邻接表表示，计算每个顶点的出度需要多长时间？计算入度需要多长时间？
谢谢
问问题
18194 次
6 回答
13
有向图的邻接表表示：
每个顶点的出度
顶点 u 的图出度等于 Adj[u] 的长度。
Adj 中所有邻接表的长度之和为|E|。
因此计算每个顶点的出度的时间是Θ(V + E)
每个顶点的入度
顶点 u 的入度等于它在 Adj 中所有列表中出现的次数。
如果我们搜索每个顶点的所有列表，计算每个顶点的入度的时间是Θ(VE)
或者，我们可以分配一个大小为 |V| 的数组 T 并将其条目初始化为零。
我们只需要扫描 Adj 中的列表一次，当我们在列表中看到 'u' 时增加 T[u]。
T 中的值将是每个顶点的入度。
这可以在Θ(V + E)时间内通过Θ(V)额外存储完成。
于 2017-08-30T09:25:09.467 回答
7
两者都是边数O(m + n)和顶点数。mn
启动一组计数器，一个用于每个顶点，一个用于入度，一个用于出度。
扫描边缘。对于每条边的出顶点，将该顶点的出度计数器加一。对于每条边的入顶点，将该顶点的入度计数器加一。这是O(m)操作。
输出每个顶点的出度和入度计数器，即O(n).
你就是这样得到的O(m + n)。
于 2013-08-06T04:05:02.020 回答
2
out-degree对于每个vertex:theta(E)
in-degree对于每个vertex:O(E)
E是图的边数
于 2015-07-09T14:51:53.707 回答
1
因为，它是一个有向图，并且只给出了邻接表。
计算出度数所需的时间为 theta (M+N)，其中 M 是顶点数，N 是指边数。
而对于入度数的计数，对于任何节点，您必须计算该节点在所有其他（其余顶点）邻接列表中出现的次数。所以，它需要theta（MN）。
但是，如果您维护一个大小为 M 的数组，那么您可以使用额外的空间存储 theta(M) 来计算 theta(M+N) 中的入度数
于 2015-04-03T05:40:13.303 回答
-1
对于具有 m 个顶点和 n 个边的图，计算入度和出度都需要 theta(m + n)。它是 theta(m+n) 而不是 O(m + n) 的原因是因为无论图形是什么，它都必须经过每个顶点 m 和每个边 n。
于 2013-10-28T00:01:59.783 回答
-2
给定一个有向图的邻接表表示Adj，顶点u的出度等于Adj[u]的长度，Adj中所有邻接表的长度之和为|E|。因此计算每个顶点的出度的时间是 Θ(|V| + |E|)。
顶点 u 的入度等于它在 Adj 中所有列表中出现的次数。如果我们搜索每个顶点的所有列表，计算每个顶点的入度的时间是 Θ(|V|.|E|)。
（或者，我们可以分配一个大小为 |V| 的数组 T 并将其条目初始化为零。然后我们只需要扫描 Adj 中的列表一次，当我们在列表中看到 u 时增加 T[u]。T 中的值将是每个顶点的入度。这可以在 Θ(|V| + |E|) 时间内完成，并带有 Θ(|V|) 额外的存储空间。）
于 2016-06-27T12:16:06.637 回答