在DAG中查找所有不可比较的节点
在DAG中查找所有不可比较的节点
提问于 2017-12-28 09:32:01
我感兴趣的是找出在有向无圈图(在拓扑顺序的意义上)中没有排序的顶点集。
也就是说，例如:非连通子图中的两个顶点，或在如下情况下的对(B，C)，(B，D)：
我想到的天真的可能性是枚举所有拓扑排序(在本例中是[ A, B, C, D ]和[ A, C, D, B ] &查找其顺序至少在两种类型中不同的所有对，但这在计算上是非常昂贵的。
对于我想要达到的目标，还有其他更快的可能性吗？我正在使用boost.graph。
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-12-28 13:33:08
基本上，您需要的是一对节点( (u,v) )，这样就没有从u到v的路径，也没有从v到u的路径。对于每个节点，您可以使用DFS为每个节点找到所有可以从该节点到达的节点。总复杂度O(n(n+m))。
现在，您所要做的就是检查每一对节点是否都不能被另一个节点访问。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/48011826
复制相关文章
相似问题
腾讯云开发者
