拓扑排序与分组
好的，所以在依赖于输入数据的拓扑排序中，通常存在多个正确的解决方案，图形可以被“处理”的顺序使得所有的依赖关系都出现在“依赖”它们的节点之前。 不过，我正在寻找一个稍微不同的答案：
假设以下数据： a -> b和c -> d （ a必须在b之前出现， c必须在d之前出现）。
只有这两个约束条件，我们有多个候选解决方案：（ abcd ， acdb ， cabd等）。 但是，我正在创建一个“分组”这些节点的方法，以便在处理完一个组之后，下一个组中的所有条目都会处理它们的依赖关系。 对于上述假设的数据，我会寻找像(a, c) (b, d)这样的分组。 在每个组内不要紧何种顺序节点被处理（ a前c或b之前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)因为在组2中有x意味着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;
}
标记具有级别值0的所有根节点。标记具有级别值parent + 1的所有子级。 如果正在重新访问节点，即已经分配了一个级别值，请检查之前分配的值是否低于新值。 如果是这样，请用更高的值更新并传播给后代。
现在，你有多少组，因为有独特的关卡标签0 ... K
我最近实现了这个算法。 我从你展示的方法开始，但没有扩展到2000万以上节点的图表。 我最终的解决方案是基于这里详述的方法。
您可以将其视为计算每个节点的高度，然后结果是在给定高度处的每个节点的一组。
考虑图表：
A - > X
B - > X
X - > Y
X - > Z
所以期望的输出是（A，B），（X），（Y，Z）
基本的方法是使用它找到没有任何东西的东西（在这个例子中是A，B）。 所有这些都在0高度。
现在从图中删除A和B，找到现在没有任何东西使用它（现在在这个例子中是X）。 所以X在高度1。
从图中移除X，找到现在没有任何东西使用它（现在在这个例子中是Y，Z）。 所以Y，Z在高度2。
您可以通过实现以下事实来进行优化：您不需要为所有内容存储双向边或实际从图中删除任何内容，只需知道指向节点的事件数量以及您知道的节点数量下一个高度。
因此，在开始的这个例子中：
当你访问一个节点时，减少它指向的每个节点的数量，如果这个数字变为零，就知道该节点在下一个高度。
链接地址: http://www.djcxy.com/p/48595.html