例如。根为1的[13,11], [13,8], [6, 8], [3, 6]
寻找一种Pythonic式的方法将树构建到字典中,这样我们就有了{13: [11, 8], 11: [], 3: [], 6: [3], 8: [6]}
因为我知道根,所以我的方法是用13循环遍历条目,连接这些条目,然后将这些条目视为根,依此类推。
请注意,没有排序。为了区分,我知道根(某个数字),并可以从那里确定。
有没有更好的方法?
发布于 2018-08-30 10:38:26
通过使用set
来跟踪哪些元素已经添加到字典中,我们可以在O(n)时间内解决这个问题。一般的想法是遍历节点,检查一个节点当前是否在图中,如果是,我们在添加到字典时就知道它是父节点。
from collections import defaultdict
class MyTree:
def __init__(self, data):
self.data = defaultdict(list)
self.seen = set()
for node in data:
self.add_node(node)
for el in self.seen:
if el not in self.data:
self.data[el] = []
def add_node(self, el):
x, y = el
if y in self.seen:
self.data[y].append(x)
else:
self.data[x].append(y)
self.seen.update(el)
在行动中:
arr = [[1,2], [1,8], [5, 8], [3, 5]]
x = MyTree(arr)
print(x.data)
defaultdict(<class 'list'>, {1: [2, 8], 8: [5], 5: [3], 2: [], 3: []})
发布于 2018-08-30 10:42:08
递归方法:
d = [[1,2], [1,8], [5, 8], [3, 5]]
def t(d, r):
o = {r: []}
n = []
for e in d:
if r in e:
if e[1] == r:
e = e[::-1]
o[e[0]].append(e[1])
else:
n.append(e)
for i in o[r]:
o.update(t(n, i))
return o
print(t(d, 1))
这将输出以下内容:
{1: [2, 8], 2: [], 8: [5], 5: [3], 3: []}
发布于 2018-08-30 22:16:43
您可以使用广度优先搜索:
import collections
data = [[1,2], [1,8], [5, 8], [3, 5]]
def bfs(d, _start = lambda x:x[0][0]):
_queue, _result, _seen = collections.deque([_start(d)]), collections.defaultdict(list), []
while _queue:
v = _queue.popleft()
r = [i[0] if i[-1] == v else i[-1] for i in d if v in i]
_r = [i for i in r if i not in _seen]
_result[v].extend(_r)
_queue.extend(_r)
_seen.extend(_r+[v])
return _result
print(bfs(data))
输出:
defaultdict(<class 'list'>, {1: [2, 8], 8: [5], 5: [3], 2: [], 3: []})
https://stackoverflow.com/questions/52088149
复制相似问题