こなさんち

しがないフリーランスエンジニアの備忘録。

基礎理論~グラフ理論(木構造の巡回)~

初めに

前回の記事では、木構造について紹介しました。

今回は、データの探索方法についてです。

データの探索とは?

木構造なので各節の値を行ったり来たりして、「目的のデータはどこじゃろかい」と探します。

「ここかな?ちがう」「ここも違う」と繰り返して、次の節を見に行くんです。

この次の節の選び方を巡回方法といいます。

巡回方法

巡回方法は「このデータを見つけるまでに、この方法を使用すると何回の巡回で見つかりますか?」という問題にて使用されます。

幅優先順

f:id:cresta522:20190630225137p:plain
幅優先順

深さ優先順(先行順)

親が先行します。

f:id:cresta522:20190630230330p:plain
先行順

深さ優先順(中間順)

親が中間にいます。

f:id:cresta522:20190630230442p:plain
中間順

深さ優先順(後行順)

親が最後 です。

f:id:cresta522:20190630230643p:plain
後行順