如何在Python中将边列表转换为树？

Question

我有一个具有以下格式的边列表：

edges=[[1,4],[1,3],[1,2],[3,5],[3,6],[3,7]]

这里，在每条边中，第一个元素是父节点，第二个元素是子节点，即，在

[1,4]---->（1为父节点，4为子节点）

我必须创建一个函数来返回指向树根的指针。起初我尝试创建一本字典，但创建后我无法继续。

请提供有关如何实施此操作的任何想法？

Answer 1

创建树数据结构的方法有很多种...而且Python没有指针数据类型，因此树的根将是一个对象。

这是一种方法：

首先定义一个Node类：

class Node():
    def __init__(self, data=None):
        self.data = data
        self.children = []

然后是主要算法：

def create_tree(edges):
    # Get all the unique keys into a set
    node_keys = set(key for keys in edges for key in keys)
    # Create a Node instance for each of them, keyed by their key in a dict:
    nodes = { key: Node(key) for key in node_keys }
    # Populate the children attributes from the edges
    for parent, child in edges:
        nodes[parent].children.append(nodes[child])
        # Remove the child from the set, so we will be left over with the root
        node_keys.remove(child)
    # Get the root from the set, which at this point should only have one member
    for root_key in node_keys:  # Just need one
        return nodes[root_key]

按如下方式运行：

# Example run
edges = [[1,4],[1,3],[1,2],[3,5],[3,6],[3,7]]
root = create_tree(edges)

如果你想快速验证树的形状，请将此方法添加到

Node

类中：

    def __repr__(self, indent=""):
        return (indent + repr(self.data) + "\n"
                + "".join(child.__repr__(indent+"  ") 
                          for child in self.children))

并用它来打印树：

print(root)

这个输出字符串只是可视化树的一种非常简单的方法。通过更多的代码，您还可以绘制树的分支，但这足以调试代码。

Answer 2

假设它始终是一棵树（因此我们没有两个单独的图），任务是确定哪个数字永远不会出现在第二个位置。

所以：

1. 获取所有数字（节点）的列表，我们称之为

   possible_roots

2. 迭代边列表并从上面的列表中删除子节点

   possible_roots

3. 如果是一棵树，

   possible_roots

   中必须只剩下一个元素。这是你的树的根。

Answer 3

您需要找出哪个顶点没有父顶点。这可以通过构建所有顶点的

set

，然后丢弃具有父级的顶点来完成。

或者，这可以通过一方面构建所有父顶点的集合，另一方面构建所有子顶点的集合来完成；然后采取不同的设置

parents - children

。

那么有三种可能：

• 没有剩下的顶点。这意味着您的有向图包含一个循环，并且没有根。示例：

  [[0,1], [1,2], [2,0]]

  .
• 还剩下多个顶点。这意味着您的有向图包含多个“根”。示例：

  [[0,2], [1,2]]

  .
• 只剩下一个顶点。这一定是根源。

# FIRST METHOD
def get_root(dag):
    candidates = set(parent for (parent,_) in dag)
    for _,child in dag:
        candidates.discard(child)
    assert(len(candidates) == 1) # or handle len(candidates) == 0 and len(candidates) > 1 with an if/elif/else
    return candidates.pop()

# SECOND METHOD
def get_root(dag):
    parents, children = map(frozenset, zip(*dag))
    candidates = parents - children
    root, = candidates  # will raise exception if len(candidates) != 1
    return root

测试：

print( get_root([[1,4],[1,3],[1,2],[3,5],[3,6],[3,7]]) )
# 1

print( get_root([[0,2], [1,2]]) )
# ValueError: too many values to unpack (expected 1)

print( get_root([[0,1], [1,2], [2,0]]) )
# ValueError: not enough values to unpack (expected 1, got 0)