如何在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個頂點的樹？

回答

相關問題