图的遍历




















图与树
搜索算法


  • α–β

  • A*

  • B*（英语：B*）

  • 回溯

  • 集束（英语：Beam search）

  • 贝尔曼-福特

  • 最佳优先（英语：Best-first search）

  • 双向

  • Borůvka（英语：Borůvka's algorithm）

  • 分支限界（英语：Branch and bound）

  • BFS

  • 大英博物馆

  • D*（英语：D*）

  • DFS

  • 深度限制（英语：Depth-limited search）

  • 戴克斯特拉

  • Edmonds（英语：Edmonds' algorithm）

  • 弗洛伊德

  • 边缘搜索

  • 爬山

  • IDA*（英语：Iterative deepening A*）

  • 迭代加深

  • Johnson（英语：Johnson's algorithm）

  • 跳点（英语：Jump point search）

  • 克鲁斯克尔

  • 词典BFS（英语：Lexicographic breadth-first search）

  • LPA*（英语：Lifelong Planning A*）

  • 普里姆

  • SMA*（英语：SMA*）

分类


  • 图算法

  • 搜索算法

  • 算法列表（英语：List of algorithms）

相关主题


  • 动态规划

  • 图的遍历

  • 树的遍历

  • 查

  • 论

  • 编


图的遍历问题分为四类：



  • 遍历完所有的边而不能有重复，即所謂“一笔画问题”或“欧拉路径”；

  • 遍历完所有的顶点而没有重复，即所谓“哈密頓路徑问题”。

  • 遍历完所有的边而可以有重复，即所谓“中国邮递员问题”；

  • 遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。


对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。


第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密顿图的性质。



算法


图的遍历方法有深度优先搜索法和广度(宽度)优先搜索法。



参阅



  • 图

  • 图论

  • 树的遍历

  • 遍历性




-