IsGraphBipartite [source code]
public class IsGraphBipartite {
static
/******************************************************************************/
class Solution {
public boolean isBipartite(int[][] graph) {
int V = graph.length;
if (V <= 1)
return true; // no illegal edges since no edges;
Boolean[] colors = new Boolean[V];
for (int i = 0; i < V; i++) if (colors[i] == null && !color (graph, colors, true, i))
return false;
return true;
}
boolean color (int[][] graph, Boolean[] colors, Boolean color, int node) {
if (colors[node] != null)
return colors[node] == color;
colors[node] = color;
color = !color;
int[] neighbors = graph[node];
for (int neighbor : neighbors) {
if (!color (graph, colors, color, neighbor))
return false;
}
return true;
}
}
/******************************************************************************/
public static void main(String[] args) {
IsGraphBipartite.Solution tester = new IsGraphBipartite.Solution();
int[][][] inputs = {
{{1,3}, {0,2}, {1,3}, {0,2}}, {{1}},
{{1,2,3}, {0,2}, {0,1,3}, {0,2}}, {{0}},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int[][] graph = inputs[2 * i];
boolean ans = inputs[2 * i + 1][0][0] == 1, output = tester.isBipartite (graph);
System.out.printf ("%s -> %s, expected: %b\n",
Matrix.printMatrix (graph), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
https://www.geeksforgeeks.org/bipartite-graph/
这个问题在Sedgwick上面也是有讲过, 归根到底实际上还是一个cycle detection问题;
这个题目其实主要还是想法; 要想到这种cycle才是出现问题的本质, 然后就知道用DFS来做了; 找到思路的核心技巧估计还是自己举例子笔算;
速度6ms (NA);
自己发帖的解释:
Try to color all nodes with alternating colors. If we came back to an already-colored node with a different color, then we return false. This is a typical application of DFS/BFS cycle detection described in Robert Sedgwick's Algorithms book.
Slight explanation of correctness: why is it that we can be sure that as long as we have a cycle, where we try to color one node with a different color the second time, we know for sure the graph is bad? This is because the node just prior to the conflicting node must have the same color as the conflicting node itself. And as long as such a cycle exists, there is no way you can bipartite-partition all nodes within this cycle because, well, these two just won't do.
Multiple DFS is required since the nodes might not be fully connected. Each DFS will color one independent subgraph. If one DFS discovers that one subgraph is okay, we can safely move on: it does not matter anymore because this subgraph and its consisting nodes won't further affect any other independent subgraph.
editorial
Approach #1: Coloring by Depth-First Search [Accepted]
Intuition
Color a node blue if it is part of the first set, else red. We should be able to greedily color the graph if and only if it is bipartite: one node being blue implies all it's neighbors are red, all those neighbors are blue, and so on.
Algorithm
We'll keep an array (or hashmap) to lookup the color of each node: color[node]. The colors could be 0, 1, or uncolored (-1 or null).
We should be careful to consider disconnected components of the graph, by searching each node. For each uncolored node, we'll start the coloring process by doing a depth-first-search on that node. Every neighbor gets colored the opposite color from the current node. If we find a neighbor colored the same color as the current node, then our coloring was impossible.
To perform the depth-first search, we use a stack. For each uncolored neighbor in graph[node], we'll color it and add it to our stack, which acts as a sort of "todo list" of nodes to visit next. Our larger loop for start... ensures that we color every node.
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;
}
}
又是这个naive Stack DFS, 也是awice的拿手好戏了;
Our goal is trying to use two colors to color the graph and see if there are any adjacent nodes having the same color.
Initialize a color[] array for each node. Here are three states for colors[] array:
-1: Haven't been colored.
0: Blue.
1: Red.
For each node,
- If it hasn’t been colored, use a color to color it. Then use another color to color all its adjacent nodes (DFS).
- If it has been colored, check if the current color is the same as the color that is going to be used to color it. (Please forgive my english… Hope you can understand it.)
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] colors = new int[n];
Arrays.fill(colors, -1);
for (int i = 0; i < n; i++) { //This graph might be a disconnected graph. So check each unvisited node.
if (colors[i] == -1 && !validColor(graph, colors, 0, i)) {
return false;
}
}
return true;
}
public boolean validColor(int[][] graph, int[] colors, int color, int node) {
if (colors[node] != -1) {
return colors[node] == color;
}
colors[node] = color;
for (int next : graph[node]) {
if (!validColor(graph, colors, 1 - color, next)) {
return false;
}
}
return true;
}
}
明明跟我的写法没有区别, 我发帖还比较早, 不知道为什么他的这么upvote这么多;
跟我一样, 这里还是用了一个boolean返回值prune的技巧, 这样就不用用global switch这样的prune了;
https://leetcode.com/problems/is-graph-bipartite/discuss/115528/Java-BFS-with-explanation
class Solution {
public boolean isBipartite(int[][] graph) {
if (graph == null || graph.length == 0) return true;
int color[] = new int[graph.length];
LinkedList < Integer > q = new LinkedList();
for (int i = 0; i < graph.length; i++) {
if (color[i] == 0) {
q.add(i);
color[i] = 1;
while (q.size() != 0) {
int node = q.removeFirst();
for (int child: graph[node]) {
if (color[child] == 0) {
color[child] = color[node] == 2 ? 1 : 2;
q.add(child);
} else if (color[child] == color[node]) return false;
}
}
}
}
return true;
}
}
> Can we divide the node in two sets such that no two nodes in same set are linked. This was the problem. But sometimes, graph can be a forest. So, we need to check if every node has been processed/colored/discovered or not. O(E)
BFS来搜索每一个CC;
---
submission还没有;
---
### Problem Description
Given a graph, return true if and only if it is bipartite.
Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.
Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
| |
| |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \ |
| \ |
3----2
We cannot find a way to divide the set of nodes into two independent ubsets.
```
Note:
- graph will have length in range [1, 100].
- graph[i] will contain integers in range [0, graph.length - 1].
- graph[i] will not contain i or duplicate values.
Difficulty:Medium
Total Accepted:714
Total Submissions:2.3K
Contributor:awice