请查看原文:
http://www.ibaiyang.org/2012/12/09/%E6%A0%91%E7%AE%97%E6%B3%95%E6%9C%80%E5%A5%87%E8%91%A9%E7%9A%84python%E4%BB%A3%E7%A0%81/
这一个月是最苦逼的日子,因为在深圳先进研究院的最后实习的日子里,我和我导师在为了siggraph奋斗着,也希望能在本科阶段发上一篇论文,哈哈。
空闲之余,来分享一下研究过程中用到的一个树的算法吧。本算法的目的非常简单,就是剔除树的中间节点,保留分支节点。如下图要求:
转化如下
以上图是由http://www.graphviz.org/doc/info/lang.html生成
附上代码:
- def reduced_graph(subtree, v, graph):
- n = graph[subtree]
- if len(n) == 0:
- v[subtree] = []
- return [subtree]
- elif len(n) == 1:
- r = reduced_graph(n[0], v, graph)
- v[subtree] = r
- if len(v[n[0]]) == 1:
- del v[n[0]]
- return v[subtree]
- else:
- next_sub = []
- for c in n:
- r = reduced_graph(c, v, graph)
- next_sub.append(r[0])
- if len(v[c]) == 1:
- del v[c]
- v[subtree] = next_sub
- return [subtree]
调用方法:
- v = {}
- graph = {0:[1], 1:[2], 2:[3, 4], 3:[5], 4:[6], 5:[7,8], 6:[9], 9:[], 7:[11], 11:[], 8:[]}
- root = 0
- reduced_graph(root, v, graph)
图表示方法是:邻接矩阵表示法。
为什么说这个python代码非常奇怪呢,因为reduced_graph函数本身也返回值,其实参数V也是返回值。等项目结束后,希望能重构一下这个奇葩的代码。
在过程中还发现 len(n) == 0 没有 n==[] 高效,我也测试了二者的代码,后者快了N倍,可能是由于函数调用开销比较大吧。
-----------------打造高质量的文章 更多关注 把酒泯恩仇---------------
为了打造高质量的文章,请 推荐 一下吧。。。。谢谢了,请关注我后续的文章,会更精彩哦
请关注sina微博:http://weibo.com/baiyang26
把酒泯恩仇官方博客:http://www.ibaiyang.org 【推荐用google reader订阅】
把酒泯恩仇官方豆瓣:http://www.douban.com/people/baiyang26/
如果您想转载本博客,请注明出处
如果您对本文有意见或者建议,欢迎留言
分享到:
相关推荐
Entropy = 系统的凌乱程度,使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。 决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点...
Hoeffding 树算法的 Python 实现,也称为超快速决策树 (VFDT)。 霍夫丁树是用于数据流中分类任务的决策树。 这个实现最初是基于Weka的 Hoeffding Tree 以及 Geoff Hulten 和 Pedro Domingos 的原创作品,VFML。...
1、资源配合博文《【python代码实现】决策树分类算法》、《【python代码实现】朴素贝叶斯分类算法》、《【python代码实现】人工神经网络分类算法及其实战案例(股票价格波动分析)》实操可掌握: 2、决策树分类算法...
资源中包含完整的C4.5决策树算法Python代码和测试数据,其中有4个文件:C45.py是算法的实现代码,treePlotter.py是绘制决策树代码,PlayData.txt是样本数据,C45test.py用来构建、绘制并测试决策树,您可以运行该...
资源中包含完整的C4.5决策树算法Python代码和测试数据,其中有4个文件:C45.py是算法的实现代码,treePlotter.py是绘制决策树代码,PlayData.txt是样本数据,C45test.py用来构建、绘制并测试决策树,
决策树算法C5.0-in-Python-master
鲸鱼优化算法python源代码
报告(全英文)图像处理-图片找不同Find the differences of the two images #Matlab下调用Python接口#SIFT算法应用 博客链接: https://blog.csdn.net/qq_34243930/article/details/85316240
鲸鱼优化算法python代码
以接近Matlab代码的编程结构,采用Python语言实现了基于非支配排序的多目标遗传算法——NSGAII,注释丰富,程序易于理解,所采用的主要是“创建函数-调用函数”模式。 首先根据搜集到的数据绘制目标问题的理论非劣...
在 Python 中使用 MUSIC 和 ESPRIT 算法估计到达方向 效果展示: https://github.com/dengjunquan/DoA-Estimation-MUSIC-ESPRIT/blob/master/Figure_1.png
用于最小化基准函数的引力搜索算法 (GSA) 的 Python 代码
粒子群算法python代码
灰狼优化算法python代码
最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最
python 机器学习-决策树算法实现
python代码 算法设计 源代码 python代码 算法设计 源代码 python代码 算法设计 源代码 python代码 算法设计 源代码 python代码 算法设计 源代码 python代码 算法设计 源代码 python代码 算法设计 源代码 ...
数学建模常用的30个常用算法(Python代码)数学建模常用的30个常用算法(Python代码)数学建模常用的30个常用算法(Python代码)数学建模常用的30个常用算法(Python代码)数学建模常用的30个常用算法(Python代码)数学建模...
该资源是Eclat算法Python实现代码,简洁实用。
2014 年 段 海 滨 教 授 通 过 归 纳 总 结 , 提 出 鸽 群 算 法(Pigeon-inspired Optimization PIO),PIO 是模拟鸽子归巢行为而设计出来的群智能优化算法。PIO 具有原理简明的特点、需要调整参数极少、易于被...