拓扑排序与分组

Question

好的,所以在拓扑排序中,取决于输入数据,通常有多个正确的解决方案,可以对图形进行"处理",以便所有依赖关系都在"依赖"它们的节点之前.但是,我正在寻找一个稍微不同的答案:

假设以下数据: a -> b和c -> d(a必须在之前b,c必须在之前d).
只有这两个限制,我们有多种候选方案:( ,,a b c d 等).但是,我正在寻找创建一种"分组"这些节点的方法,以便在处理组之后,下一组中的所有条目都会依赖它们的依赖关系.对于上面假设的数据,我会寻找像这样的分组.在每个组内,只要组1 在处理组2 中的任何一个之前完成,那么处理节点的顺序(在之前或之前等,反之亦然)并不重要.a c d bc a b d(a, c) (b, d)acbd(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.