判断是否为二分图的两种算法 dfs/bfs

判断是否为二分图的两种算法 dfs/bfs

判断一个无向图是不是二分图，使用染色法.对每个顶点的相邻顶点染与顶点不同的颜色。如果染过色且与顶点颜色相同，则不是二分图。

/*
author: 熊谦智

判断该图是否为二分图 

1:判断无向图是否有环: 如果图g有环，用dfs遍历图g，会访问到已经访问过的顶点。
2:判断无向图是否为二分图：利用bfs遍历图给图上色（2种颜色），然后判断上色顶点间是否冲突。若冲突，则为非二分图。

link:
https://blog.csdn.net/wuhuajunbao/article/details/41775341
https://blog.csdn.net/haiboself/article/details/51892375 
*/
#include<iostream>
#include<vector>
#include<queue> 
#include<cstring>
using namespace std;
const int N = 1005;
int color[N];
bool bfs(int v,vector<vector<int> >& edge) ;
bool dfs(int v,vector<vector<int> >& edge) ;
int main() {
  int n, m;
  while (cin >> n >> m) {
    int from, to;
    vector<vector<int> > edge(n+1,vector<int>());
    for (int i = 0; i < m; i++) {
      cin >> from >> to;
      edge[from].push_back(to);
      edge[to].push_back(from);
    }
    memset(color,0,sizeof(color));
    bool flag = true;
//    for (int i = 1; i <= n; i++) { bfs循环 
//      if (color[i] == 0 && !bfs(i,edge)) {
//        cout << i << endl;
//        flag = false; //不是二分图 
//        break;
//      }
//    }

    for (int i = 1; i <= n; i++) { // dfs循环 
      if (color[i] == 0) {
        color[i] = 1;
        if (!dfs(i,edge)) {
          cout << i << endl;
          flag = false; //不是二分图 
          break;
        }
      }
    }
    if (flag) {
      cout << "是二分图" << endl;
    } else {
      cout << "不是二分图" << endl;
    }
  }
  
  
} 
bool dfs(int v,vector<vector<int> >& edge) {
  for (int i = 0; i < edge[v].size(); i++) {
    int temp = edge[v][i];
    if(color[temp] == 0) {
      color[temp] = -color[v];
      //  不能直接return  dfs(temp,edge); 不然 temp后面的边就不会被检测了 
      //但是下面这个语句可以  当 dfs(temp,edge) 返回true 时 就继续执行temp后面的节点 一旦出错就返回false 
      if (!dfs(temp,edge)) return false;
    }
    if (color[temp] == color[v]) {
      return false;
    }
  }
  return true;
}
bool bfs(int v,vector<vector<int> >& edge) {
  queue<int> q;
  q.push(v);
  color[v] = 1;
  while (!q.empty()) {
    int temp = q.front();
    q.pop();
    for (int i = 0; i < edge[temp].size(); i++) {
      int flag = edge[temp][i];
//      cout << "flag = " << flag << endl; 
      if (color[flag] == 0) {
        color[flag] = -color[temp];
        q.push(flag);
      }
      if (color[flag] == color[temp]) {
//        cout << "flag = " << flag << " temp = " << temp << endl;
        return false;
      }
    }
  }
  return true;
} 

/*
3 3
1 2 
1 3 
2 3

4 5
1 2
1 3
1 4
2 3
3 4
*/

二分图匹配算法 一般有匈牙利算法

二分图匹配总结：https://www.cnblogs.com/newera/p/8420756.html