2色グラフで交互の色を持つパスを見つける

色関数C：E→{赤、青}のグラフG =（V、E）が与えられている2色グラフで交互の色を持つパスを見つける

私はパスを見つけたいと思いますが、必ずしも単純ではありません（パスにはエッジやノードを複数回含めることができます）。これは色が交互に変わります。パス内のエッジの色は、パス内の前の色とは異なります。

これ以上制約はありませんが、これは線形時間で達成できると言われました。

おそらく関連：http://stackoverflow.com/questions/41934717/how-to-find-the-shortest-colored-path – Codor

はい、これは線形時間で実行できます。

パスは交互の色のエッジに従う必要があるため、各特定の頂点に到達するときには3つの状態があります。赤いエッジをたどっただけであるか、青いエッジをたどったか、非常に開始し、まだ何も横断していない。

各状態では、現在の頂点からトラバースできるエッジが異なります。

あなたは全ての可能な（頂点、状態）の組み合わせのための頂点と、新しい、より大きなグラフを作ることができる場合、あなたは無色で、それら頂点を接続することができ、があなたを介して到達できる頂点に各頂点からエッジを方向付け適切な色の元のエッジ。

次に、新しい有向グラフでDFSまたはBFSを実行して、パスを見つけることができます。

注：新しいグラフを作成することは、理解には役立ちますが、厳密には必要ありません.BFSまたはDFS検索アルゴリズムは、実際に構築することなく新しいグラフをトラバースするように簡単に変更できます。

2017-01-30 13:26:47

あなたは、あなたが新しいを作ることができれば」によって何を意味するのか明確にすることができ、すべての可能な（頂点、状態）の組み合わせの頂点を持つ大きなグラフ "？指数関数的に多くの組み合わせがありますが、そこにはありませんか？ – IVlad

@IVlad：より大きなグラフ、すなわち、各元の頂点「v」については、2つの新しい頂点「v_red」および「v_blue」と追加の「開始」頂点があります。元のグラフがN個の頂点を有する場合、新しい頂点は2N + 1個の頂点を有する。 –

もちろん、現在のノードと最後に訪問した色の2つのパラメータでdfsを定義することができます。そのため、各ノードで、そのノードの未訪問の頂点が最後に訪問した色そして続けなさい。

dfs(int node,int lastColor) 
    for(edge : graph[node]) 
     if(edge.color != lastColor) 
     dfs(edge.pos,edge.color)

2017-01-30 14:00:55

答えて