隣接リストindegree

Question

私はこのCLRSの問題を解決していました。グラフの各頂点の実数を求める質問を受けましたG(V,E)。すべての頂点の次数を見つけるためにすべての辺をスキャンするだけで済むので、解がO(|E|)であることがわかりました。

しかし、ほとんどのソリューションは、私がオンラインで見つけたのはO(|V|+|E|)だと言います。どうして？時間の頂点はどのように考慮されますか？

Answer 1

有向グラフの実装で頂点のオブジェクトが使用され、各頂点に関連する後続のリストがあり、追加のデータ構造がないと仮定すると、エッジを直接反復することは不可能です。

有向グラフが接続されている場合、各頂点には少なくとも1つの関連するエッジがあります。これは、頂点の反復によるエッジの反復は、O(|E|)時間を要することを意味します。頂点の反復は、実行時間を増加させず、エッジの数によって支配されます。

有向グラフがではなく、である場合、頂点の反復は必ずしもエッジの数に支配されません。孤立した頂点であっても、関連する出て行くアークがないことを知るために処理する必要があります。これは、O(|V|+|E|)時に実行できます。

O(|V|+|E|)の実行時境界は、どちらの場合でも正しいです。しかし、接続された有向グラフ（または、頂点の数に関係なくエッジ上で直接的な反復を可能にする実装）の場合、O(|E|)のより厳しい実行時境界を得ることができます。