algorithm - 在 2 色图中找到颜色交替的路径

Question

我得到了一个图 G=(V,E) ，颜色函数为 C: E-->{red,blue} (例如，一条边可以用这两种颜色中的一种着色)

我想找到一条路径，不一定是简单的(意思是允许路径多次包含一条边或节点)，它的颜色是交替的——这意味着路径中每条边的颜色都不同于路径中以前的颜色。

没有更多的限制，但有人告诉我这可以在线性时间内实现。

Answer 1

是的，您可以在线性时间内完成。

由于路径需要沿着交替颜色的边，当它到达每个特定的顶点时，它可以处于 3 种状态:要么它刚刚穿过红色边缘，要么它刚刚穿过蓝色边缘，或者它是非常开始，还没有遍历任何东西。

在每个状态下，从当前顶点可以遍历的边是不同的。

如果您可以制作一个新的更大的图，每个可能的(顶点，状态)组合都有一个顶点，那么您可以将这些顶点与从每个顶点到顶点的无色有向边连接起来您可以通过适当颜色的原始边缘到达。

然后你可以在新的有向图中做一个DFS或BFS来找到路径。

注意:制作新图有助于理解，但并非绝对必要 - BFS 或 DFS 搜索算法很容易修改以遍历新图，而无需实际构建它。