algorithm - 红-黑生成树

Question

早上好

我遇到了以下与图形有关的问题，但无法提出正确的解决方案。我将不胜感激任何可能的帮助:

给你一张图，有些边是黑色的，有些是红色的。找到一棵具有一个限制的生成树:如果我们以某个节点为根，则从它到某个叶节点的每条路径都必须由交替的红-黑-红-黑边组成。也就是说，从根到叶的任何路径都必须包含连续的黑-黑边或红-红边。您可以保证存在这样的生成树。

谢谢。

Answer 1

这可能不是最有效的解决方案，而且编写起来会非常麻烦。

考虑一个图，其中每个节点都是具有给定根的树。如果 B 由具有一条额外边的 A 组成，则从一个节点 A 到另一个 B 有一条边。我们可以使用 BFS 遍历这个超图，并在找到生成树时停止。事实上，当没有这样一棵树时，我们也可以计算出这种情况。

假设给你一个由 (id, vertex, vertex, color) 定义的图，由 (1, e1, e2, b),(2, e1, e3, r),(3, e1, e4, b ) 根节点为 e4。

迭代的第一个元素是 (-1, e4, nil)(-1 是到达节点的边的 id，nil 代表从根到达的颜色)下一次迭代我们有 [(-1, e4, nil), (3, e1, b)]。在第三次迭代中，当我们到达带有蓝色的 e1 时，我们只能添加 [(-1, e4, nil), (3, e1, b), (2, e3, r)]

在这个例子中，只有一种可能的边加法。通常，我们需要在给定点跟踪所有可能的树。

请注意，树的超图是一个 DAG(每一边都添加一条边，经过 n 步后，您会到达一棵树，该树的边数比您开始时的边数更多)。