如何从给定图中的项目子集进行拓扑排序? [英] How to do a topological sort from a subset of items from a given graph?

问题描述

我有以下问题:给您一个待办事项列表，其中某些项目取决于其他项目.编写一个函数，其中包含这些待办事项的子集，并返回要完成的所有待办事项的有序列表.给定的子集包含一个或多个这些待办事项.

I have the following problem: You are given a todo list, some items of which depend on others. Write a function that takes a subset of those todos and returns an ordered list of all the todos to complete. The given subset contains one or more of these todos.

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

I have written a topological sort using Kahn's Algorithm, turning the list I'm given into an adjacency list. When I have the ordered list of todos, I start adding them into another array and stop when it contains all of the items in the given subset.

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

This works, but I feel like it's a little bit clumsy and inefficient since I am doing a sort on the entire list and then returning a truncated version.

关于如何使此解决方案更加优雅的任何想法?

Any thoughts on how to make this solution a little more elegant?

推荐答案

不要认为这是一种拓扑排序.可以将其视为首先执行依赖项，不要重复执行两次".只要我们跟踪我们将要做的事情和已经完成的事情，这就是简单的递归函数.

Don't think of this as a topological sort. Think of this as "do dependencies first, do not do them twice." Which is simple recursive function as long as we keep track of what we will do, and what has been done.

以下Python解决方案可以使这一点更加清楚.

The following Python solution may make this clearer.

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']
))

这篇关于如何从给定图中的项目子集进行拓扑排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！