どのように私は色によって二部グラフを分割するのですか？

StackOverflow https://stackoverflow.com/questions/1655162

質問

例えば、私はグラフG =（V、E）を有すると仮定する。ここで、

V = {A、B、C、D}
E = {（A、B）、（A、D）、（C、D）}

このグラフは二部であり、したがって、2点の互いに素な集合{A、C}と{B、D}に分割することができます。私の最初の推測では、私は単純にグラフを歩くと、各頂点に交互に色を割り当てることができるということです。これはそうである、またはそれは、これよりも単純/複雑ですか？このため、任意の既知のアルゴリズムがありますか？

役に立ちましたか？

解決

は最初の推測が正しい - グラフおよび代替トラバース

このアルゴリズムは簡単でなければなりません。私は、各色のための1つを訪問したノードの2つのキューを維持するだろう。ポップは、その色をマークし、反対色のためにキューに任意の非訪れた隣接ノードをプッシュし、交互のキューをオフノード。訪問したノードの数が+両方のキューの長さは、グラフ内のノードの数=ときに終了します。

他のヒント

それはそれはあなたのグラフは二部ではないことを意味succededしない場合です。

、グラフおよび代替をトラバース

あなたはグラフがbiparteであることが確実な場合は、それが保持しているとして

は、その後、あなただけの、色は各頂点を通過するためにそれらを交互に割り当てることができます：

  

のグラフは、2-着色ある場合にのみ二部である。

ウィキペディアから（ http://en.wikipedia.org/wiki/Bipartite_graphする）

二部グラフが接続されている場合は、

、その2分割は、任意に選択された頂点vからの距離のパリティによって定義することができる。一つのサブセットは、Vにも距離で頂点からなり、他のサブセットは奇数の距離で頂点から成りVへ。

このように、一方が効率グラフは別々にグラフの各連結成分の中に、2つのサブセットにU及びVの頂点を割り当てるには、このパリティ技術を使用して二連であるかどうかをテストし、それがエンドポイントを持っていることを確認するために、各エッジを検査することができます異なるサブセットに割り当てられます。

私は私のグラフ描画ツールの中でそれを実装するには、JavaScriptで私のコードを見ることができます。

私はちょうど再帰的権利partityとしての隣人をマークし、その後、左partityとして最初の頂点をマークし、再帰的に左partityとして隣人をマーク...あなたが正しくマークされたノードを見つけた場合は、このブランチの再帰を停止します。あなたはuncorrectlyマークされたノードを見つけた場合、グラフは二部ではありません。

多分それは単純に行うことができますが、最後の数ヶ月間、私はいくつかのハードプロローグを持っていた - Haskellのコーディング日、多分それは私の脳に影響を与えていたし、今私は

:-Dすべてに再帰を見ます

念のために誰でも好奇心だ、ここで私が思い付いたコードです 

def dfs(root, colorings):
    to_visit1 = deque()
    to_visit2 = deque()
    to_visit1.append(root)
    while len(to_visit1) != 0 or len(to_visit2) != 0:
        dfs_color(to_visit1, to_visit2, True, colorings)
        dfs_color(to_visit2, to_visit1, False, colorings)

def dfs_color(queue, opposite_queue, color, colorings):
    while len(queue) != 0:
    v = queue.pop()
    if v in adjacency_list:
        colorings[v] = color
        neighbors = adjacency_list[v]
        del adjacency_list[v]
        for neighbor in neighbors:
        opposite_queue.append(neighbor)

確かに、これは私の最高のコードではありません。私は再帰を使用する場合、それは簡単にだけTrueを言うために作られたので、私は色としてFalse / not colorを使用しています。もちろん、私は大きなグラフに私のスタックを吹いたので、それを変更しなければなりませんでした。また、信用どこ原因を与えるために、このコードは、 DFS 。

が指摘されているように、私はこれは単なる偽装BFSかもしれないと思うが。

所属していません StackOverflow
scroll top