Python算法——树的拓扑排序

Echo_Wish

发布于 2023-11-30 19:44:19

29500

代码可运行

文章被收录于专栏：数据结构和算法数据结构和算法

运行总次数：0

代码可运行

Python中的树的拓扑排序

拓扑排序是一种对有向无环图（DAG）进行排序的算法。在树结构中，树是一种特殊的有向无环图，因此我们可以将拓扑排序应用于树的节点。

拓扑排序算法

拓扑排序算法通常使用深度优先搜索（DFS）来实现。基本思想是从根节点开始，依次访问每个节点，并将节点加入结果列表。在访问节点时，递归地遍历其子节点。当一个节点的所有子节点都被访问完后，将该节点加入结果列表。

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.children = []

def topological_sort(root):
    result = []

    def dfs(node):
        if not node:
            return
        for child in node.children:
            dfs(child)
        result.append(node.val)

    dfs(root)
    return result

示例

考虑以下树结构：

1 / 2 3 / \ 4 5 6

# 构建树
root = TreeNode(1)
root.children = [TreeNode(2), TreeNode(3)]
root.children[0].children = [TreeNode(4), TreeNode(5)]
root.children[1].children = [TreeNode(6)]

# 进行拓扑排序
result = topological_sort(root)
print("拓扑排序结果:", result)

输出结果：