Java LeetCode 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
| |
| |
3----2
我們可以将節點分成兩組: {0, 2} 和 {1, 3}。
示例 2:
輸入: [[1,2,3], [0,2], [0,1,3], [0,2]]
輸出: false
解釋:
無向圖如下:
0----1
| \ |
| \ |
3----2
我們不能将節點分割成兩個獨立的子集。
**注意:**
graph 的長度範圍為 [1, 100]。
graph[i] 中的元素的範圍為 [0, graph.length - 1]。
graph[i] 不會包含 i 或者有重複的值。
圖是無向的: 如果j 在 graph[i]裡邊, 那麼 i 也會在 graph[j]裡邊。
題目分析
二分圖定義
設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關聯的兩個頂點i和j分别屬于這兩個不同的頂點集(i in A,j in B)，則稱圖G為一個二分圖。簡單來說，如果圖中點可以被分為兩組，并且使得所有邊都跨越組的邊界，則這就是一個二分圖。
圖中U和V構造的點集所形成的循環圈不為奇數，是以是二分圖
圖中U和V和W構造的點集所形成的的循環圈為奇數，是以不是二分圖
思路
如果節點屬于第一個集合，将其着為藍色，否則着為紅色。隻有在二分圖的情況下，所有節點都可以分成兩個集合，一個為藍色節點的集合和一個為紅色的節點集合：一個節點為藍色，說明它的所有鄰接點為紅色，它的鄰接點的所有鄰接點為藍色，依此類推。
算法
使用棧完成深度優先搜尋，存儲着下一個要通路節點的順序。在 graph[node] 中，對每個未着色鄰接點，着色該節點并将其放入到棧中。搜尋節點時，需要考慮圖是非連通的情況。對每個未着色節點，從該節點開始深度優先搜尋着色。每個鄰接點都可以通過目前節點着相反的顔色。如果存在目前點和鄰接點顔色相同，則着色失敗。
代碼
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n]; //存取每個節點的顔色的數組
Arrays.fill(color, -1); // 初始化，-1代表未着色，0代表藍色 ，1代表紅色
for (int i = 0; i < n; ++i) {
if (color[i] == -1) {
Stack<Integer> stack = new Stack();
stack.push(i);
color[i] = 0;
while (!stack.empty()) {
Integer node = stack.pop();
for (int j: graph[node]) {
if (color[j] == -1) {
stack.push(j);
color[j] = color[node] ^ 1;
} else if (color[j] == color[node]) {
return false;
}
}
}
}
}
return true;
}
}
參考于：https://blog.csdn.net/qq_28468707/article/details/103718238?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3.nonecase