公司網(wǎng)站建設需要哪些,餐飲裝修,上海巴士公司,開阿里巴巴網(wǎng)站建設流程判斷二分圖 問題描述 存在一個無向圖#xff0c;圖中有 n 個節(jié)點#xff0c;編號從 0 到 n - 1。給你一個二維數(shù)組 graph 表示圖的鄰接表#xff0c;其中 graph[u] 是一個節(jié)點數(shù)組#xff0c;表示與節(jié)點 u 相鄰的節(jié)點。 如果可以將圖中節(jié)點分為兩組#xff0c;使得每條…判斷二分圖問題描述存在一個無向圖圖中有n個節(jié)點編號從0到n - 1。給你一個二維數(shù)組graph表示圖的鄰接表其中graph[u]是一個節(jié)點數(shù)組表示與節(jié)點u相鄰的節(jié)點。如果可以將圖中節(jié)點分為兩組使得每條邊的兩個節(jié)點分別屬于不同組則稱這個圖是二分圖。請你判斷給定的圖是否是二分圖。如果是返回true否則返回false。示例輸入: graph [[1,2,3],[0,2],[0,1,3],[0,2]] 輸出: false 解釋: 節(jié)點不能分成兩組使得每條邊的兩個節(jié)點在不同組。 因為存在奇數(shù)長度的環(huán)三角形0-1-2-0。 輸入: graph [[1,3],[0,2],[1,3],[0,2]] 輸出: true 解釋: 可以將節(jié)點分成兩組: {0, 2} 和 {1, 3}。算法思路經(jīng)典的圖著色問題可以用深度優(yōu)先搜索DFS或廣度優(yōu)先搜索BFS解決。二分圖著色可以用兩種顏色對圖進行著色使得相鄰節(jié)點顏色不同環(huán)圖中不存在奇數(shù)長度的環(huán)奇環(huán)等價圖是二分圖 圖中所有環(huán)的長度都是偶數(shù)方法圖著色為每個節(jié)點分配顏色0或1相鄰節(jié)點必須顏色不同沖突檢測如果發(fā)現(xiàn)相鄰節(jié)點顏色相同則不是二分圖連通分量圖可能不連通需要檢查所有連通分量代碼實現(xiàn)方法一DFSclassSolution{/** * 使用DFS判斷圖是否為二分圖 * * param graph 鄰接表表示的無向圖 * return true表示是二分圖false表示不是 */publicbooleanisBipartite(int[][]graph){intngraph.length;// color[i] 表示節(jié)點i的顏色-1表示未著色0和1表示兩種顏色int[]colornewint[n];Arrays.fill(color,-1);// 遍歷所有節(jié)點處理可能的多個連通分量for(inti0;in;i){// 如果節(jié)點未著色從該節(jié)點開始DFS著色if(color[i]-1){if(!dfs(graph,color,i,0)){returnfalse;}}}returntrue;}/** * DFS著色函數(shù) * * param graph 鄰接表 * param color 顏色數(shù)組 * param node 當前節(jié)點 * param c 當前要著的顏色 * return true表示著色成功false表示發(fā)現(xiàn)沖突 */privatebooleandfs(int[][]graph,int[]color,intnode,intc){// 為當前節(jié)點著色color[node]c;// 遍歷所有相鄰節(jié)點for(intneighbor:graph[node]){if(color[neighbor]-1){// 相鄰節(jié)點未著色遞歸著色為相反顏色if(!dfs(graph,color,neighbor,1-c)){returnfalse;}}elseif(color[neighbor]c){// 相鄰節(jié)點已著色且顏色相同發(fā)現(xiàn)沖突returnfalse;}// 如果相鄰節(jié)點顏色不同color[neighbor] 1 - c繼續(xù)檢查}returntrue;}}方法二BFSimportjava.util.*;classSolution{/** * 使用BFS判斷圖是否為二分圖 * * param graph 鄰接表表示的無向圖 * return true表示是二分圖false表示不是 */publicbooleanisBipartite(int[][]graph){intngraph.length;int[]colornewint[n];Arrays.fill(color,-1);// 遍歷所有節(jié)點for(inti0;in;i){if(color[i]-1){if(!bfs(graph,color,i)){returnfalse;}}}returntrue;}/** * BFS著色函數(shù) * * param graph 鄰接表 * param color 顏色數(shù)組 * param start 起始節(jié)點 * return true表示著色成功false表示發(fā)現(xiàn)沖突 */privatebooleanbfs(int[][]graph,int[]color,intstart){QueueIntegerqueuenewLinkedList();queue.offer(start);color[start]0;// 起始節(jié)點著色為0while(!queue.isEmpty()){intnodequeue.poll();intcurrentColorcolor[node];// 遍歷相鄰節(jié)點for(intneighbor:graph[node]){if(color[neighbor]-1){// 未著色著相反顏色color[neighbor]1-currentColor;queue.offer(neighbor);}elseif(color[neighbor]currentColor){// 顏色沖突returnfalse;}}}returntrue;}}方法三并查集classSolution{/** * 使用并查集判斷二分圖 * 核心思想每個節(jié)點u和它的所有鄰居v應該在不同的集合中 * 將u的所有鄰居合并到同一個集合然后檢查u是否與該集合連通 */publicbooleanisBipartite(int[][]graph){intngraph.length;UnionFindufnewUnionFind(n);// 遍歷每個節(jié)點for(intu0;un;u){int[]neighborsgraph[u];if(neighbors.length0)continue;// 將u的所有鄰居合并到同一個集合intfirstNeighborneighbors[0];for(inti1;ineighbors.length;i){uf.union(firstNeighbor,neighbors[i]);}// 檢查u是否與鄰居集合連通如果是則不是二分圖if(uf.isConnected(u,firstNeighbor)){returnfalse;}}returntrue;}/** * 并查集實現(xiàn) */classUnionFind{privateint[]parent;privateint[]rank;publicUnionFind(intn){parentnewint[n];ranknewint[n];for(inti0;in;i){parent[i]i;rank[i]0;}}publicintfind(intx){if(parent[x]!x){parent[x]find(parent[x]);// 路徑壓縮}returnparent[x];}publicvoidunion(intx,inty){introotXfind(x);introotYfind(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/BFSO(V E)V是節(jié)點數(shù)E是邊數(shù)并查集O(E × α(V))α為常數(shù)空間復雜度DFSO(V) - 遞歸?？臻gBFSO(V) - 隊列空間并查集O(V) - parent和rank數(shù)組算法過程1graph [[1,3],[0,2],[1,3],[0,2]]二分圖DFS過程從節(jié)點0開始著色為0節(jié)點1和3著色為1從節(jié)點1節(jié)點2著色為0從節(jié)點3檢查節(jié)點2已著色為0與節(jié)點3的1不同所有節(jié)點著色成功返回true著色結果組0{0, 2}組1{1, 3}2graph [[1,2,3],[0,2],[0,1,3],[0,2]]非二分圖DFS過程從節(jié)點0開始著色為0節(jié)點1、2、3著色為1從節(jié)點1檢查節(jié)點2已著色為1與節(jié)點1相同發(fā)現(xiàn)沖突返回false沖突原因存在三角形環(huán)0-1-2-0奇數(shù)長度環(huán)測試用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 測試用例1標準二分圖int[][]graph1{{1,3},{0,2},{1,3},{0,2}};System.out.println(Test 1: solution.isBipartite(graph1));// true// 測試用例2非二分圖奇環(huán)int[][]graph2{{1,2,3},{0,2},{0,1,3},{0,2}};System.out.println(Test 2: solution.isBipartite(graph2));// false// 測試用例3單個節(jié)點int[][]graph3{{}};System.out.println(Test 3: solution.isBipartite(graph3));// true// 測試用例4兩個節(jié)點一條邊int[][]graph4{{1},{0}};System.out.println(Test 4: solution.isBipartite(graph4));// true// 測試用例5三個節(jié)點形成三角形int[][]graph5{{1,2},{0,2},{0,1}};System.out.println(Test 5: solution.isBipartite(graph5));// false// 測試用例6四個節(jié)點形成正方形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不連通圖包含奇環(huán)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}關鍵點二分圖節(jié)點可分為兩個互斥集合每條邊的兩個端點屬于不同集合著色策略使用兩種顏色0和1相鄰節(jié)點必須顏色不同顏色數(shù)組初始值為-1表示未訪問連通分量圖可能不連通需要遍歷所有節(jié)點每個連通分量都要是二分圖沖突檢測發(fā)現(xiàn)相鄰節(jié)點同色立即返回false不需要繼續(xù)處理其他部分圖鄰接表形式graph[u]包含u的所有鄰居無向圖如果u在graph[v]中則v也在graph[u]中常見問題為什么奇數(shù)長度的環(huán)會導致不是二分圖奇環(huán)中從任意節(jié)點開始著色最終會回到起始節(jié)點且顏色沖突偶環(huán)可以成功著色奇環(huán)不行并查集每個節(jié)點u的鄰居應該在同一集合中u本身不應該與該集合連通如果連通說明存在奇環(huán)