tree - グラフのトラバースとツリーのトラバース

Question

グラフをトラバースする関数は、ツリーをトラバースするのと同じように機能しますか?

Answer 1

ツリーは、有向非循環グラフと呼ばれる特別なタイプのグラフにすぎないので、そうです...幅優先と深さ優先のトラバーサルはどちらもツリーで機能します。

幅優先トラバーサルと深さ優先トラバーサルの違いの詳細な説明を書き出すことはできますが、おそらく間違っていると思います (私はまだコンプ サイエンティストではありません)。

幅優先トラバーサルと深さ優先トラバーサルの唯一の違いは、頂点を処理する順序だけです。幅優先で、頂点を「処理対象」キューに追加すると考えることができます。深さ優先は、頂点を「処理対象」スタックに追加することと考えることができます。頂点を処理するときが来たら (それぞれのデータ構造に頂点が追加された後)、スタックをデキューまたはポップして、次に処理する頂点を取得します。深さ優先トラバーサルの巧妙なバージョンでは、スタックに頂点を追加する代わりに、再帰を使用して頂点を処理します。

これが役に立ったかどうかはわかりません...

Google で簡単に検索すると (幅が広いのか、深さがあるのか​​わかりません) 、BFS と DFS の違いを説明するのに非常に適していると思われるこれが見つかります。さらに深く読みたい場合は、Steve Skiena のThe Algorithm Design Manualもお勧めします。

Answer 2

純粋なツリーではサイクルをチェックする必要がないため、一般的なグラフをトラバースできる関数は、ツリーをトラバースするには過剰かもしれません。それでうまくいきますが、もっと単純なものでもうまくいきます。