本文摘自php中文网,作者巴扎黑,侵删。
这篇文章主要介绍了Python基于回溯法子集树模板实现图的遍历功能,结合实例形式分析了Python使用回溯法子集树模板针对图形遍历问题的相关操作技巧与注意事项,需要的朋友可以参考下本文实例讲述了Python基于回溯法子集树模板实现图的遍历功能。分享给大家供大家参考,具体如下:
问题
一个图:
A --> B
A --> C
B --> C
B --> D
B --> E
C --> A
C --> D
D --> C
E --> F
F --> C
F --> D
从图中的一个节点E出发,不重复地经过所有其它节点后,回到出发节点E,称为一条路径。请找出所有可能的路径。
分析
将这个图可视化如下:
本问题涉及到图,那首先要考虑图用那种存储结构表示。邻接矩阵、邻接表、...都不太熟。
前面这篇文章http://www.jb51.net/article/122927.htm有一种最简洁的邻接表表示方式。
接下来对问题本身进行分析:
显然,问题的解的长度是固定的,亦即所有的路径长度都是固定的:n(不回到出发节点) 或 n+1(回到出发节点)
每个节点,都有各自的邻接节点。
对某个节点来说,它的所有邻接节点,可以看作这个节点的状态空间。遍历其状态空间,剪枝,深度优先递归到下一个节点。搞定!
至此,很明显套用回溯法子集树模板。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
|
效果图:
以上就是实例讲解Python基于回溯法子集树模板实现图的遍历功能的详细内容,更多文章请关注木庄网络博客!!
相关阅读 >>
更多相关阅读请进入《Python》频道 >>
Python编程 从入门到实践 第2版
python入门书籍,非常畅销,超高好评,python官方公认好书。