7

Level-Order Traversal がいつ必要になるか (実用的/現実的なシナリオを解決するために) 誰かが私に提案してもらえますか?

4

2 に答える 2

6

レベル順トラバーサルは、実際には幅優先検索であり、本質的に再帰的ではありません。

出典: http://en.wikipedia.org/wiki/Breadth-first_search

幅優先探索は、グラフ理論の多くの問題を解決するために使用できます。次に例を示します。

  • 1 つの接続されたコンポーネント内のすべてのノードを見つける
  • コレクションのコピー、Cheney のアルゴリズム
  • 2 つのノード u と - v の間の最短パスを見つける (パスの長さはエッジの数で測定)
  • 二部性のグラフのテスト
  • (逆) Cuthill–McKee メッシュの番号付け
  • フロー ネットワークの最大フローを計算するための Ford–Fulkerson 法
  • バイナリ ツリーのシリアライゼーション/デシリアライゼーションと並べ替えられた順序でのシリアライゼーションにより、効率的な方法でツリーを再構築できます。
于 2012-10-31T10:01:21.493 に答える
1

Google マップの方向は、常にレベル オーダー トラバーサル (BFS) を使用しています。

アルゴリズムは、交点に最も近いノードを選択する同じ方法を繰り返し、最終的に最短の長さのルートを選択します。

http://blog.hackerearth.com/breadth-first-search-algorithm-example-working-of-gps-navigation

于 2017-03-31T21:48:09.167 に答える