算法题判断二分图-洪萨配资

判断二分图

问题描述

存在一个无向图，图中有n个节点，编号从0到n - 1。给你一个二维数组graph表示图的邻接表，其中graph[u]是一个节点数组，表示与节点u相邻的节点。

如果可以将图中节点分为两组，使得每条边的两个节点分别属于不同组，则称这个图是二分图。

请你判断给定的图是否是二分图。如果是，返回true；否则，返回false。

示例：

输入: graph = [[1,2,3],[0,2],[0,1,3],[0,2]] 输出: false 解释: 节点不能分成两组，使得每条边的两个节点在不同组。 因为存在奇数长度的环（三角形0-1-2-0）。 输入: graph = [[1,3],[0,2],[1,3],[0,2]] 输出: true 解释: 可以将节点分成两组: {0, 2} 和 {1, 3}。

算法思路

经典的图着色问题，可以用深度优先搜索（DFS）或广度优先搜索（BFS）解决。

二分图：

着色：可以用两种颜色对图进行着色，使得相邻节点颜色不同
环：图中不存在奇数长度的环（奇环）
等价：图是二分图 = 图中所有环的长度都是偶数

方法：

图着色：为每个节点分配颜色（0或1），相邻节点必须颜色不同
冲突检测：如果发现相邻节点颜色相同，则不是二分图
连通分量：图可能不连通，需要检查所有连通分量

代码实现

方法一：DFS

