2

グラフの基本的な幅優先検索トラバーサルについての私の理解は次のとおりです。

BFS        
    Start from any node. 
    Add it to queue. 
    Add it to visited array.

    While queue is not empty:
        Remove head from queue; 
        Print node.

        add all unvisited direct subchilds to que; 
        mark them as visited

ただし、特定のノードから有向グラフをトラバースする必要があり、特定のノードからすべてのノードに (直接的または間接的に) アクセスできるわけではない場合、この状況のグラフをトラバースするために BFS をどのように使用すればよいでしょうか?

このグラフについても説明してください。 

a=> b => d => e => d  
a=> c => d

ここで、開始ノードが である場合、andbは出力されません。ac

アルゴリズムに何か欠けていますか?

HashMap<String, ArrayList> adj = new HashMap();グラフを保存する隣接リストを作成していました。

4

2 に答える 2

1

ただし、特定のノードから DIRECTED グラフをトラバースする必要があり、特定のノードから [直接的または間接的に] すべてのノードにアクセスできない場合、どのように BFS を使用すればよいでしょうか。

検索アルゴリズムはグラフをトラバースします。通過できないエッジがあり、したがって到達できないノードがある場合、検索ではそれらが見つかりません。

于 2010-04-06T04:07:25.900 に答える
0

「任意のノードから開始」の部分を除いて、あなたの理解は正しいです-BFSトラバーサルはルートノードから開始する必要があります。したがって、あなたの例では、ノード a から始める必要があります。そうしないと、あなたが言ったように、決してアクセスすることはありません。

于 2010-04-06T04:06:43.420 に答える