performance - 有向グラフを転置するコストは?

Question

元のグラフで DFS を実行し、新しいノードが検出されたときにミラーの隣接リストを生成することにより、有向グラフの転置を構築しようとしています。

これの計算時間はどれくらいになるでしょうか? DFS が O(|V| + |E|) を取ることは知っていますが、隣接リストの作成についてはどうでしょうか? DFS を介して転置の隣接リストを作成するのにどのくらいの時間がかかりますか?

Answer 1

グラフに項目を O(1) 挿入する場合 (頂点ルックアップにハッシュテーブルまたはハッシュマップを使用するか、頂点が整数で表されている場合は配列を使用すると仮定)、漸近的な実行時間は DFS と変わらないはずです。

正直なところ、実際に DFS を実行する必要はないと思います。各頂点の隣接リストを反復処理してから、そのようにエッジを追加できると思います。実行時間は O(V+E) のままなので、理論的には問題ありません。

また、グラフがエッジ リストとして表されている場合、転置グラフを作成するのは O(E) になると思いますが、それにはグラフを接続する必要があると思います。

余分な情報が多すぎて申し訳ありません。お役に立てれば幸いです。