从树数据中找到根节点

Question

我有以下 class:

class Category(object):
    def __init__(self, *args, **kwargs):
        self.id = kwargs.get('id')
        self.name = kwargs.get('name')
        self.parent_id = kwargs.get('parent_id', None)

    def get_top_parent_category(self, obj_list):
        # This algorithm is using extensive resource 
        category = self
        while category.parent_id:
            def filter_func(obj):
                return obj.id == category.parent_id
            parent = list(filter(filter_func, obj_list))

            category = parent[0]
        return category

    @classmethod
    def all(cls):
        url = BASE_URL + '/api/v1/categories/'
        response = requests.get(url, headers=headers, verify=False)
        if not response.status_code == 200:
            raise Exception('Error')
        categories = response.json()
        _temp_categories = []
        for _i in categories['results']:
            _temp_categories.append(cls(**_i))
        return _temp_categories

我通过以下方式获取所有类别：

all_categories = Category.all()

现在我需要找到所提供的任何类别的根节点。

category = Category(**category_data)
category.get_top_parent_category(all_categories)

我得到了想要的结果，但我觉得可能有一些更好的方法可以使用图论

找到根节点

解决这个问题的更好方法是什么？

Answer 1

如果您需要对其进行更多与树相关的处理，您可能希望 link 类别对象相互关联，而不是通过父标识符进行间接访问。

但在代码中，您 post 主要问题是这些重复调用，您必须在其中扫描整个对象列表：

parent = list(filter(filter_func, obj_list))

如果你用字典替换它，你的性能会好很多，因为单亲的查找时间将是〜常数时间

例如举个例子

parent_map = dict([(c.id, c) for c in obj_list])

（显然不要在 get_top_parent_category() 方法中执行此操作，因为它同样昂贵）

然后查找类别的父级可以用一个简单的方式完成：

parent = parent_map[parent.id]

您现在拥有的相同循环将以这种方式快一个数量级。

从树数据中找到根节点

finding the root node from tree data

python

tree

graph-theory