leetcode:判断二分图(图的遍历)
程序员文章站
2022-06-21 13:31:32
https://leetcode-cn.com/problems/is-graph-bipartite/思路:根据分析可知,任意两个相邻的节点,一定是一个属于集合A,一个属于集合B。可以用一个标记的方式来判断,从任意一个点开始,先把他标记为红色,然后遍历整个图将与他直接相连的点标记为绿色,再继续遍历绿色的点,把他们直接相邻的点标为红色。如果在遍历的过程中,比如一个已经标为红色的点,他的相邻的点也为红色,那么这个就不符合二分图,直接返回false。直到所有点都被标记,那么就返回true。图的遍历有...
https://leetcode-cn.com/problems/is-graph-bipartite/
思路:根据分析可知,任意两个相邻的节点,一定是一个属于集合A,一个属于集合B。可以用一个标记的方式来判断,从任意一个点开始,先把他标记为红色,然后遍历整个图将与他直接相连的点标记为绿色,再继续遍历绿色的点,把他们直接相邻的点标为红色。如果在遍历的过程中,比如一个已经标为红色的点,他的相邻的点也为红色,那么这个就不符合二分图,直接返回false。直到所有点都被标记,那么就返回true。
图的遍历有两种方式,一个是深度,一个是广度。(顺便复习一下图的遍历)
DFS
class Solution {
static final int NO = 0;
static final int RED = 1;
static final int GREEN = 2;
static int[] color;//保存每个节点的颜色
static boolean isOK;
public static boolean isBipartite(int[][] graph) {
int n = graph.length;//节点的个数
isOK = true;
color = new int[n];
Arrays.fill(color, NO);//初始化为无色
//图可能不是连通图,要全部遍历一遍
for (int i = 0; i < n && isOK; ++i) {
if (color[i] == NO) {
dfs(i, RED, graph);
}
}
return isOK;
}
/**
* @param i 节点
* @param c 该节点的颜色
*/
public static void dfs(int i, int c, int[][] graph) {
color[i] = c;
int c2;//相邻节点的颜色
if(c == RED) c2 = GREEN;
else c2 = RED;
for (int neighbor : graph[i]) {
if (color[neighbor] == NO) {
dfs(neighbor, c2, graph);
} else if (color[neighbor] == c) {
isOK = false;
return;
}
}
}
}
BFS
class Solution {
static final int NO = 0;
static final int RED = 1;
static final int GREEN = 2;
static int[] color;//保存每个节点的颜色
public static boolean isBipartite(int[][] graph) {
int n = graph.length;//节点的个数
color = new int[n];
Arrays.fill(color, NO);//初始化为无色
for (int i = 0; i < n; i++) {
if(color[i] == NO){
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(i);
color[i] = RED;
while (!queue.isEmpty()){
int node = queue.poll();
int c2;
if(color[node] == RED) c2 = GREEN;
else c2 = RED;
for (int neighbor:graph[node]) {
if(color[neighbor] == NO){
queue.offer(neighbor);
color[neighbor] = c2;
}else if(color[neighbor] != c2){
return false;
}
}
}
}
}
return true;
}
}
本文地址:https://blog.csdn.net/vv0606/article/details/107381513
上一篇: 高德地图车机版进入评测 实时联网成亮点