在字典树中查找根
Find root in dictionary-tree
我有一个这样的字典树：
{ b : [e], a : [b,c], c : [], e : []}
即使我的字典很长，我如何才能快速找到词根（在此示例中为“a”）？
遍历邻接表，将每个"from"个节点放入一组源节点，将其对应的每个"to"个节点放入一组目的节点。
从一组源中减去一组目的地将产生以下结果之一：
- 一个空集 - 这意味着你的邻接表不代表一棵树或一片森林，
- 具有多个节点的集合 - 这意味着您的邻接列表代表一片森林，或者
- 只有一个项目的集合 - 这是您的邻接表所表示的树的根。
以下是您的示例的工作原理：
source: { b, a, c, e }destination: { e, b, c }source \ destination: { a }
在您的示例中，未定义变量 (a、b、c、e)。假设您可以用字符串（甚至整数）替换它们：
d = {'b':['e'], 'a':['b','c'], 'c':[], 'e':[]}
root = set(d).difference(*d.values()).pop()
print(root)
--> a
我有一个这样的字典树：
{ b : [e], a : [b,c], c : [], e : []}
即使我的字典很长，我如何才能快速找到词根（在此示例中为“a”）？
遍历邻接表，将每个"from"个节点放入一组源节点，将其对应的每个"to"个节点放入一组目的节点。
从一组源中减去一组目的地将产生以下结果之一：
- 一个空集 - 这意味着你的邻接表不代表一棵树或一片森林，
- 具有多个节点的集合 - 这意味着您的邻接列表代表一片森林，或者
- 只有一个项目的集合 - 这是您的邻接表所表示的树的根。
以下是您的示例的工作原理：
source:{ b, a, c, e }destination:{ e, b, c }source \ destination:{ a }
在您的示例中，未定义变量 (a、b、c、e)。假设您可以用字符串（甚至整数）替换它们：
d = {'b':['e'], 'a':['b','c'], 'c':[], 'e':[]}
root = set(d).difference(*d.values()).pop()
print(root)
--> a