7

有人可以建议我什么时候需要 Level-Order Traversal（解决一些实际/现实生活中的场景）？

4

2 回答 2

6

层序遍历实际上是一种广度优先搜索，本质上不是递归的。

来自：http ://en.wikipedia.org/wiki/Breadth-first_search

广度优先搜索可用于解决图论中的许多问题，例如：

  • 查找一个连接组件中的所有节点
  • 复制集合，切尼算法
  • 找到两个节点 u 和 - v 之间的最短路径（路径长度由边数测量）
  • 测试图的二分性
  • （反向）Cuthill–McKee 网格编号
  • 用于计算流网络中最大流量的 Ford-Fulkerson 方法
  • 二叉树的序列化/反序列化与排序顺序的序列化，允许以有效的方式重新构建树。
于 2012-10-31T10:01:21.493 回答
1

Google Map Direction 一直在使用 Level Order Traversal (BFS)。

算法重复相同的方法，选择离交叉点最近的节点，最终选择长度最短的路线。

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

于 2017-03-31T21:48:09.167 回答