1

我想知道是否有人可以提供一些关于如何在对图执行深度优先搜索时检查钻石依赖关系的指示......我有以下图表A -> B, A -> F, B -> C, B-> E, C -> D, E -> D。

我正在尝试构建代表指定图形的容器层次结构，但是当我达到菱形依赖项时，我不确定该怎么做。例如，在我的图中，CandE都是 的子容器B，当我解决 时D，我需要引用Cand E。我可以检测到钻石依赖关系并将其组合C到E一个容器中吗？

4

6 回答 6

3

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

所有节点都以白色开始。

正在处理的节点是灰色的。

处理完节点后，将其着色为黑色。

一旦遇到节点，您就将它涂成灰色。

处理完其子节点后，您将节点着色为黑色。

如果您遇到黑色节点，那么您就遇到了菱形依赖项。

于 2009-03-10T04:06:00.423 回答
2

Rohan，您可以使用深度优先搜索通过查找交叉或前向边缘来检测“钻石深度”。如果您在 boost-graph-library 主页上查看深度优先搜索的伪代码实现。

... else if (color[v] = BLACK) (u,v) 是十字边或前边...

于 2009-03-13T11:31:41.953 回答
1

Rohan，因为我有时会教算法和数据结构，所以我可能会有偏见，但我怀疑你需要看一本图算法书。有很多不同的方法来做这似乎暗示的事情，但并不完全清楚你真正想要做什么。是的，在这种情况下，您有两个节点，其传入边和传出边到/来自相同节点（这里，（B，E），（B，C）（C，D），（E，D））将两个节点 C 和 E 组合成一个“C，E”节点是合法的。将 D 分解为 D 1和 D 2也是合法的，使其成为树而不是 DAG。

也就是说，根据问题这样做是合法的。

于 2009-03-10T04:29:16.077 回答
0

我不知道您如何定义图形的节点。让我们说一种表示节点的方法如下 -

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

这种实现的问题是——我们不知道一个节点的父节点。如果我们有办法知道谁是一个节点的父节点，我们就可以找出菱形依赖关系。

例如，在你的情况下，我们应该从树的底部开始，我们可以看到 D 有两个 Parenet，它们来自 B。所以我会说建立你的图，它不仅照顾孩子，而且照顾父母. 然后在一次通过中，找出哪些节点有多个父节点（如 D 有），以及这些父节点（C 和 E）是否具有相同的父节点（B）。

于 2009-03-10T04:05:18.553 回答
0

我不太确定您要做什么，但最迟当您的图表包含循环时，您确实需要检测在搜索过程中重复找到的节点。通常这是通过在处理节点时以某种方式标记节点来完成的，这样您可以稍后查看您之前是否已经访问过它们。这在您的情况下效果如何取决于您的实现以及这些节点的外观......

于 2009-03-10T04:12:13.263 回答
-1

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

我猜你会在这里看到一些非常合理的建议，然后稍后它们会被确定为部分甚至大部分是错误的。小心地走。

于 2009-03-10T04:09:32.210 回答