classSolution{/** * 使用DFS判断图是否为二分图 * * @param graph 邻接表表示的无向图 * @return true表示是二分图，false表示不是 */publicbooleanisBipartite(int[][]graph){intn=graph.length;// color[i] 表示节点i的颜色，-1表示未着色，0和1表示两种颜色int[]color=newint[n];Arrays.fill(color,-1);// 遍历所有节点，处理可能的多个连通分量for(inti=0;i<n;i++){// 如果节点未着色，从该节点开始DFS着色if(color[i]==-1){if(!dfs(graph,color,i,0)){returnfalse;}}}returntrue;}/** * DFS着色函数 * * @param graph 邻接表 * @param color 颜色数组 * @param node 当前节点 * @param c 当前要着的颜色 * @return true表示着色成功，false表示发现冲突 */privatebooleandfs(int[][]graph,int[]color,intnode,intc){// 为当前节点着色color[node]=c;// 遍历所有相邻节点for(intneighbor:graph[node]){if(color[neighbor]==-1){// 相邻节点未着色，递归着色为相反颜色if(!dfs(graph,color,neighbor,1-c)){returnfalse;}}elseif(color[neighbor]==c){// 相邻节点已着色且颜色相同，发现冲突returnfalse;}// 如果相邻节点颜色不同（color[neighbor] == 1 - c），继续检查}returntrue;}}

方法二：BFS

importjava.util.*;classSolution{/** * 使用BFS判断图是否为二分图 * * @param graph 邻接表表示的无向图 * @return true表示是二分图，false表示不是 */publicbooleanisBipartite(int[][]graph){intn=graph.length;int[]color=newint[n];Arrays.fill(color,-1);// 遍历所有节点for(inti=0;i<n;i++){if(color[i]==-1){if(!bfs(graph,color,i)){returnfalse;}}}returntrue;}/** * BFS着色函数 * * @param graph 邻接表 * @param color 颜色数组 * @param start 起始节点 * @return true表示着色成功，false表示发现冲突 */privatebooleanbfs(int[][]graph,int[]color,intstart){Queue<Integer>queue=newLinkedList<>();queue.offer(start);color[start]=0;// 起始节点着色为0while(!queue.isEmpty()){intnode=queue.poll();intcurrentColor=color[node];// 遍历相邻节点for(intneighbor:graph[node]){if(color[neighbor]==-1){// 未着色，着相反颜色color[neighbor]=1-currentColor;queue.offer(neighbor);}elseif(color[neighbor]==currentColor){// 颜色冲突returnfalse;}}}returntrue;}}

方法三：并查集

classSolution{/** * 使用并查集判断二分图 * 核心思想：每个节点u和它的所有邻居v应该在不同的集合中 * 将u的所有邻居合并到同一个集合，然后检查u是否与该集合连通 */publicbooleanisBipartite(int[][]graph){intn=graph.length;UnionFinduf=newUnionFind(n);// 遍历每个节点for(intu=0;u<n;u++){int[]neighbors=graph[u];if(neighbors.length==0)continue;// 将u的所有邻居合并到同一个集合intfirstNeighbor=neighbors[0];for(inti=1;i<neighbors.length;i++){uf.union(firstNeighbor,neighbors[i]);}// 检查u是否与邻居集合连通（如果是，则不是二分图）if(uf.isConnected(u,firstNeighbor)){returnfalse;}}returntrue;}/** * 并查集实现 */classUnionFind{privateint[]parent;privateint[]rank;publicUnionFind(intn){parent=newint[n];rank=newint[n];for(inti=0;i<n;i++){parent[i]=i;rank[i]=0;}}publicintfind(intx){if(parent[x]!=x){parent[x]=find(parent[x]);// 路径压缩}returnparent[x];}publicvoidunion(intx,inty){introotX=find(x);introotY=find(y);if(rootX!=rootY){// 按秩合并if(rank[rootX]<rank[rootY]){parent[rootX]=rootY;}elseif(rank[rootX]>rank[rootY]){parent[rootY]=rootX;}else{parent[rootY]=rootX;rank[rootX]++;}}}publicbooleanisConnected(intx,inty){returnfind(x)==find(y);}}}

算法分析

时间复杂度：
- DFS/BFS：O(V + E)，V是节点数，E是边数
- 并查集：O(E × α(V))，α为常数
空间复杂度：
- DFS：O(V) - 递归栈空间
- BFS：O(V) - 队列空间
- 并查集：O(V) - parent和rank数组

算法过程

1：graph = [[1,3],[0,2],[1,3],[0,2]]（二分图）

DFS过程：

从节点0开始，着色为0
节点1和3着色为1
从节点1，节点2着色为0
从节点3，检查节点2已着色为0（与节点3的1不同）
所有节点着色成功，返回true

着色结果：

组0：{0, 2}
组1：{1, 3}

2：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]（非二分图）

DFS过程：

从节点0开始，着色为0
节点1、2、3着色为1
从节点1，检查节点2已着色为1（与节点1相同）
发现冲突，返回false

冲突原因：存在三角形环0-1-2-0（奇数长度环）

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准二分图int[][]graph1={{1,3},{0,2},{1,3},{0,2}};System.out.println("Test 1: "+solution.isBipartite(graph1));// true// 测试用例2：非二分图（奇环）int[][]graph2={{1,2,3},{0,2},{0,1,3},{0,2}};System.out.println("Test 2: "+solution.isBipartite(graph2));// false// 测试用例3：单个节点int[][]graph3={{}};System.out.println("Test 3: "+solution.isBipartite(graph3));// true// 测试用例4：两个节点一条边int[][]graph4={{1},{0}};System.out.println("Test 4: "+solution.isBipartite(graph4));// true// 测试用例5：三个节点形成三角形int[][]graph5={{1,2},{0,2},{0,1}};System.out.println("Test 5: "+solution.isBipartite(graph5));// false// 测试用例6：四个节点形成正方形int[][]graph6={{1,3},{0,2},{1,3},{0,2}};System.out.println("Test 6: "+solution.isBipartite(graph6));// true// 测试用例7：不连通图（多个连通分量）int[][]graph7={{1},{0},{3},{2}};System.out.println("Test 7: "+solution.isBipartite(graph7));// true// 测试用例8：不连通图包含奇环int[][]graph8={{1,2},{0,2},{0,1},{4},{3}};System.out.println("Test 8: "+solution.isBipartite(graph8));// false// 测试用例9：空图int[][]graph9={};System.out.println("Test 9: "+solution.isBipartite(graph9));// true// 测试用例10：星型图int[][]graph10={{1,2,3,4},{0},{0},{0},{0}};System.out.println("Test 10: "+solution.isBipartite(graph10));// true}