leetcode_785. 判断二分图

785. 判断二分图 - 力扣（LeetCode）

 

实现思路：观察题目发现 给个节点只能与另外两个节点相连 才能叫作二分图 那么我们只需要找到一个节点与其他节点相连的节点数量大于两个 那么这个图将不是二分图

具体实现：我们可以使用染色法 先将所有节点看作白色 表示未被访问 访问该节点是 将其染色 访问该节点的下一节点之后 将其下一节点也进行染色 但是 为了表示染色的颜色只有两个 我们可以先将第一个节点染色为颜色 0  那么他的下一节点 将会是这样子染色 color[v] = 1 - color[u]; (u表示当前节点 v表示 下一节点, 只有下一节点没有被染色时才需要进行染色 ) 这样子的一个染色思路 只会出现 0 1 这两个染色标记(已经访问过) 当我们访问过程中 发现当前节点与下一节点的颜色相同 那么就不是一个二分图

图示

这个不是二分图

二分图示例

循环解法

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int color[101];
        memset( color, -1, sizeof(color) );
        for ( int i = 0; i < graph.size(); ++i ){
            if ( color[i] != -1 ){
                continue;
            }
            
            color[i] = 0;
            queue<int> q;
            q.push( i );

            while ( !q.empty() ){
                int u = q.front();
                q.pop();
                for ( int v : graph[u] ){
                    if ( color[v] == -1 ){  //v节点已经被访问过且颜色等于当前节点
                        color[v] = 1 - color[u];
                        q.push(v);
                    }
                    else if ( color[v] == color[u] ){
                        return false;
                    }
                }
            } 
        } 
        return true;
    }
};

递归解法

class Solution {
    int color[101];

    bool dfs(vector<vector<int>>& graph, int node, int c) { 
        color[node] = c;
        for ( int neighbor : graph[node] ){
            if ( color[neighbor] == -1 ){
                if ( !dfs( graph, neighbor, 1 - c ) ){
                    return false;
                }
            }else if ( color[node] == color[neighbor] ){
                return false;
            }
        }
        return true;
    }

public:
    bool isBipartite(vector<vector<int>>& graph) {
        memset(color, -1, sizeof(color));
        for (int i = 0; i < graph.size(); ++i) {
            if (color[i] == -1) {
                if ( !dfs( graph, i, 0) ) {
                    return false;
                }
            }
        }
        return true;
    }
};

原文地址：https://blog.csdn.net/m0_63056769/article/details/144397878

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！