从给定边缘构建DAG

让我们绘制N个没有边缘的垂直图。从给定边缘构建DAG

让我们边的名单：

x1 y1 
x2 y2 
x3 y3 
. 
. 
. 
xk yk

我们必须从1处理所有边缘到k。我们不得不说，如果第x个边缘正在循环图。如果不是，请将其添加到图表中。

如何有效地做到这一点？我的意思是不要检查DFS是否第x个边缘每次都制作循环图。

有什么更快的？这是波兰SPOJ问题

https://pl.spoj.pl/problems/XIWTPZF/

感谢您的任何帮助。 Chris

来源

2011-05-31 Spinach

创建一个边缘对象。在边缘对象中你有两个标志。跟踪标志和添加的标志。从要检查的边缘列表中构建您的对象模型。添加所有边，并连接使用边对象中的指针进行链接的边。向模型添加边时，链接到新添加的边以及以新添加的边的起点为终点的所有先前添加的边。

当您测试边缘时，首先将其设置为临时添加标志。然后递归跟踪，随时设置跟踪标志。如果碰撞已经有迹象的边缘，则返回false，并在出路中清除跟踪标志。重要的部分是，你不追踪没有设置添加标志的边缘。

如果不发生碰撞，则在没有触及跟踪标志的情况下，对于终止的每条边都返回true。

如果返回true，则移动到您的有序列表中的下一条边。如果返回false，请清除添加的标志。

在跟踪结束时，检查添加的标志。

在这个位置（所以不要纠正我的C++语法）严重的伪代码：http://pastebin.com/dT2bFmqp

来源

2011-05-31 21:56:33

这通过去除实际添加的低效和删除对象模型的边缘可以节省一些时间，这就需要去耦和删除对象。此外，您还可以获得订单检查清单以及对象模型，因此最后只需循环检查订单检查清单即可。此时，您可以移除未添加的项目，并且您有最终的列表。如果您在检测阶段使用接口并在使用阶段使用单独的接口，那么您不必为使用阶段保留较大的接口。 – 2011-05-31 22:09:51

一般来说，我不确定这样做的有效方法。我认为你可以通过将你的图分成不相交的集合来获得一些效率，但是这取决于你的具体输入图的布局，这将取决于你获得多少收益。另外，你可以采取其他一些快捷方式（比如检查你连接的边是否有边），但是这又取决于你的特定图的属性是否对你有帮助。

这是我想出的算法可能是效率不高，只要你愿意：

# No cycles on an empty list 
for edge in edgeList: 
    graph.addEdge(edge) 
    cycles = detectCycle(graph) 
    if cycles 
     graph.removeEdge(edge)

来源

2011-05-31 21:42:59

从给定边缘构建DAG

回答

相关问题