Как быстро выполнить топологическую сортировку дерева из списка?

Question

[AntonGoretskiy]

Здравствуйте!
Имеется список с атрибутами(Name, ID, ParentID), который представляет из себя дерево разного уровня вложенности. Как наиболее быстро восстановить дерево из этого списка? Спасибо

Answer 1

[Миша Кринкин]

Ну например так:

class TreeNode:
    def __init__(self):
        self.children = []
        self.name = None

    def add_child(self, child):
        self.children.append(child)

    def set_name(self, name):
        self.name = name

entries = {}
for entry in data:
    parent = entries.get(entry.ParentID, TreeNode())
    child = entries.get(entry.ID, TreeNode())
    parent.add_child(child)
    child.set_name(entry.Name)
    entries[entry.ParentID] = parent
    entries[entry.ID] = child

root = entries[RootID]

В зависимости от используемого "словаря" (в примере entries) получаем разную сложность. Если, например, известно что ID - это числа от 0 до N, то можно использовать как словарь простой массив - тогда получаем гарантированно O(n), если пишем на C++ и в качестве словаря используем std::map или TreeMap в Java, то O(n log n).

Comments

[AntonGoretskiy]

Спасибо)

Answer 2

[throughtheether]

Я не вполне понял задачу, которую вы пытаетесь решать.

Как быстро выполнить топологическую сортировку дерева из списка?

У вас фактически заданы дуги (arcs) графа. Вы можете из этих данных заполнить более удобную структуру данных (adjacency list, например) и на ней уже запустить алгоритм топологической сортировки. Например, основанный на поиске в глубину. То есть, при помощи DFS (depth-first search, поиск в глубину) ищем ноду (вершину, node, vertex), из которой нет исходящих дуг (sink node), присваиваем ей значение, равное количеству нод, удаляем ее из графа, повторяем. Число - позиция ноды в результирующем списке. Сложность O(m+n), где n - число нод, m - число дуг. Это если вам достаточно топологически отсортированного списка нод.

Как наиболее быстро восстановить дерево из этого списка?

Это уже другой вопрос. Что вы имеете в виду? В каком смысле 'восстановить'? У вас дерево (как частный случай графа) уже задано списком дуг фактически, в каком виде вам его необходимо представить?
Если в виде (Name, ID, ChildID), то мне представляется, что за O(m) можно создать подобную структуру с фактически перевернутыми (относительно заданного дерева) дугами. Для каждого кортежа (Name, ID, ParentID) создаете (или обновляете поле Name, если нода уже существует) ноду (Name, ID), ноду ParentID (если она не создана), у ноды ParentID указываете наследника (child node) ID.

Comments

[AntonGoretskiy]

Есть класс TreeNode с полями (Name, ID, ChildID). Далее есть List - список с экземплярами этих классов.(У самых верхних родителей ChildID=0).
Сейчас это работает так:

ClassifierTree tree = new ClassifierTree();
                foreach (TreeNode Node in Nodes)
                {
                    if (Node.ParentID == 0)
                    {
                        tree.Childrens.Add(Node);
                        Node.Childrens = GetChildsFromList(Node, Nodes);
                    }
                }

private static List<TreeNode> GetChildsFromList(TreeNode Node, List<TreeNode> list)
        {
            List<TreeNode> childs = new List<TreeNode>();
            foreach(TreeNode node in list)
            {
                if (node.ParentID == Node.ID)
                {
                    childs.Add(node);
                    node.Childrens = GetChildsFromList(node, list);
                }
            }
            return childs;
        }

Спасибо

[Миша Кринкин]

@AntonGoretskiy наверно не ChildID, а ParentID?

[AntonGoretskiy]

да)прошу прощения)