如何从给定图中的项目子集进行拓扑排序？

Question

我有以下问题：给你一个待办事项列表，其中一些项目依赖于其他项目。编写一个函数，该函数接受这些待办事项的子集和 returns 所有要完成的待办事项的有序列表。给定的子集包含这些待办事项中的一个或多个。

我使用 Kahn 算法编写了拓扑排序，将给我的列表转换为邻接列表。当我有待办事项的有序列表时，我开始将它们添加到另一个数组中，并在它包含给定子集中的所有项目时停止。

这行得通，但我觉得它有点笨拙且效率低下，因为我对整个列表进行排序，然后返回截断的版本。

关于如何让这个解决方案更优雅一点有什么想法吗？

Answer 1

您应该能够检查每个任务是否添加到输出 filteredTasks，而不是进行单独的过滤过程，因为它被处理以添加到 orderedTasks。

由于 orderedTasks 的唯一其他用途是检查其长度，因此您应该可以用计数器替换它。

这可能不会使您的函数更快，但会简化您的代码。

Answer 2

不要认为这是拓扑排序。将此视为“首先执行依赖项，不要执行两次”。这是一个简单的递归函数，只要我们跟踪我们将要做什么以及已经做了什么。

以下 Python 解决方案可能会使这一点更清楚。

def arrange_tasks(dependencies, todo, in_order=None, done=None):
    if in_order is None:
        in_order = []
    if done is None:
        done = set()

    for item in todo:
        # Do we need to?
        if item not in done:
            # Marking it done first avoids deep recursion on dependency loops!
            done.add(item)
            # Make sure that dependencies happened.
            arrange_tasks(dependencies, dependencies[item], in_order, done)
            # And now this can happen.
            in_order.append(item)
    return in_order

print(arrange_tasks(
    {
        'make a sandwich': ['buy groceries'],
        'buy groceries': ['go to store'],
        'go to store': []
    },
    ['buy groceries']
))

如何从给定图中的项目子集进行拓扑排序？

How to do a topological sort from a subset of items from a given graph?

javascript

algorithm

graph

topological-sort