leetcode判断二分图

判断二分图

图的问题肯定要用到深度优先遍历或者广度优先遍历，但又不是单纯的深度优先遍历算法和广度优先遍历算法，而是需要在遍历的过程中加入与解决题目相关的逻辑。

题干中说了，这个图可能不是连通图，这个提示有什么作用呢？

很多时候我们接触的题目，图都是连通的，对于连通图来说，从一个点开始遍历，不管是深度优先还是广度优先，遍历一遍就可以把图中的所有点都遍历到；而对于非连通图来说，从一个点开始遍历，就无法将所有点都遍历一遍，这就需要针对每个点都进行一次遍历。

不管使用深度优先遍历算法还是使用广度优先遍历算法，都要实时记录结果，如果当前已经确定了不是连通图，那么说明结果已经确定了，就不需要继续判断，直接返回就可以。因为已经判断不是连通图，那么再继续判断下去没有意义，不是连通图的情况已经确定；如果在判断过程中，一直是连通图，那么还有没有遍历到的点，还是需要继续遍历的，因为剩下的点可能是不连通的。

1 深度优先遍历算法

class Solution {
public:
    enum Color {
        kUnColored = 0,
        kRed = 1,
        kGreen = 2
    };
    // 如果已经确定不是连通图了，就不需要继续遍历了
    bool isBipartite(vector<vector<int>>& graph) {
      int size = graph.size();
      // 图可能是非连通图，所以需要从每个节点开始进行一次遍历
      for (int i = 0; i < size && result == true; i++) {
        // 如果这个点没有遍历到，那么才需要遍历，已经遍历到的不需要继续遍历
        if (dataColor[i] == Color::kUnColored) {
          dfsScanGraph(graph, i, Color::kRed);
        }
      }
      return result;
    }

    void dfsScanGraph(vector<vector<int>> &graph, int const node, Color const color) {
       if (result == false) {
           return;
       }
       dataColor[node] = color;
       const Color line_color{color == Color::kRed ? Color::kGreen : Color::kRed};
       
       //给node连接的这一行的节点染色
       for (int data : graph[node]) {
         if (result == false) {
            return;
         }
         // 1、如果与node颜色相同，那么这两者属于同一个区域，可以确定不是二分图
         // 2、如果这个点还没有染色，那么进行递归染色，颜色与node不同的颜色
         // 3、如果节点已经染色，并且与node颜色不同，那么不做处理
         if (dataColor[data] == color) {
            result = false;
            return;
         } else if (dataColor[data] == Color::kUnColored){
            dfsScanGraph(graph, data, line_color);  
         }
       }
    }

private:
  int dataColor[101] = {0};
  bool result = true;
};

2 广度优先遍历算法

class Solution {
public:
    enum Color {
        kUnColored = 0,
        kRed = 1,
        kGreen = 2
    };

    bool isBipartite(vector<vector<int>>& graph) {
      int size = graph.size();
      for (int i = 0; i < size && result == true; i++) {
          if (dataColor[i] == Color::kUnColored) {
              // 广度优先遍历需要使用一个队列来辅助
              // 每一次广度优先遍历，都使用一个新的，空的队列
              std::queue<int> queue;
              bfsScanGraph(graph, i, Color::kRed, queue);
          }
      }
      return result;
    }

    void bfsScanGraph(vector<vector<int>> &graph, int const data, Color const color,std::queue<int> &queue) {
        if (result == false) {
            return;
        }

        dataColor[data] = color;
        queue.push(data);

        
        while (!queue.empty()) {
            int head_data = queue.front();
            queue.pop();
            const Color another_color{dataColor[head_data] == Color::kRed ? Color::kGreen : Color::kRed};

            for (int line_data : graph[head_data]) {
                if (result == false) {
                    return;
                }

                if (dataColor[line_data] == Color::kUnColored) {
                    dataColor[line_data] = another_color;
                    queue.push(line_data);
                } else {
                    // 这里比较的对象与深度优先遍历中比较的是不一样的
                    // 深度优先比较的对象是node，广度优先比较的对象是出队的head_data
                    // 两者的相同点，比较的对象都是与这一行的行首进行比较，行首表示这与当前这个节点是临接点
                    if (dataColor[line_data] == dataColor[head_data]) {
                        result = false;
                        return;
                    }
                }
            }

        }
    }

private:
  int dataColor[101] = {0};
  bool result = true;
};