Создание случайного дерева?

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

Дерево с п узлами может быть однозначно выражается в виде последовательности из п-2 целых чисел (в диапазоне [0, N-1]). Это называется Prüfer sequence.

Создание случайной последовательности не должно быть проблемой. Тогда вам просто нужно преобразовать последовательность в свою древовидную структуру, и все готово.