编写一个程序来检查图是否为二分图。

Question

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

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

- John Graveston

Answer 1

为什么你不能这样做？由于你甚至没有提到特定的语言，这让别人很难为你编写程序......

这个想法是从将一个随机节点放入FIFO队列（也在这里）开始的。将其涂成蓝色。然后在队列中仍然有节点的情况下重复此过程：出队一个元素。用与提取元素不同的颜色对其邻居进行染色，并将每个邻居插入（入队）到FIFO队列中。例如，如果你出队（提取）一个红色节点（元素），则用蓝色给它的邻居上色。如果你提取了一个蓝色节点，则用红色来给它的邻居上色。如果没有颜色冲突，则图形是二分图。如果你最终将一个节点染成两种不同的颜色，则它不是二分图。

正如@Moron所说，我所描述的只适用于连通图。但是，你可以将相同的算法应用于每个连通组件，从而使其适用于任何图形。

- IVlad

---

不错！如果有人不明白为什么着色冲突意味着它不是二分图，那我建议阅读@Haoran Wang的答案。 - Narek

Answer 2

详细的实现如下（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;
}

- herohuyongtao

Answer 3

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

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

当且仅当图不包含奇数循环时，它才是二分图。

- Haoran Wang