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

Question

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

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

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

[1,4]---->(1 is the parent node and 4 is child node)

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

请提供有关如何实施的任何想法？提前致谢

Answer 1

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

所以：

获取我们称之为possible_roots
迭代边列表并从我们上面的列表中删除子节点possible_roots
如果是树，则possible_roots中一定只剩下一个元素。这是你树的根。

Answer 2

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

这是一种方法：

首先定义一个节点class:

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 class:

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

并用它来打印树：

print(root)

这个print方法只是一种非常简单的可视化树的方法。代码再多一点也可以画出树的分支，但这已经足够调试代码了。

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)

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

How to convert a list of edges to a tree in python?

python

algorithm

tree

binary-tree

graph