1

次の有向グラフの実装があります

 Nodes nod[]
 List<Arcs> arc[]

したがって、n 番目の位置にあるノードには、リストのすべてのアークが位置 n にあります。もちろん、ノードはそれに応じて編成されているため、バイナリ検索を使用できます。この実装に基づいています。DFS アルゴリズムを作成したいと考えています。私は疑似コードをよく知っているので、Java に適応することは問題にならないはずです。

しかし、私の質問は次のとおりです。DFS では、「トップ」ノードから検索を開始する必要があります。考えてみると、この「トップ」ノードはありません。また、入手方法がわかりません。だから私は、私の実装を考慮して、どうすればこのトップノードを取得できますか?

助けてくれてありがとう。

4

2 に答える 2

2

私のコメントを拡張します：

アークが方向付けられている (つまり、親ノードから子のみ) と仮定すると、すべてのノードを検索して、入ってくるアークがないノードを探すことができます。

// parent_count is an integer array of the same size as nod[]

for i = 1..n
    for each arc in arc[i] (arc going from i to j)
        increment parent_count[j]
    end
end

for k = 1..n
    if parent_count[k] == 0
        return k
end
于 2012-10-12T20:23:38.643 に答える
0

DFS / BFSは非常に一般的で一般的なアルゴリズムであり、グラフ上を移動します。どちらも最上位ノードの特別な意味はありません。どのノードからでもDFSを開始できます。たとえば、DFSはトポロジカルソートアルゴリズムで使用され、入力エッジのないノードから開始する必要があると述べています。

解決したい問題を強調していただけますか？これは、DFSのルートとして使用する必要のあるノードを見つけるのに役立ちます。

于 2012-10-12T20:07:22.150 に答える