深度优先搜索,如何检测钻石依赖关系?

我发现最容易想到使用颜色的图形算法。

所有节点都以白色开头。

正在处理的节点为灰色。

处理完节点后,将其涂成黑色。

处理完节点的子节点后,可以将其着色为黑色。

如果您遇到一个黑色节点,那么您遇到了菱形依赖项。

Rohan您可以使用深度优先搜索,通过查找交叉或前边缘来检测“钻石DEP”。如果您看一下 depth-first-search 在boost图形库主页上。

... else if(颜色[v]=黑色) (u,v)为十字或前缘 ...

我不知道您是如何定义图的节点的。假设表示节点的一种方法如下所示-

public interface Node {
            int getValue();
            List<Node> getChildren();
        }

例如,在你的例子中,我们应该从树的底部开始,我们可以看到D有两个parenet,它们来自B。 所以我想说,建立一个图表,它不仅照顾孩子,也照顾父母。然后在一个过程中,找出哪些节点具有多个父节点(如D),以及这些Parenet(C和E)是否具有相同的父节点(B)。

我不确定你到底想做什么,但最晚当你的图表包含循环时,你真的需要检测你在搜索过程中反复找到的节点。通常,这是通过在处理节点时以某种方式标记节点来完成的,以便以后可以查看之前是否已经访问过它们。这在您的案例中的效果取决于您的实现以及这些节点的外观。。。

做 . 是的,在这种情况下,如果有两个节点的传入边和传出边与相同节点(此处,(B,E),(B,C)(C,D),(E,D))相连,则将两个节点C和E合并为“C,E”节点是合法的。把D分解成D也是合法的 _2. 把它变成一棵树而不是一只狗。

也就是说,这样做是合法的 依靠 关于这个问题。

图论是一个非常庞大而复杂的数学领域。这是一件很危险的事情:)即使是图论的基本应用,也很难找到简单的解释。很有可能,任何你可能遇到的图形都被打死了,并且有比你解决问题时想象的多5倍的陷阱和陷阱。

我猜你会在这里看到一些非常合理的建议,然后过一会儿,他们会被认为是部分错误,甚至大部分错误。小心一点。