如何在C++中随机生成n个顶点的树？

-2

给定n：顶点的数量，我想随机生成一个有n个顶点的树。目前，我正在使用random_shuffle（）生成n个顶点的随机序列，以仅生成线性树。但是，我怎样才能使它足够随机地包含其他树型以及C++？如何在C++中随机生成n个顶点的树？

来源

2017-10-12 user3243499

有没有这样一个“纯粹随机”的树;你的意思是，如何在具有n个顶点的树集合上产生一个统一的*概率分布的伪随机树？ –

@MassimilianoJanes是的。 – user3243499

假设你的目标是产生一个伪随机树下面通过一组有n个顶点扎根标记树的均匀概率分布，解决的办法就是产生所谓的Prüfer代码，这是一个均匀地产生随机（n-2） - [1，n]中的数字。

Wiki的文章有准备使用的伪代码：

https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence

但我怎么能做到足够的随机

有没有这样的事情“随机足够的”; you需要指定树分布应该具有哪些属性（并且可能存在多个此类分布）。在有限集合的特殊情况下（例如所有具有n个顶点的树的集合），您始终可以唯一地定义一个均匀分布，但这绝不是“更加随机”，也不是“更自然”，也不是任何事......这取决于你（和你的最终目标）来决定这是否是正确的分配。

来源

2017-10-12 13:17:03

这也是由python的[networkx]（https://networkx.github.io/documentation/stable/reference/generated/networkx.generators.tree.random_tree.html#networkx.generators.tree.random_tree）实现''' 'generators.tree.random_tree'''（支持它的实际重要性）。 – sascha

如何在C++中随机生成n个顶点的树？

回答

相关问题