写在前面

从简单实用的角度来看，二分图结构在某些场景可以更高效地存储数据。不同于哈希表的一对一的映射；二分图可以做到一到多的映射，想象二分图中一个节点，与它相连的节点与它的颜色都不一样且均为另一种颜色。

  • 二分说白了就是遍历一遍图，一边遍历一边染色，看看能不能用两种颜色给所有节点染色，且相邻节点的颜色都不相同。
  • BFS和DFS都可以，为了避免为环，需要visited数组辅助
  • 整体思路：遍历每个节点的相邻节点（类比遍历多叉树的过程，只不过相邻节点的信息是由邻接表提供的）的过程中，如果之前遍历过，判断是否符合二分条件，反之，给它染上合适的颜色。

用到的基本变量及注意点

  • 肯定要记录每个节点的颜色: vector<int> color
  • 需要一个辅助数组，避免走回头路：vector<int> visited
  • 邻接表：遍历下去，自然需要知道每个节点的邻接点，如果需要建表，一定要注意编号的范围
  • 如果使用BFS，自然需要用到队列，DFS则是利用系统的栈来维护数据。
  • 为了避免图不是连通的，因此无论DFS还是BFS，都需要对所有的节点作为起始点遍历（不会增加复杂度，因为有visited数组剪枝）

DFS实现

785. 判断二分图，注意递归的框架：base case的位置以及visited的使用。

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        bool cancolored=true;
        vector<bool> visited(graph.size(),false);
        vector<bool> color(graph.size());
        // 避免不连通，依次遍历，利用visited剪枝
        for(int i=0;i<graph.size();i++){
            if(visited[i]) continue;
            traverse(graph,visited,i,color,cancolored);
        }
        return cancolored;
    }
    void traverse(vector<vector<int>>&graph,vector<bool>&visited,int s,vector<bool>&color,bool& cancolored){
        // base case，是否可以染色，是否访问过
        if(cancolored==false)
            return;
        if(visited[s]){
            return;
        }
        // 记录当前节点
        visited[s]=true;
        for(auto t: graph[s]){
            // 访问过相邻节点判断颜色
            if(visited[t]){
                if(color[s]==color[t]){
                    cancolored=false;
                    return;
                }
            }
            // 没访问过，染色相反的，并遍历其相邻
            else{
                color[t]=!color[s];
                traverse(graph,visited,t,color,cancolored);
            }  
        }
        return;
    }
};

BFS 实现

借助队列实现，避免不连通，依次遍历，利用visited剪枝

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        // visited数组
        vector<bool> visited(graph.size());
        // 染色数组
        vector<int> color(graph.size());
        // 合适的数据结构：队列
        queue<int>Q;
        // 避免非连通的图
        for(int i=0;i<graph.size();i++){
            // 遍历过则返回
            if(visited[i]) continue;
            // 否则放入队列并设置为true
            Q.push(i);
            visited[i]=true;
            // Q不为空
            while(!Q.empty()){
                // 取出队首并pop
                int cur=Q.front();
                Q.pop();
                // 依次遍历cur的相邻节点
                for(auto s:graph[cur]){
                    // 判断是否访问过
                    if(visited[s]){
                        if(color[s]==color[cur]){
                            return false;
                        }
                    }
                    else{
                        visited[s]=true;
                        color[s]=!color[cur];
                        Q.push(s);
                    }
                }
            }
        }
        return true;
    }

};

$\cdots$ end $\cdots$