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] の範囲) のシーケンスによって一意に表現できます。これはプリューファー数列と呼ばれます。

ランダムなシーケンスを作成することは問題ありません。次に、シーケンスをツリー構造に変換するだけで完了です。

score 2 · Accepted Answer

上記のアイデアに基づいて、20 ノードのラベル付きランダムツリーを生成する方法を次に示します (図 3 python)。

セット {1,2,...,20} から選択された各要素を持つ、ランダムに生成された長さ 18 のシーケンスから開始します。
生成された文字列を 20 個の頂点上の完全なグラフ K20 のスパニングツリーの Prufer シーケンスとして使用し、次のアルゴリズムを使用して対応するラベル付きツリーを生成します (常に 1 対 1 の対応があるため) (ここから)。

次のコードスニペットは、上記のアルゴリズムを実装して、(エッジを計算することにより) プルーファーシーケンスが与えられたラベル付きツリーを生成します。

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

これで、常にプルファーシーケンス (長さ 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