は、隣接リストの出次数と入次数の計算

Question

質問

隣接リストの出次数と入次数を計算する際に、時間の複雑さを計算します。

私のアプローチ/ダウト

レッツ調整] []は、サイズV V =いいえの配列です。隣接リストを表す有向グラフ の頂点の数。

Iは

頂点U（UはVに属する）の出次数は、実際の頂点の[U]

と

入次数のAdjの長さである、ことを知っているU （uはVに属します）は実際にリストAdjのuのカウントです。どちらの場合も

、私は時間の複雑さは、シータ（V * E）であるべきだと思う

どこV =なし。

外出を計算するために、すべての頂点をスキャンし、各頂点の下でその頂点のすべてのエッジをスキャンするためです。

そして、なぜそれであるThrta（V + E）

私は間違っているところ私を修正してください？

ありがとうございます！

Answer 1

さて、Vの頂点とEのエッジがあるとしましょう。両方双方向と単方向グラフで
は、各エッジE _Iため、我々は2つの頂点V 、V を得ます。エッジの方向を簡単に取得して、特定の頂点の外れ値と余りの値を更新することができます。

例：

頂点：1、2、3、4つの
エッジ：1 - > 2、2 - > 4、3 - > 1、2 - > 3
出次数：0 0 0
入次数：0 0 0 0

パス1：
エッジ1 - > 2
出次数：1 0 0 0
入次数：0 1 0 0

パス2：
エッジ2 - > 4
出次数：1 1 0 0
入次数：0 1 0 1

パス3：
エッジ3 - > 1
出次数。 1 1 1 0
入次数：1つの1 0 1

パス4：
エッジ2 - > 3
出次数：1 2 1 0
入次数：1 1 1 1

そこでここでは、複雑さ（V + E）で得られ、したがって正確に一度、各エッジをループし、各頂点を実行する必要があります。

Answer 2

サイズ| V |の配列arr []を割り当てることができます。そのエントリをゼロに初期化する。それで、Adjのリストを一度スキャンして、リスト内のuを見るとarr [u]をインクリメントするだけです。

arr []の値は、すべての頂点のアウトディグレードになります。これは、Θ（|​​ V |）の追加ストレージでΘ（| V | + | E |）時間で実行できます。