(a) 从图中的某个顶点做深度优先遍历，并将不同层的顶点标记为红黑两种颜色，使得每条树边的两个顶点的颜色都不相同，如果遇到一条回边并且两个顶点的颜色都相同则说明图不是二部图。
(b)如果存在一个长度为奇数的环，则环的顶点的个数和边的条数为奇数，若把环的顶点分成两个集合，至少有一个集合的两个点是相邻的，即无法把点分成两个集合，使得每一个集合中的两个点不存在边相连。一个图为二部图的充要条件是对于每一条树边(u,v)要使u和v的颜色不同，即u和v之间存在偶数条边。
(c)三种颜色
1 package org.xiu68.ch03.ex11; 2 3 public class Ex3_7 { 4 5 //用线性时间证明一个图是否是二部图 6 public static void main(String[] args) { 7 // TODO Auto-generated method stub 8 int[][] graph=new int[][]{ 9 {0,1,0,1}, 10 {1,0,1,0}, 11 {0,1,0,1}, 12 {1,0,1,0} 13 }; 14 MGraph m1=new MGraph(graph); 15 m1.biPartGraph(0); 16 17 18 System.out.println("************************************"); 19 int[][] graph2=new int[][]{ 20 {0,1,1,0,0,0}, 21 {1,0,0,0,0,1}, 22 {1,0,0,1,1,1}, 23 {0,0,1,0,1,0}, 24 {0,0,1,1,0,0}, 25 {0,1,1,0,0,0} 26 }; 27 MGraph m2=new MGraph(graph2); 28 m2.biPartGraph(2); 29 } 30 31 } 32 33 class MGraph{ 34 private int vexNum; //顶点数量 35 private int[][] edges; //边 36 private int[][] visitedEdges; //记录已访问的边 37 private int[] visited; //标记顶点访问状态,-1表示未访问到,0表示正在访问中,1表示已访问 38 private boolean[] color; //表示每个顶点有两种颜色,true和false表示，表示所属的顶点的集合(V1或V2) 39 40 public MGraph(int[][] edges){ 41 this.edges=edges; 42 this.vexNum=edges.length; 43 this.visitedEdges=new int[vexNum][vexNum]; 44 this.visited=new int[vexNum]; 45 for(int i=0;i<vexNum;i++){ 46 visited[i]=-1; 47 } 48 49 this.color=new boolean[vexNum]; 50 } 51 public void biPartGraph(int v){ 52 color[v]=true; 53 boolean result=dfs(v); 54 if(result) 55 System.out.println("二部图"); 56 else 57 System.out.println("非二部图"); 58 } 59 public boolean dfs(int v){ 60 visited[v]=0; 61 for(int i=0;i<vexNum;i++){ 62 if(edges[v][i]==1 && visitedEdges[v][i]!=1){ //两个顶点存在边未被访问过 63 64 visitedEdges[v][i]=visitedEdges[i][v]=1; //标记边已访问 65 66 if(visited[i]==0){ //访问到访问状态为0的顶点 67 if(color[v]==color[i]) //两个顶点颜色相同 68 return false; 69 else //两个顶点颜色不同 70 color[i]=!color[v]; 71 }else if(visited[i]==-1){ //访问到访问状态为-1的顶点 72 color[i]=!color[v]; 73 if(!dfs(i)) 74 return false; 75 } 76 }//if 77 }//for 78 visited[v]=1; 79 return true; 80 } 81 }