我试图计算依赖图的部分“拓扑排序”,这实际上是一个DAG(定向非循环图),它是精确的;以便并行执行没有冲突的依赖关系的任务.
我想出了这个简单的算法,因为我在Google上发现的并不那么有用(我只会发现自己并行运行的算法来计算正常的拓扑排序).
visit(node)
{
maxdist = 0;
foreach (e : in_edge(node))
{
maxdist = max(maxdist,1 + visit(source(e)))
}
distance[node] = maxdist;
return distance[node];
}
make_partial_ordering(node)
{
set all node distances to +infinite;
num_levels = visit(node,0);
return sort(nodes,by increasing distance) where distances < +infinite;
}
(请注意,这只是伪代码,肯定会有一些可能的小优化)
对于正确性,似乎很明显：对于叶子(= =没有进一步依赖的节点),最大距离到叶始终为0(正确,因为循环由于0边缘而被跳过).
对于连接到节点n1,…,nk的任何节点,最大距离到叶是1 max {distance [n1],..,distance [nk]}.
我写下了算法之后,我找到了这篇文章：http://msdn.microsoft.com/en-us/magazine/dd569760.aspx
但是老实说,他们为什么要做所有的列表复制等等,这似乎真的没有效率？
无论如何,我想知道我的算法是否正确,如果是这样的话,我可以读取一些关于它的东西.
更新：我在我的程序中实现了这个算法,似乎对我测试的一切都很有用.
代码如下：
typedef boost::graph_traits<my_graph> my_graph_traits;
typedef my_graph_traits::vertices_size_type vertices_size_type;
typedef my_graph_traits::vertex_descriptor vertex;
typedef my_graph_traits::edge_descriptor edge;
vertices_size_type find_partial_ordering(vertex v,std::map<vertices_size_type,std::set<vertex> >& distance_map)
{
vertices_size_type d = 0;
BOOST_FOREACH(edge e,in_edges(v))
{
d = std::max(d,1 + find_partial_ordering(source(e),distance_map));
}
distance_map[d].insert(v);
return d;
}
你的算法(C)是有效的,但它具有非常糟糕的最坏情况时间复杂度.它计算节点上的find_partial_ordering与该节点一样多的路径.在树的情况下,路径的数量为1,但是在一般的有向无环图中,路径的数量可以是指数的.
原文链接：https://www.f2er.com/javaschema/281330.html您可以通过memoizing的find_partial_ordering结果修复此问题,并在您已经计算了特定节点的值时返回而不进行递归.然而,这仍然给你一个堆栈破坏的递归解决方案.
这不符合你的需要吗？
编辑：啊,我明白,你想知道深度边界在哪里,这样你可以在给定的深度平行一切.您仍然可以使用维基百科的算法(因此避免递归).
首先,使用维基百科上的算法进行拓扑排序.现在通过以拓扑顺序访问节点来计算深度：
depths : array 1..n
for i in 1..n
depths[i] = 0
for j in children of i
depths[i] = max(depths[i],depths[j] + 1)
return depths
请注意,上面没有递归,只是一个简单的O(| V | | E |)算法.这与维基百科的算法具有相同的复杂性.
