编写一个程序来检查，如果一个图是二部 [英] Writing a program to check if a graph is bipartite

问题描述

我需要写检查程序：如果一个图是二分。

I need to write a program that check if a graph is bipartite.

我已经经历了维基百科的文章阅读图着色和的二部图。这两篇文章暗示方法来测试bipartiteness像BFS搜索，但我不能写一个程序实现这些方法。

I have read through wikipedia articles about graph coloring and bipartite graph. These two article suggest methods to test bipartiteness like BFS search, but I cannot write a program implementing these methods.

推荐答案

你为什么不能？你的问题使得它很难有人甚至写你的计划，因为你甚至没有提到具体的语言......

Why can't you? Your question makes it hard for someone to even write the program for you since you don't even mention a specific language...

我们的想法是，开始通过将随机节点插入到先进先出的队列（也here ）。颜色是蓝色。然后重复此同时还存在留在队列中的节点：出列的元件。颜色邻国有不同的颜色比提取元素和插入（排队），每个邻居到FIFO队列。例如，如果你出列（提取物）的元素（节点）红色，颜色邻国蓝色。如果您抽取一个蓝色节点，色彩邻国红色。如果没有着色冲突，该图是二部。如果你最终着色两种不同颜色的点，比这不是二分。

The idea is to start by placing a random node into a FIFO queue (also here). Color it blue. Then repeat this while there are nodes still left in the queue: dequeue an element. Color its neighbors with a different color than the extracted element and insert (enqueue) each neighbour into the FIFO queue. For example, if you dequeue (extract) an element (node) colored red, color its neighbours blue. If you extract a blue node, color its neighbours red. If there are no coloring conflicts, the graph is bipartite. If you end up coloring a node with two different colors, than it's not bipartite.

就像@Moron说，我描述了将只对连通图。但是，您可以使用相同的算法，每个连接的组件，使之成为任何图形工作。

Like @Moron said, what I described will only work for connected graphs. However, you can apply the same algorithm on each connected component to make it work for any graph.

这篇关于编写一个程序来检查，如果一个图是二部的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！