performance - 转置有向图的成本？

Question

我试图通过在原始图上运行 DFS 来构造有向图的转置，然后在发现新节点时生成镜像的邻接列表。

这将是什么计算时间？我知道 DFS 需要 O(|V| + |E|) 但是构建邻接列表呢？通过DFS构建转置的邻接表需要多长时间？

Answer 1

如果您将 O(1) 项插入到图形中（假设您使用哈希表或哈希图进行顶点查找，或者如果您的顶点由整数表示，则使用数组），那么渐近运行时应该与 DFS 没有什么不同。

老实说，我认为您实际上不需要进行 DFS。我认为您可以遍历每个顶点的邻接列表，然后以这种方式添加边。运行时间仍然是 O(V+E)，所以理论上，这并不重要。

此外，如果您的图表示为边列表，那么我相信制作转置图只需 O(E)，但我想这需要连接图。

对不起，如果那里有太多额外的信息，我希望我能提供帮助！