785. 判断二分图
给定一个无向图graph，当这个图为二分图时返回true。
如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。
graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。
示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释:
无向图如下:
0----1
|
在计算机科学中，二分图（Bipartite Graph）是一种特殊的无向图，其中所有节点可以被划分为两个不相交的集合A和B，使得图中的每条边连接的两个节点分别属于不同的集合。如果一个图可以被这样划分，那么它就被称为二分图。在LeetCode的785题“判断二分图”中，我们需要编写一个程序来确定给定的无向图是否为二分图。
给定的输入是以邻接表的形式表示的，其中`graph[i]`是一个列表，包含了与节点i相邻的所有节点。由于图是无向的，所以如果节点j在`graph[i]`中，那么节点i也会在`graph[j]`中。题目保证了图中没有自环（即一个节点不会与自身相连）和平行边（即一个边不会重复出现）。
要判断一个图是否为二分图，我们可以采用深度优先搜索（DFS）或广度优先搜索（BFS）的方法。这里使用的是BFS策略，因为BFS通常更容易处理颜色分配，而且在解决这类问题时效率较高。
我们创建一个颜色数组`color`，长度与节点数相同，并将其所有元素初始化为-1。-1表示节点尚未被染色。接下来，我们遍历所有的节点，对于每个未染色的节点，我们可以将其作为起始节点进行BFS。我们使用一个栈来存储待处理的节点，并在初始时将起始节点染上一种颜色，例如0。在BFS过程中，每当访问到一个新节点，我们就将其染上与父节点不同颜色（颜色值异或1，0变1，1变0），确保同一条边连接的两个节点颜色不同。如果发现相邻节点的颜色相同，说明图不是二分图，返回false。如果遍历完整个图都没有发现颜色冲突，那么图是二分图，返回true。
以下是Java代码实现的详细步骤：
1. 初始化颜色数组`color`，用-1表示未染色。
2. 遍历所有节点，对每个未染色的节点执行以下操作：
a. 使用栈`stack`进行BFS，将起始节点入栈并染色。
b. 当栈非空时，执行以下操作：
i. 弹出栈顶节点`node`，检查其所有邻居`nei`。
ii. 如果邻居`nei`未染色，将其入栈并染上与`node`颜色异或1的颜色。
iii. 如果邻居`nei`已染色且颜色与`node`相同，说明存在颜色冲突，返回false。
3. 如果BFS过程结束没有返回false，说明图是二分图，返回true。
代码如下：
```java
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
Arrays.fill(color, -1);
for (int start = 0; start < n; ++start) {
if (color[start] == -1) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
color[start] = 0;
while (!stack.empty()) {
Integer node = stack.pop();
for (int nei : graph[node]) {
if (color[nei] == -1) {
stack.push(nei);
color[nei] = color[node] ^ 1;
} else if (color[nei] == color[node]) {
return false;
}
}
}
}
}
return true;
}
}
```
这个解决方案的时间复杂度是O(V+E)，V是节点数，E是边数，因为每个节点和边都会被访问一次。空间复杂度是O(V)，用于存储颜色数组和BFS过程中使用的栈。这个算法能够有效地判断一个无向图是否为二分图。
