• 热门专题

二分图判断(图的搜索)

作者:  发布日期:2015-03-04 20:44:01
  • 二分图,又叫做双分图 二部图 偶图指顶点可以分成两个不相交的集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("no\n");
                    return;
                }
            }
        }
        printf("yes\n");
    }

延伸阅读:

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规