创建一个随机树？

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",
    }];

Answer 1

具有n个节点的树可以由n-2个整数序列(在[0,n-1]的范围内)唯一地表示.这称为Prüfer序列.

创建随机序列应该没问题.然后你只需要将序列转换为你的树结构,你就完成了.

Answer 2

基于上述想法，我们可以生成一个 20 节点标记随机树（参见python）：

1. 从随机生成的长度为 18 的序列开始，每个元素选自集合 {1,2,...,20}。
2. 使用生成的字符串作为 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 个节点的标记树。