分组的拓扑排序

Question

好的，因此在根据输入数据进行拓扑排序时，通常存在多个正确的解决方案，可以根据这些正确的解决方案对图进行“处理”，以便所有依赖项都位于“依赖”它们的节点之前。但是，我正在寻找稍微不同的答案：

假设以下数据： a -> b和c -> d（a必须先于b并且c必须先于d）。
只有这两个限制，我们有多种候选方案：（ ，，a b c d
等）。但是，我正在寻找一种将这些节点“分组”的方法，以便在处理完一组后，下一组中的所有条目都将处理其依赖项。对于上述假设的数据，我正在寻找类似的分组。在每个组内，节点的处理顺序无关紧要（之前或之前，等等，反之亦然），只要在处理第2组中的任何一个之前完成第1
组中的操作即可。a c d b``c a b d``(a, c) (b, d)``a``c``b``d``(a, c)``(b, d)

唯一的附加困难是每个节点应尽可能早地处于组中。考虑以下：
a -> b -> c
d -> e -> f
x -> y

的分组方案在(a, d) (b, e, x) (c, f, y)技术上是正确的，因为x在之前y，一个更佳的解决方案是，(a, d, x) (b, e, y) (c, f)因为x组2中的存在意味着x依赖组1中的某个节点。

关于如何执行此操作的任何想法？

编辑：我想我设法拍了一些解决方案代码。感谢所有提供帮助的人！

// Topological sort
// Accepts: 2d graph where a [0 = no edge; non-0 = edge]
// Returns: 1d array where each index is that node's group_id
vector<int> top_sort(vector< vector<int> > graph)
{
    int size = graph.size();
    vector<int> group_ids = vector<int>(size, 0);
    vector<int> node_queue;

    // Find the root nodes, add them to the queue.
    for (int i = 0; i < size; i++)
    {
        bool is_root = true;

        for (int j = 0; j < size; j++)
        {
            if (graph[j][i] != 0) { is_root = false; break; }
        }

        if (is_root) { node_queue.push_back(i); }
    }

    // Detect error case and handle if needed.
    if (node_queue.size() == 0)
    {
        cerr << "ERROR: No root nodes found in graph." << endl;
        return vector<int>(size, -1);
    }


    // Depth first search, updating each node with it's new depth.
    while (node_queue.size() > 0)
    {
        int cur_node = node_queue.back();
        node_queue.pop_back();

        // For each node connected to the current node...
        for (int i = 0; i < size; i++)
        {
            if (graph[cur_node][i] == 0) { continue; }

            // See if dependent node needs to be updated with a later group_id
            if (group_ids[cur_node] + 1 > group_ids[i])
            {
                group_ids[i] = group_ids[cur_node] + 1;
                node_queue.push_back(i);
            }
        }
    }

    return group_ids;
}

Answer 1

用级别值0标记所有根节点。用级别值parent +
1标记所有子节点。如果正在重新访问节点，即已经分配了一个级别值，请检查先前分配的值是否小于新的值。如果是这样，请使用较高的值对其进行更新，并将其传播给后代。

现在，您拥有与唯一级别标签0 … K一样多的组