幅優先検索と深さ優先検索 - Advanced SQL Engine - Teradata Database

Teradata Vantage™ - SQLデータ定義言語 詳細トピック

Product
Advanced SQL Engine
Teradata Database
Release Number
17.05
17.00
Published
2020年6月
ft:locale
ja-JP
ft:lastEdition
2021-03-30
dita:mapPath
ja-JP/jpx1556733107962.ditamap
dita:ditavalPath
ja-JP/jpx1556733107962.ditaval
dita:id
B035-1184
Product Category
Software
Teradata Vantage

階層ツリーは幅優先または深さ優先のいずれかによるトラバースが可能です。これらの検索は、次の表に示すように略記します。

略語 定義
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がシミュレーションされます。