当您有一组项的依赖关系图时，您可以进行标准的主题排序来检查该图是否包含循环。如果有一个循环，那么就有一个依赖关系，如果不违反另一个，就无法满足。
但是冲突信息呢？我指的是一种结构：
V-一组项目E-一组依赖边：E\subet V\times VC-一组冲突边：C\subet V\times V
检查依赖关系图是否包含无法满足的冲突信息的标准算法是什么？
例如：
V=｛a，b，c｝E={(a->b(，(b->c(}C={(a->C(}
这个例子显示了一个不健全的依赖图，因为c依赖于a是没有意义的，同时给定a的c的存在被指定为冲突。
这种模型的一个真实例子是包管理器，其中包描述可能包括依赖和冲突规范。另一个例子是基于依赖关系的运行服务，其中只有在没有冲突作业正在运行的情况下才能启动作业。
我不知道标准算法，但它有效：
- 像往常一样找到
(V,E)的拓扑排序(如果发现循环依赖性( - 以DFS/BFS方式，标记每个依赖项跟踪/组件唯一(以下解释(
- 遍历
C和检查是否不存在对CCD_ 7使得CCD_。如果有这样一对===>返回不稳定，否则===>返回稳定
运行时间O(|E|+|V|+|C|):
由于拓扑排序和DFS在(V,E)中是线性的，第三部分在C中是线性。
第2阶段的说明：
我们从依赖图的顶部开始(或者如果你喜欢的话，从拓扑排序的开始(，选择第一个节点和第一个标签，比如1。我们以DFS(或BFS(方式遍历图中的每条边；只要我们仍然连接，我们就继续用相同的标签标记节点。一旦连接"用完"，我们就会增加标签并在DFS/BFS中继续。
即，从第一个节点可到达的一切都被标记为1。一旦我们耗尽了该节点(DFS或BFS算法中的外循环(的可达性，我们就增加标签并选择下一个未搜索的节点。
正确性证明：
我们做了一个关键的观察——图是不稳定的，当在CCD_ 15中存在一些对CCD_ 14使得CCD_。
首先，我不是指C中的元素，因为存在对称性。如果C中有(u -> v)，那就意味着，用你的话来说，给定u，v就不可能存在。因此，它们不可能同时存在，这意味着u既不可能依赖于v(因为u要存在，v必须存在，这是不可能的(，也不可能相反。
有了这样的理解，我们就可以证明上述观察结果：
我们注意到，如果u依赖于v，或者相反，则为label(u) = label(v)。这是构造的一个简单结果，其中可达性(以及依赖性(定义了标签。所以，如果我们假设我们是这样一对，那么图是不稳定的(正如上面一段所解释的(。
观察的另一个方向(不稳定===>对(也很容易看到。如果我们假设图是不稳定的，那么就有一些u不可能存在。这个u要么依赖于冲突的东西，要么某个其他节点依赖于它，并且该对是冲突的。无论哪种方式，我们在C中发现了一对具有相同标签的(u,v)。