如何构造一个prufer序列？

我们给一棵无根树的节点编上号，每次找到一个编号最小的度为1节点，删除它，并输出与它连接的点的编号，直到只剩下两个节点。

这样，我们就构造出来了一个prufer序列。

通过prufer序列的构造方式我们可以知道：

性质1：一棵节点数为n的树的prufer序列的长度为n-2。

比如，这棵树的prufer序列是2,1,3,3

从这个样例我们也可以知道：

性质2：每一个编号在prufer序列中出现的次数是它在树中的度数\(-1\)。

由prufer序列转化为无根树。

取出prufer最前面的点\(u\)。

每次从点集中找到最小的没有在树中的点\(v\)，连接\(u\),\(v\)。

当点集中只剩2点时，连接这两个点。

最新文章

1. 为.NET Core项目定义Item Template
2. SQL Server存储过程
3. jsp URL中文传值
4. [连载]《C#通讯（串口和网络）框架的设计与实现》- 5.串口和网络统一IO设计
5. TAP/TUN浅析（一）
6. Web之路笔记之四
7. Excel 读写程序 C#源代码下载
8. 【Python】django多对多 查询 ，反查等操作
9. NETMON& Message Analyzer
10. Android对象类系列化public class User implements Parcelable
11. windows下修改apache并发数
12. MySQL插件实现浅析——插件的调用
13. html 提取 公用部分
14. Netbeans rcp中获得本地文件系统路径
15. 在ASP.NET Web API中使用OData的Containment
16. feign的callback设定后，项目启动错误
17. Socket通信原理简介
18. python3学习笔记.1.初体验
19. Linux下TCP/IP内核参数优化
20. Hadoop1.x目录结构及Eclipse导入Hadoop源码项目

热门文章

1. VisualStudio自定义调试工具（GIS）
2. selenium + python + firefox 测试环境的搭建与配置
3. 视图向控制器传参@RequestMapping()和@RequestParam()
4. .NetCore WebApi —— Swagger版本控制
5. Web性能优化：雅虎35条
6. 2019滴滴php面试总结 (包含面试题解析)
7. ThinkPHP架构(一)-TP原理及路径问题及后台实现实例
8. 程序猿的产品思考：2C与2B产品思维的区别
9. MakeDownPad2基本使用
10. 数据结构2_java---栈,括号匹配