これはインタビューで尋ねられる質問です。無向グラフが赤または黒の2色にならないようにする方法を決定する方法
インタビュアーは、私の解決策が正しいことを主張するために私を望んでいたし、それは私が単に凍結
O(|V| + |E|)で実行されます。
これは簡単ではない理由のように具体的に、以下の点を考慮しsubquestions：
どのような状況下では、答えは私たちがすることはできません、ないだろう。
推奨されるBFSまたはDFSは、なぜですか？
無向グラフを持たないのは難しいですか？私は前後に行くことができるので、偶数ノードのサイクルがあれば、本当にそうすることはできないようです。
このプロパティを持っているグラフがbipartite graphと呼ばれ、あなたはグラフは二部であるかどうかをテストするために使用できる素敵なアルゴリズムがいくつかあります。
二部グラフの重要な定理は、グラフが奇数長のサイクルを含まない場合にのみ、二部グラフであることです。この定理は本当に役に立ちます。なぜなら、あなたが見たノードを見直してしまうと、それがあなたにとって重要かどうかを判断できるからです。それが奇数長のサイクルを閉じると、グラフは二部構成ではなく、完了しているということが分かります。それ以外の場合、偶数長のサイクルを閉じると、それを無視して移動することができます。
これに基づいて、グラフのDFSかBFSのどちらかを少しずつ変更することで、グラフが二者であるかどうかを確認できます。まず、検索中の深さを追跡します。すべてのノードを偶数レベルに、奇数レベルのノードをすべて黒にマークします。検索を行う際に、ノードに色を割り当て、その隣人のいずれかにすでに同じ色が与えられていることに気がついたら、奇数長のサイクルがあり、色付けがないことを報告できます（理由は分かりますか？ ）。これが起こらないなら、あなたは同じ色の2つのadjacenfノードを持たない赤色または黒色の各ノードに色付けしました。
ノードごとにBFSまたはDFSに一定量の作業が追加されるため、ランタイムはグラフのサイズが直線的になります。あなたはどんな検索アルゴリズムを選んでも構いません。選択のトレードオフはメモリ使用量などの他の要因に依存します。
2値グラフは、有名で有用なグラフクラスであり、今後読む価値があります。彼らはクールなプロパティと素晴らしいアプリケーションのトンを持っています！