分组拓扑排序

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

假设以下数据: a -> b 和 c -> d ( a 必须先于 b 和 c 必须先于 d )
在这两个约束条件下,我们有多个候选解决方案:( a b c d , a c d b , c a b d 等等)。但是,我希望创建一个对这些节点进行“分组”的方法,以便在处理完一个组后,下一个组中的所有条目都能处理它们的依赖关系。对于上述假定的数据,我将查找类似 (a, c) (b, d) . 在每个组中,处理节点的顺序无关紧要( 一 之前 C 或 乙 之前 D 等等,反之亦然)只要第1组 (a, c) 在第2组之前完成 (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) 因为有

// 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;
}