algorithm - 编写一个程序来检查一个图是否是二分图

Question

我需要编写一个程序来检查一个图是否是二分的。

我已阅读有关图形着色和二分图的维基百科文章。这两篇文章提出了测试二分性的方法，例如 BFS 搜索，但我无法编写实现这些方法的程序。

Answer 1

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...

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.

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.

Answer 2

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm

请阅读此网页，使用广度优先搜索检查何时发现某个节点已被访问，检查当前循环是奇数还是偶数。

一个图是二分的当且仅当它不包含奇数循环。

Answer 3

详细实现如下（C++版本）：

struct NODE
{
    int color;
    vector<int> neigh_list;
};

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index);

bool checkBigraph(NODE * graph, int numNodes)
{
    int start = 0;

    do 
    {
        queue<int> Myqueue;
        Myqueue.push(start);
        graph[start].color = 0;

        while(!Myqueue.empty())
        {
            int gid = Myqueue.front();
            for(int i=0; i<graph[gid].neigh_list.size(); i++)
            {
                int neighid = graph[gid].neigh_list[i];
                if(graph[neighid].color == -1)
                {
                    graph[neighid].color = (graph[gid].color+1)%2; // assign to another group
                    Myqueue.push(neighid);
                }
                else
                {
                    if(graph[neighid].color == graph[gid].color) // touble pair in the same group
                        return false;
                }
            }
            Myqueue.pop();
        }
    } while (!checkAllNodesVisited(graph, numNodes, start)); // make sure all nodes visited 
                                            // to be able to handle several separated graphs, IMPORTANT!!!

    return true;
}

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index)
{
    for (int i=0; i<numNodes; i++)
    {
        if (graph[i].color == -1)
        {
            index = i;
            return false;
        }
    }

    return true;
}