階層ツリーは幅優先または深さ優先のいずれかによるトラバースが可能です。これらの検索は、次の表に示すように略記します。
略語 | 定義 |
---|---|
BFS | 幅優先検索 幅優先のレポーティングを参照してください。 |
DFS | 深さ優先検索 深さ優先レポーティングを参照してください。 |
BFSではノードの直接の子はそれぞれ、その孫よりも前に検索されます。
DFSでは、グラフ内の各直接ノードの子孫はすべて、そのノードのその他の直接の子の前に検索されます。
次の部品階層のグラフを考えます。
このグラフが幅優先で検索される場合、そのノードの検索順序は次のようになります。
p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12
一方、このグラフが深さ優先で検索される場合、そのノードの検索順序は次のようになります。
p1 p2 p5 p6 p7 p3 p8 p9 p4 p10 p11 p12
BFSを指定する場合とDFSを指定する場合の実質効果は、結果セットの順序付けです。そのため、出力の単純な順序付けによって簡単にBFSまたはDFSがシミュレーションされます。