2

有向グラフのソースは、エッジが入っていないノードです。入力として隣接リスト形式の有向グラフを取り、そのすべてのソースを出力する線形時間アルゴリズムを与えます。

解決：

有向グラフのソースを見つける。各ノードの次数 (入力エッジの数) を保持する配列 in[u] を保持します。ソースの場合、この値はゼロです。

function sources(G)
Input: Directed graph G = (V,E)
Output: A list of G's source nodes
for all u ∈ V : in[u] = 0
for all u ∈ V :
    for all edges (u,w) ∈ E:
      in[w] = in[w] + 1

L = empty linked list
for all u ∈ V :
    if in[u] is 0: add u to L
return L

上記のコードについて特に理解していないのは、最初のコード ブロックの最も内側の for ループです。in[w] = in[w]+1 とは正確には何を意味するのでしょうか。それは各ノードの度数を数えることを意味すると思いますが、それがどのように正確に行われているかを想像することはできません。誰かがこの側面を視覚化するのを手伝ってくれますか

4

1 に答える 1

4

in[w] = in[w] + 1に入るエッジの数を増やしwます。

例が役立つかもしれません：

簡単なグラフを考えてみましょう:

a ---> b

隣接リストの表現は次のとおりです。

a: {b}
b: {}

これで、アルゴリズムはすべての頂点をループします。

の場合a、エッジをループしてのカウント(a,b)を増やします。b

の場合b、エッジはありません。

Nowaの count はまだゼロであるため、ソース頂点です。

于 2013-11-01T08:21:55.833 に答える