graph - Mathematica 中具有特定分支因子的随机树

Question

您知道是否有可能以某种方式生成具有特定分支因子的随机树图？我不希望它是一个 k-ary 树。

如果我可以同时定义分支因子和最大深度，那就太好了。我想随机生成一堆分支因子和深度不同的树。

带有随机整数输入的 TreePlot 返回的东西几乎是我想要的：

TreePlot[RandomInteger[#] -> # + 1 & /@ Range[0, 100]]

但我想不出一种方法来获得具有特定分支因子的树。

谢谢！

Answer 1

我想我有点晚了，但我喜欢这个问题。而不是在表单中创建树

{0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4}

我将使用以下形式的嵌套调用，其中每个参数都是一个子节点，它代表另一个节点

0[1[2, 3, 4], 5]

两种形式是等价的，可以相互转化。

Row[{
  TreeForm[0[1[2, 3, 4], 5]],
  TreePlot[{0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4}]
  }]

以下是算法的工作原理：作为参数，我们需要一个函数f，它给出随机数量的子节点，并在创建节点时调用。此外，我们有一个深度d，它定义了（子）树可以具有的最大深度。

1. [选择分支]定义一个f可以调用的分支函数，f[]并返回随机数量的子节点。如果你想要一棵有 2 个或 4 个孩子的树，你可以使用 eg f[] := RandomChoice[{2, 4}]。将为树中每个创建的节点调用此函数。

2. [Choose tree-depth]选择树的最大深度d。在这一点上，我不确定您希望将随机性纳入树的生成中。我在这里所做的是，当创建一个新节点时，它下面的树的深度是在其父节点的深度减一和零之间随机选择的。

3. [创建 ID 计数器]创建一个唯一的计数器变量count并将其设置为零。这将使我们增加节点 ID。创建新节点时，增加 1。

4. [创建节点]增加count并用作节点ID。如果当前深度d为零，则返回一个具有 ID 计数的叶子，否则调用f以决定该节点应该获得多少个子节点。对于每个新孩子，随机选择其子树的深度，可以0,...,d-1为每个新孩子调用 4.。当所有递归调用都返回时，树就建立起来了。

幸运的是，在Mathematica代码中，这个过程不是那么冗长，并且只包含几行代码。我希望你能在代码中找到我上面描述的内容

With[{counter = Unique[]},
 generateTree[f_, d_] := (counter = 0; builder[f, d]);
 builder[f_, d_] := Block[
   {nodeID = counter++, childs = builder[f, #] & /@ RandomInteger[d - 1, f[]]},
   nodeID @@ childs
 ];
 builder[f_, 0] := (counter++);
]

现在您可以创建如下所示的随机树

branching[] := RandomChoice[{2, 4}];
t = generateTree[branching, 6];
TreeForm[t]

或者，如果您愿意，可以使用下一个函数将树转换为接受的内容TreePlot

transformTree[tree_] := Module[{transform},
  transform[(n_Integer)[childs__]] := (Sow[
     n -> # & /@ ({childs} /. h_Integer[__] :> h)]; 
    transform /@ {childs});
  Flatten@Last@Reap[transform[tree]
]

并用它来创建许多随机树

trees = Table[generateTree[branching, depth], {depth, 3, 7}, {5}];
GraphicsGrid[Map[TreePlot[transformTree[#]] &, trees, {2}]]