图的遍历




















图的遍历问题分为四类:



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

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

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

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


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


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



算法


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



参阅




  • 图论

  • 树的遍历

  • 遍历性




Popular posts from this blog

GameSpot

日野市

Tu-95轟炸機