Как я могу генерировать случайное (не обязательно двоичное) дерево? - PullRequest
Новая
       38

Как я могу генерировать случайное (не обязательно двоичное) дерево?

0 голосов
/ 12 мая 2019

Я изучаю структуры данных и пытаюсь написать программу, которая создала бы мне дерево (не обязательно двоичное), которое содержит n вершин. До сих пор я пробовал последовательность Prufer, и она хорошо работает для меня - это очень интересное решение проблемы. Я нашел бумагу с алгоритмом быстрой генерации случайного дерева (стр. 881-882).

На самом деле, меня не волнует скорость генерации, но этот метод должен быть быстрее генерации дерева из последовательности Пруфера. Я написал код для его генерации, и я не уверен, что он работает правильно. Что-то не так с моим кодом или методом, представленным выше. Ниже я покажу, что я произвел. Код написан на Python3. Обратите внимание, что я изменил индексирование, так как Python 0-indexed. 

import random


def fast_random_tree(n):
    """
    https://link.springer.com/content/pdf/10.1007/3-540-44862-4_95.pdf
    """
    I = list(range(n))  # Initial vector of node numbers
    root = random.randint(0, n - 2)  # choosing root
    I[root], I[-1] = I[-1], I[root]  # replacing with last value
    edges = [None for _ in range(n - 1)]
    for m in range(n - 1):
        t = random.randint(0, m)  # new node
        s = random.randint(m + 1, n - 1)
        edges[m] = (I[t], I[s])  # adding edgde 
        I[t], I[n - m - 1] = I[n - m - 1], I[t]  # replaceing from n-m+1 to n - nodes that are in a tree already

    return edges


if __name__ == '__main__':
    edges = fast_random_tree(5)
    print(edges)

Иногда я получаю набор ребер, которые не создают дерево, потому что оно содержит циклы или граф не полностью связан. Пример: 

>>> print(fast_random_tree(5))
[(0, 4), (0, 3), (1, 2), (2, 1)]

  0      1
 / \     |
4   3    2

который явно не дерево. Меня также беспокоит то, что корень выбирается случайным образом и перемещается на последнюю позицию в массиве, но он никогда не может быть связан с какой-либо другой вершиной.

Я о чем-то забыл или просто этот алгоритм не работает? Если вы знаете другие алгоритмы для генерации случайного дерева, я хотел бы прочитать об этом. Спасибо за любую помощь заранее!

...