构建树形结构，以给定的根节点为起点。

Question

寻找一种Python的方式来将树构建为字典，使我们最终得到{13: [11, 8], 11: [], 3: [], 6: [3], 8: [6]}

由于我知道根节点，我的方法是循环遍历具有值为13的条目，并连接它们，然后将这些条目视为根，依此类推。

请注意，没有排序。为了区分，我知道根节点（某个数字），并可以从中确定。

是否有更好的方法？

- SS'

---

应该注意到没有排序，例如第一个条目是父级，第二个是子级。因此，8实际上是5的父级，但是1的子级。为了区分，我知道根并可以从那里确定。 - SS'

树中是否可以有重复元素？ - user3483203

你能够拥有循环依赖吗？就像在图表中的一个循环一样？ - user3483203

没有循环，这是一棵树，无环。 - SS'

你改变了示例，但你并没有改变根源。 - user2357112

Answer 1

通过使用 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: []})

- user3483203

Answer 2

我能想到的最符合Python风格的方式，也是最快的方式如下：

def dfs(es, s):
    graph = {}
    for x, y in es:
        graph.setdefault(x, set()).add(y)
        graph.setdefault(y, set()).add(x)

    tree, stack = {}, [s]
    while stack:
        parent = stack.pop()
        children = graph[parent] - tree.keys()
        tree[parent] = list(children)
        stack.extend(children)
    return tree

edges = [[1, 2], [5, 8], [1, 8], [3, 5]]
print(dfs(edges, 1))

输出

{8: [5], 1: [8, 2], 2: [], 3: [], 5: [3]}

上述方法在图的大小上是线性的，复杂度为O(N + E)，其中N是节点数，E是边数。虽然速度较慢，但更简单的方法是：

egdes = [[1, 2], [1, 8], [5, 8], [3, 5]]
tree = {}
sources = {1}


while sources:
    parent = sources.pop()
    children = [t for s, t in egdes if (s == parent and t not in tree)] + \
               [s for s, t in egdes if (t == parent and s not in tree)]
    tree[parent] = children
    sources.update(children)

print(tree)

输出

{8: [5], 1: [2, 8], 2: [], 3: [], 5: [3]}

更快的方法是删除已经看到的边缘：

while sources:
    parent = sources.pop()
    children = [y if x == parent else x for x, y in edges if parent in (x, y)]
    edges = [edge for edge in edges if parent not in edge]
    tree[parent] = children
    sources.update(children)

输出

{8: [5], 1: [2, 8], 2: [], 3: [], 5: [3]}

- Dani Mesejo

Answer 3

递归方法：

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: []}

- blhsing

Answer 4

你可以使用广度优先搜索：

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: []})

- Ajax1234

Answer 5

d = [[1,2], [1,8], [5, 8], [3, 5]]
def t(d, r):
    o = {r: []}
    while d:
        e = d.pop(0)
        if e[1] in o:
            e = e[::-1]
        if e[0] in o:
            o[e[0]].append(e[1])
            o[e[1]] = []
        else:
            d.append(e)
    return o
print(t(d, 1))

这将输出：

{1: [2, 8], 2: [], 8: [5], 5: [3], 3: []}

- blhsing

---

更大的树会出现中断。 - SS'

已修复。不再假定包含父节点的边在包含子节点的边之前。 - blhsing