在双色图中查找具有交替颜色的路径 [英] Find a path with alternating colors in a 2-color graph

问题描述

我给出了一个图G =（V，E），带有颜色函数C：E - > {红色，蓝色}（例如，边缘可以用这两种颜色之一着色）

我想找到一条路径，不一定是简单的（意思是允许路径不止包含一个边或节点），这是交替的颜色 - 这意味着每条边路径中的颜色与路径中的前一种颜色不同。

没有任何约束，但我被告知可以在线性时间内实现。

解决方案

是的，您可以在线性时间内完成这项工作。

由于路径需要跟随交替颜色的边缘，因此当它到达每个特定顶点时，它可以处于3种状态：它既可以穿过红色边缘，也可以穿过蓝色边缘，也可以是开始并且还没有遍历任何东西。

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

如果您可以创建一个新的更大的图形，并为每个可能的（顶点，状态）组合创建一个顶点，那么您可以将这些顶点与无色指向从每个顶点到可以通过适当颜色的原始边缘到达的顶点的边。

然后，您可以在新的有向图中执行DFS或BFS，以便找到路径。注意：创建新图对理解有用，但不是绝对必要的 - BFS或DFS搜索算法很容易修改而无需实际遍历新图必须建立它。

I'm given a graph G=(V,E) , with a color function C: E-->{red,blue} (e.g an edge can be colored in one of those 2 colors)

I would like to find a path, not necessarily simple (meaning the path is allowed to include an edge or node more than once), which is alternating in colors - that means that every edge's color in the path is different than the previous color in the path.

There aren't any more constraints, but I was told that this could be achieved in linear time.

解决方案

Yes, you can do this in linear time.

Since the path needs to follow edges of alternating colors, there are 3 states that it can be in when it reaches each particular vertex: either it just traversed a red edge, or it just traversed a blue edge, or it is the very start and hasn't traversed anything yet.

In each state, the edges that can be traversed from the current vertex are different.

If you can make a new, larger graph, with a vertex for every possible (vertex,state) combination, then you can connect those vertexes with uncolored, directed edges from each vertex to the vertices you can reach through an original edge of the appropriate color.

Then you can just do a DFS or BFS in the new directed graph to find the path.

NOTE: Making a new graph is useful for understanding, but not strictly necessary - BFS or DFS search algorithms are easily modified to traverse the new graph without actually having to build it.

这篇关于在双色图中查找具有交替颜色的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！