2024/06/08记录
算法小计 785. 判断二分图 - 力扣（LeetCode） https://leetcode.cn/problems/is-graph-bipartite/?envType=study-plan-v2&envId=2024-spring-sprint-100 这题不能被描述带偏。我一开始的思路是找如何将图分为两部分，没有特别好的想法 实际上本题采用的方法是 染色 ，让我想起了JVM中垃圾收集的三色标记法，三色标记法…
算法小计
785. 判断二分图 - 力扣（LeetCode）
这题不能被描述带偏。我一开始的思路是找如何将图分为两部分，没有特别好的想法
实际上本题采用的方法是染色，让我想起了JVM中垃圾收集的三色标记法，三色标记法的本质也是将所有的对象分为可以被回收的和不能被回收的两个集合，也就是三个状态，白色代表还未被标记，灰色代表正在被标记，黑色代表标记完成
通过配置不同的标记的规则，可以将图划分为两个不同的集合，按照本题给出的条件，图中的每一条边的的两个节点，一个节点来自集合A，一个节点来自集合B，可以推出染色的规则。同一边上的两个节点的颜色不同
做题的思路
对于图的题目，可以建模，可以遍历，基本上解决了大部分问题。
遍历的方式有两种，分别为DFS和BFS
首先是DFS，在编写DFS的时候，我认为应该从每个节点开始染色，实际上，如果某个节点已经被染色过，并且不能完全染色，说明以该节点起始的路径都是不可以的
题目中给定的无向图不一定保证连通，因此我们需要进行多次遍历，直到每一个节点都被染色，或确定答案为 false 为止。每次遍历开始时，我们任选一个未被染色的节点，将所有与该节点直接或间接相连的节点进行染色。
DFS
class Solution {
private int UNCOLORED = 0;
private int RED = 1;
private int GREEN = 2;
private int[] color;
private boolean isVaild;
public boolean isBipartite(int[][] graph) {
isVaild = true;
color = new int[graph.length];
for (int i = 0; i < graph.length && isVaild; i++) {
// 从所有节点尝试向下遍历并染色
if (color[i] == UNCOLORED) {
dfs(graph, RED, i);
}
}
return isVaild;
}
public void dfs(int[][] graph, int c, int cur) {
color[cur] = c;
int nextC = c == RED ? GREEN : RED;
for (int t : graph[cur]) {
if (color[t] == UNCOLORED) {
dfs(graph, nextC, t);
// 如果返回后，发现存在一个节点已经被染色，并且颜色和待染色的节点产生冲突，说明本条路不行
if (!isVaild) {
return;
}
} else if (color[t] != nextC) {
isVaild = false;
return;
}
}
}
}BFS
class Solution {
private int UNCOLORED = 0;
private int RED = 1;
private int GREEN = 2;
private int[] color;
public boolean isBipartite(int[][] graph) {
int n = graph.length;
color = new int[n];
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (color[i] == UNCOLORED) {
queue.offerFirst(i);
// 起始节点默认位RED
color[i] = RED;
while (!queue.isEmpty()) {
int node = queue.pollLast();
int cNei = color[node] == RED ? GREEN : RED;
for (int neighbor : graph[node]) {
if (color[neighbor] == UNCOLORED) {
color[neighbor] = cNei;
queue.offerFirst(neighbor);
} else if (color[neighbor] != cNei) {
return false;
}
}
}
}
}
return true;
}
}并查集
如果是二分图的话，那么图中每个顶点的所有邻接点都应该属于同一集合，且不与顶点处于同一集合。因此我们可以使用并查集来解决这个问题，我们遍历图中每个顶点，将当前顶点的所有邻接点进行合并，并判断这些邻接点中是否存在某一邻接点已经和当前顶点处于同一个集合中了，若是，则说明不是二分图。
class Solution {
public boolean isBipartite(int[][] graph) {
UnionFind uf = new UnionFind(graph.length);
for (int i = 0; i < graph.length; i++) {
int[] adjs = graph[i];
for (int w : adjs) {
if (uf.isConnected(i, w)) {
return false;
}
uf.union(adjs[0], w);
}
}
return true;
}
}
class UnionFind {
int[] roots;
public UnionFind(int n) {
roots = new int[n];
for (int i = 0; i < n; i++) {
roots[i] = i;
}
}
public int find(int i) {
if (roots[i] == i) {
return i;
}
return roots[i] = find(roots[i]);
}
public boolean isConnected(int p, int q) {
return find(q) == find(p);
}
public void union(int p, int q) {
roots[find(p)] = find(q);
}
}