好的,因此在根据输入数据进行拓扑排序时,通常存在多个正确的解决方案,可以根据这些正确的解决方案对图进行“处理”,以便所有依赖项都位于“依赖”它们的节点之前。但是,我正在寻找稍微不同的答案:
假设以下数据: 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
a
b
c
d
a b c d
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 -> 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中的某个节点。
(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; }
用级别值0标记所有根节点。用级别值parent + 1标记所有子节点。如果正在重新访问节点,即已经分配了一个级别值,请检查先前分配的值是否小于新的值。如果是这样,请使用较高的值对其进行更新,并将其传播给后代。
现在,您拥有与唯一级别标签0 … K一样多的组