天天看点

python 回溯法 子集树模板 系列 —— 8、图的遍历

一个图:

A --> B

A --> C

B --> C

B --> D

B --> E

C --> A

C --> D

D --> C

E --> F

F --> C

F --> D

从图中的一个节点E出发,不重复地经过所有其它节点后,回到出发节点E,称为一条路径。请找出所有可能的路径。

将这个图可视化如下:

python 回溯法 子集树模板 系列 —— 8、图的遍历

本问题涉及到图,那首先要考虑图用那种存储结构表示。邻接矩阵、邻接表、...都不太熟。

接下来对问题本身进行分析:

显然,问题的解的长度是固定的,亦即所有的路径长度都是固定的:n(不回到出发节点) 或 n+1(回到出发节点)

每个节点,都有各自的邻接节点。

对某个节点来说,它的所有邻接节点,可以看作这个节点的状态空间。遍历其状态空间,剪枝,深度优先递归到下一个节点。搞定!

至此,很明显套用回溯法子集树模板。

python 回溯法 子集树模板 系列 —— 8、图的遍历