785. 判断二分图

原题链接：

785. 判断二分图

https://leetcode.cn/problems/is-graph-bipartite/description/

完成情况：

解题思路：

 题目解释：每个节点都有一个编号 0~~~n-1然后一个graph[][] 二维数组，其中每个数组graph[u]，代表按编号顺序过去的，里面的内容即为与当前对应编号所连接的边有哪些。

染色法 去解。

在算法中，“染色法” 通常指的是图论中的一种算法，用于解决图的染色问题，其中最经典的问题就是图的顶点着色问题。该问题的目标是为图的顶点分配颜色，使得任何相邻的顶点具有不同的颜色，同时最小化所使用的颜色数目。

这个问题在现实生活中有很多应用，例如在时间表设计中，课程或会议安排不同时需要同一时间和地点的资源，就可以使用图的染色方法来解决。

染色法有不同的变种和算法，其中一种基本的方法是贪心染色算法。贪心染色算法从一个顶点开始，为其分配一个颜色，然后遍历相邻的顶点，为每个相邻顶点分配一个颜色，但要确保分配的颜色与其相邻顶点的颜色不同。然后继续遍历未着色的顶点，为其分配颜色，并重复这个过程，直到所有顶点都被染色。

然而，贪心染色算法并不总能保证得到最少的颜色数。在一些情况下，可能需要使用更复杂的图染色算法，如回溯法、分支限界法等，来找到更优的染色方案。

总之，“染色法” 是解决图的顶点着色问题的一种算法，用于在满足相邻顶点颜色不同的条件下，找到尽可能少的颜色数目。

参考代码：

package 西湖算法题解___中等题;public class __785判断二分图__染色法     {/**题目解释：每个节点都有一个编号 0~~~n-1然后一个graph[][] 二维数组，其中每个数组graph[u]，代表按编号顺序过去的，里面的内容即为与当前对应编号所连接的边有哪些。*/int color [];public boolean isBipartite(int[][] graph) {int nLength = graph.length;     //这是一个无向图color = new int[nLength];boolean flag = true;for (int i=0;i<nLength;i++){if (color[i] == 0){if (!dfs_isBipartite(i,1,graph)){flag = false;}}}return flag;}/**** @param u* @param c* @param graph* @return*/private boolean dfs_isBipartite(int u, int c, int[][] graph) {color[u]  = c;for (int i = 0;i<graph[u].length;i++){int node = graph[u][i];if (color[node] == 0) {if (!dfs_isBipartite(node, 3 - c, graph)) {return false;}} else {if (color[node] == c){return false;}}}return true;}
}