javascript - 创建随机树？

Question

创建随机树（或满足树属性的邻接矩阵）的好方法是什么？我目前有以下要返回的数据结构，但我想随机生成它。有什么建议么？

    return [{
        Source: "A1",
        Target: "A2",
    }, {
        Source: "A2",
        Target: "A3",
    }, {
        Source: "A1",
        Target: "A4",
    }, {
        Source: "A4",
        Target: "A6",
    }, {
        Source: "A4",
        Target: "A7",
    }, {
        Source: "A3",
        Target: "A8",
    }, {
        Source: "A3",
        Target: "A5",
    }];

score 9 · Accepted Answer

一棵有n个节点的树可以用n-2个整数的序列唯一表示（范围为[0, n-1]）。这称为Prüfer 序列。

创建一个随机序列应该没问题。然后你只需要将序列转换为你的树结构就可以了。

score 2 · Accepted Answer

在上述想法的基础上，我们可以生成一个 20 节点标记的随机树（在中python）：

从随机生成的长度为 18 的序列开始，每个元素从集合 {1,2,...,20} 中选择。
使用生成的字符串作为 20 个顶点上完整图 K20 的生成树的 Prufer 序列，并使用以下算法（从此处）生成相应的标记树（因为始终存在 1-1 对应关系）。

下一个代码片段实现了上述算法，以在给定 prufer 序列的情况下生成标记树（通过计算边）：

def get_tree(S):
    n = len(S)
    L = set(range(1, n+2+1))
    tree_edges = []
    for i in range(n):
        u, v = S[0], min(L - set(S))
        S.pop(0)
        L.remove(v)
        tree_edges.append((u,v))
    tree_edges.append((L.pop(), L.pop()))
    return tree_edges

现在，我们总是可以随机生成一个 prufer 序列（长度为 n-2），随后生成相应的生成树（在 n 个顶点上），它可以作为我们的随机树（可以认为是从n^(n-2) 生成树的 Kn)。

n = 20 # Kn with n vertices
N = 25 # generate 25 random trees with 20 vertices (as spanning trees of K20)
for i in range(N):
    S = np.random.choice(range(1,n+1), n-2, replace=True).tolist()
    T_E = get_tree(S) # the spanning tree corresponding to S
    # plot the tree generated (with `networkx`, e.g.,)

下一个动画展示了一些这样随机生成的带有 20 个节点的标记树。

javascript - 创建随机树？

2 回答 2

Related

Reference