2

私はこのアルゴリズムの質問に苦労しています：

How would I write a theta(m+n) algorithm that prints the in-degree and the out-degree of every vertex in an m-edge, n-vertex directed graph where the directed graph is represented using adjacency lists.

4

2 に答える 2

7

注:簡潔にするために、シータの代わりに「O」を使用しています。

BFS は必要ありません。

隣接リストが有向辺のリストで構成されている場合、2 つの頂点カウント マッピングを維持します。各頂点は、最初はゼロにマップする必要があります。次に、各エッジを反復処理し、u,vout-degree(u) と in-degree(v) をインクリメントします。すべてのエッジを反復処理した後、各頂点を反復処理し、その結果をマッピングから出力できます。各エッジの反復は O(m)、各頂点の反復 (マッピングを初期化するために 1 回、実際に出力するために 1 回) は O(n) です。それらの合計は O(m+n) です。

コード例:

#python-ish, untested

V = set([1,2,3,4,5])
#{(u,v}
E = set([(1,2),(1,3),(2,3)])

in_degree_count = {}
out_degree_count = {}

#initialize the mappings to 0
#O(n)
for u in V:
  in_degree_count[u] = 0
  out_degree_count[u] = 0

#iterate through each edge, incrementing the respective mappings for u,v
#O(m)
for u,v in E:
  out_degree_count[u] += 1
  in_degree_count[v] += 1

#iterate through each vertex to print them
#O(n)
for u in V:
  print 'out_degree({0}):'.format(u), out_degree_count[u]
  print 'in_degree({0}):'.format(u), in_degree_count[u]

頂点数のマッピングには、任意の連想マップを使用できます。ハッシュマップを使用すると、償却された一定時間の操作が得られ、アルゴリズム全体の複雑さには影響しません。ただし、[1,n] のように、頂点がギャップのない範囲内にあることがわかっている場合は、値を持つ頂点を表すインデックスを使用して、カウントの配列を使用できます。そう：

in_degrees = [0] * (n + 1) #array/list of zeros, of size n,
                           # index 0 is disregarded since there is no vertex named 0
in_degree[1] = 0 # will mean that vertex `1` has an in-degree of zero.
etc.

これにより、一定時間のマッピング操作が明確に得られます。

于 2012-09-19T18:01:01.147 に答える
1

各ノードのハッシュ テーブルを維持し、それをゼロに初期化します。ハッシュ テーブル内の頂点の現在の頂点増分値 (ヒットされている) に隣接する頂点にヒットするたびに、BFS を実行します。上記の方法は、頂点のイン次数用です。ノードが接続されているときはいつでも、その値を1つ増やして反復します（BFS））。

于 2012-09-18T06:59:46.323 に答える