javascriptpython-3.xalgorithmgraphgraph-theory

Creating a random tree?


What is a good way of creating a random tree (or an adjacency matrix that satisfies tree properties)? I currently have the following data structure that I am returning but I would like to generate this randomly. Any suggestions?

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

Solution

  • A tree with n nodes can be uniquely expressed by a sequence of n-2 integer numbers (in the range of [0, n-1]). This is called the Prüfer sequence.

    Creating a random sequence should be no problem. Then you just have to transform the sequence to your tree structure and you're done.