我需要写一个程序来检查一个图是否是二部图。
我通读了维基百科上关于graph coloring和bipartite graph的文章。这两篇文章推荐了一些测试二部性的方法,比如BFS搜索,但我不能编写实现这些方法的程序。
发布于 2010-05-23 01:35:04
为什么你不能呢?你的问题让人很难为你写程序,因为你甚至没有提到一种特定的语言……
其思想是首先将一个随机节点放入FIFO队列(也称为here)。把它涂成蓝色。然后,在队列中仍有节点时重复此操作:将一个元素出队。用与提取的元素不同的颜色对其邻居进行着色,并将每个邻居插入(入队) FIFO队列。例如,如果您将红色的元素(节点)出队(提取),则将其相邻元素显示为蓝色。如果提取蓝色节点,请将其相邻节点颜色设置为红色。如果没有着色冲突,则该图是二部图。如果你最终用两种不同的颜色给一个节点上色,那么它就不是二分的。
就像@Moron所说的,我所描述的只适用于连接的图。但是,您可以对每个连接的组件应用相同的算法,使其适用于任何图形。
发布于 2011-05-26 17:06:44
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm
请阅读此网页,使用广度优先搜索来检查当您发现某个节点已被访问时,检查当前周期是奇数还是偶数。
图是二部图当且仅当它不包含奇圈。
发布于 2013-09-20 17:33:52
具体实现如下(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;
}https://stackoverflow.com/questions/2889036
复制相似问题