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

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

Product
Advanced SQL Engine
Teradata Database
Release Number
17.10
Release Date
2021年7月
Content Type
プログラミング リファレンス
Publication ID
B035-1184-171K-JPN
Language
日本語 (日本)

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

略語 定義
BFS 幅優先検索

幅優先のレポーティングを参照してください。

DFS 深さ優先検索

深さ優先レポーティングを参照してください。

BFSではノードの直接の子はそれぞれ、その孫よりも前に検索されます。

DFSでは、グラフ内の各直接ノードの子孫はすべて、そのノードのその他の直接の子の前に検索されます。

次の部品階層のグラフを考えます。


12ノードから構成される部品階層

このグラフが幅優先で検索される場合、そのノードの検索順序は次のようになります。

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