1
我正在解决这个CLRS问题，它要求找出图的每个顶点的indegree G(V,E)。我发现解决方案为O(|E|)，因为我们只需扫描所有边来找出所有顶点的度数。邻接列表indegree
但我在网上找到的大多数解决方案都说它是O(|V|+|E|)。怎么来的？顶点如何占用时间？
A
回答
0
如果我们假设图的实现使用顶点对象，并且每个顶点都有一个关联的后继列表并且没有附加的数据结构，那么直接迭代边将是不可能的。
如果有向图连通，那么每个vertext至少有一个关联的边。这意味着通过迭代遍历顶点遍历顶点需要O(|E|)时间 - 顶点迭代不会增加运行时间，这是由边的数量决定的。
如果有向图是而不是连接，那么在顶点上的迭代不一定由边的数量支配;即使是孤立的顶点也必须进行处理以发现它们没有关联的输出弧，这可以在O(|V|+|E|)时间内完成。
总之，无论哪种情况，O(|V|+|E|)的运行时限都是正确的;然而，对于连接的有向图（或允许直接在边上迭代而不管顶点的数量如何的实现），可以获得更加严格的运行时限为O(|E|)。