二分图判断 (图的搜索)

50 阅读 0 评论 33 点赞

我是靠谱客的博主热情老虎，最近开发中收集的这篇文章主要介绍二分图判断 (图的搜索)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二分图，又叫做双分图二部图偶图，指顶点可以分成两个不相交的集U和V，使得在同一个集内的顶点不相邻(没有共同边)的图。

无向图G为二分图的充要条件是，G至少有两个顶点，且其所有回路的长度均为偶数。

给定一个具有N个顶点的图，判断其是不是二分图(如着色问题，最小着色数为2的图就是二分图)，可以用DFS处理。选择任意一个顶点出发，依次确定相邻顶点的颜色，就可以判断是否可以被2种颜色染色了。

代码如下

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_V = 1000;
vector<int> G[MAX_V];//假设边已经装在了邻接表里
int V;
int color[MAX_V];//记录颜色
bool dfs(int node,int clr)
{
    color[node] = clr;//涂色
    for(int i = 0 ; i < G[node].size() ; i ++) {
        if(color[G[node][i]] == clr) return false;//如果有一样的颜色就失败了
        if(color[G[v][i]] == 0 && !dfs(G[v][i],-c)) return false;//递归
    }
    return true;
}
void solve()
{
    for(int i = 0 ; i < V ; i ++) {//循环主要是为了防止非连通图
        if(color[i] == 0) {
            if(!dfs(i,1)) {
                printf("non");
                return;
            }
        }
    }
    printf("yesn");
}