二分图判定 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 给定一个具有n个顶点的图. 要给图上每个顶点染色, 并且要使相邻的顶点颜色不同. 

是否能最多用2种颜色进行染色. 没有重边和闭环.

即二分图问题.

使用深度优先搜索(dfs), 把顶点染成c, 然后相邻边染成-c. 

如果相邻边被染色过, 且相同, 则图不是二分图; 如果所有边都被染色, 并且互不相同, 则是二分图.

进行多次搜索, 避免非连通图.

代码:

/*
 * CppPrimer.cpp
 *
 *  Created on: 2014.7.27
 *      Author: Caroline
 */

/*eclipse cdt*/

#include <stdio.h>

#include <vector>

using namespace std;

class Program {
	static const int MAX_V = 100;

	/*vector<int> G[MAX_V] = {{1,3}, {0,2}, {1,3}, {0,2}};
	int V = 4;*/

	vector<int> G[MAX_V] = {{1,2}, {0,2}, {0,1}};
	int V = 3;

	int color[MAX_V] = {0};

	bool dfs(int v, int c) {
		color[v] = c;
		for (size_t i=0; i<G[v].size(); ++i) {
			if (color[G[v][i]] == c) return false;
			if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) return false;
		}
		return true;
	}
public:

	void solve() {
		for (int i=0; i<V; i++) {
			if (color[i] == 0) {
				if(!dfs(i,1)) {
					printf("result = No\n");
					return;
				}
			}
		}
		printf("result = Yes\n");
	}
};

int main (void)
{
	Program iP;
	iP.solve();

	return 0;

}

输出:

result = No