Python基于回溯法子集树模板实现图的遍历功能示例
作者:罗兵 发布时间:2021-10-29 15:20:31
标签: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,称为一条路径。请找出所有可能的路径。
分析
将这个图可视化如下:
本问题涉及到图,那首先要考虑图用那种存储结构表示。邻接矩阵、邻接表、...都不太熟。
前面这篇文章https://www.jb51.net/article/122927.htm有一种最简洁的邻接表表示方式。
接下来对问题本身进行分析:
显然,问题的解的长度是固定的,亦即所有的路径长度都是固定的:n(不回到出发节点) 或 n+1(回到出发节点)
每个节点,都有各自的邻接节点。
对某个节点来说,它的所有邻接节点,可以看作这个节点的状态空间。遍历其状态空间,剪枝,深度优先递归到下一个节点。搞定!
至此,很明显套用回溯法子集树模板。
代码:
'''
图的遍历
从一个节点出发,不重复地经过所有其它节点后,回到出发节点。找出所有的路径
'''
# 用邻接表表示图
n = 6 # 节点数
a,b,c,d,e,f = range(n) # 节点名称
graph = [
{b,c},
{c,d,e},
{a,d},
{c},
{f},
{c,d}
]
x = [0]*(n+1) # 一个解(n+1元数组,长度固定)
X = [] # 一组解
# 冲突检测
def conflict(k):
global n,graph,x
# 第k个节点,是否前面已经走过
if k < n and x[k] in x[:k]:
return True
# 回到出发节点
if k == n and x[k] != x[0]:
return True
return False # 无冲突
# 图的遍历
def dfs(k): # 到达(解x的)第k个节点
global n,a,b,c,d,e,f,graph,x,X
if k > n: # 解的长度超出,已走遍n+1个节点 (若不回到出发节点,则 k==n)
print(x)
#X.append(x[:])
else:
for node in graph[x[k-1]]: # 遍历节点x[k]的邻接节点(x[k]的所有状态)
x[k] = node
if not conflict(k): # 剪枝
dfs(k+1)
# 测试
x[0] = e # 出发节点
dfs(1) # 开始处理解x中的第2个节点
效果图:
希望本文所述对大家Python程序设计有所帮助。
来源:http://www.cnblogs.com/hhh5460/p/6928465.html
0
投稿
猜你喜欢
- Pillow图像降噪处理由于成像设备、传输媒介等因素的影响,图像总会或多或少的存在一些不必要的干扰信息,我们将这些干扰信息统称为&l
- 前言我们在写应用时,基本都会用到配置文件,从各种 shell 到 nginx 等,都有自己的配置文件。虽然这没有太多难度,但是配置项一般相对
- Python 定义了类型转换函数以将一种数据类型直接转换为另一种数据类型,这在日常和竞争性编程中很有用。本文旨在提供有关某些转换函数的信息。
- Smptp类定义:smtplib.SMTP(host[,port[,local_hostname[,,timeout]]]),作为SMTP的
- 前言本文给大家深入的解答了关于Python的11道基本面试题,通过这些面试题大家能对python进一步的了解和学习,下面话不多说,来看看详细
- 神经网络玩得越久就越会尝试一些网络结构上的大改动。先说意图有两个模型:模型A和模型B。模型A的输出可以连接B的输入。将两个小模型连接成一个大
- Python 相对路径报错:"No such file or directory"'原因及解决方法如果你取相对路
- 本文总结了asp初学者在学习asp过程中可能会碰到的常见问题,并做了详细的解答。1.如何用Asp判断你的网站的虚拟物理路径 答:使用Mapp
- 这篇文章主要介绍了基于python3抓取pinpoint应用信息入库,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习
- 前言可选链操作符(?.)允许读取位于链接对象链身处的属性的值,而不必明确验证链中的每个引用是否有效。不同之处在于,在引用为空(null或者u
- 编者注:当讲到了性能优化和案例方面的东西,就要想到如何从开发人员的角度进行了理解,认识SQL是如何执行,以及如何学习高级的SQL,这篇文章对
- 1、使用说明首先说明,本文所使用的功能为pycharm专业版所支持,其他版本如社区版,教育版,则不一定支持。作为一名后端开发,我猜你的桌面上
- 目录前言前期准备数据的选择与获取分词筛选与可视化总结前言”数据可视化“这个话题,相信大家并不陌生,在一些平台,经常可以看到一些动态条形图的视
- 在 Python 中是没有原生数据类型支持时间的,日期与时间的操作需要借助三个模块,分别是 time、datetime、calendar。t
- JSP 开发之 releaseSession的实例详解Hibernate可以实现分页查询,昨天试了一下,分页效果不错。但是发现了一个问题,就
- asp使用fso对象遍历目录及目录下的文件代码:<%@ Language=VBScript %><%&
- 一。安装python1.到python官网下载安装包注意:班级同学们请到班级资料下载安装包,可以不用到网上下载。点击导航栏download-
- 我用FSO生成了unicode的文件,但这不是我想要的。FSO可以生成utf-8格式编码的html文件吗?用什么办法才能生成?FSO的编码问
- 如下所示:list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] slice = random.sample(list
- 技巧 16:如果页面需要很长时间才能完成,那么执行前使用 Response.IsClientConnected 如果用户性急,他们可能会在您