首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >编写检查图是否为二部图的程序

问编写检查图是否为二部图的程序
EN

Stack Overflow用户
提问于 2010-05-23 01:23:06
回答 3查看 16.8K关注 0票数 6

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

我通读了维基百科上关于graph coloring和bipartite graph的文章。这两篇文章推荐了一些测试二部性的方法,比如BFS搜索,但我不能编写实现这些方法的程序。

EN

回答 3

Stack Overflow用户

发布于 2010-05-23 01:35:04

为什么你不能呢?你的问题让人很难为你写程序,因为你甚至没有提到一种特定的语言……

其思想是首先将一个随机节点放入FIFO队列(也称为here)。把它涂成蓝色。然后,在队列中仍有节点时重复此操作:将一个元素出队。用与提取的元素不同的颜色对其邻居进行着色,并将每个邻居插入(入队) FIFO队列。例如,如果您将红色的元素(节点)出队(提取),则将其相邻元素显示为蓝色。如果提取蓝色节点,请将其相邻节点颜色设置为红色。如果没有着色冲突,则该图是二部图。如果你最终用两种不同的颜色给一个节点上色,那么它就不是二分的。

就像@Moron所说的,我所描述的只适用于连接的图。但是,您可以对每个连接的组件应用相同的算法,使其适用于任何图形。

票数 12
EN

Stack Overflow用户

发布于 2011-05-26 17:06:44

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

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

图是二部图当且仅当它不包含奇圈。

票数 1
EN

Stack Overflow用户

发布于 2013-09-20 17:33:52

具体实现如下(C++版本):

代码语言:javascript
复制
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;
}
票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/2889036

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档