이분 그래프 (Bipartite Graph) 를 간단하게 알아보자.

이분 그래프를 간단하게 설명하면?

모든 정점들을 두 가지 색으로만 칠하되, 인접한 정점끼리는 서로 다른 색을 칠해야 하는 그래프!

 

 

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프.

 

 

1. DFS, BFS로 각각의 정점을 돌아다니며 한 가지 색으로 칠합니다. 
2. 다음 정점으로 방문하면서 인접 정점들은 다른 색으로 칠합니다.
3. 탐색 진행시 자신과 인접 정점이 같은 색이면 이분 그래프가 아닙니다. 

 

이분 그래프 특징

• 그래프의 정점의 집합을 둘로 분할하여 각 집합에 속한 정점끼리는 서로 인접하지 않도록 하는 그래프입니다.
• DFS와 BFS로 구현이 가능합니다.
• BFS의 경우 같은 레벨의 정점들은 모두 같은 색깔을 칠한다고 생각하면 쉽습니다.
• 연결 성분의 개수를 구하는 방법과 유사합니다.

 

구현 과정 

DFS의 경우 main에서 모든 정점을 방문, 탐색 , 결과 도출하였고

BFS의 경우 BFS메소드 내에서 모든 정점을 방문 , 탐색 후 바로 결과를 반환하였다.

 

DFS

import java.util.*;
import java.io.*;

public class Main{
static int v,e;
static int[] visit;
static ArrayList<ArrayList<Integer>> list;

static void dfs(int x, int color) {
	visit[x]= color;
	for(int i=0; i<list.get(x).size(); i++) {
		int temp = list.get(x).get(i);
		
		if(visit[temp]==0) {
			if(visit[x]==1)
				dfs(temp, -1);
			if(visit[x]==-1)
				dfs(temp, 1);
		}
	}
}

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st;
       int k = Integer.parseInt(br.readLine());
       String[] answerArr = new String[k];
       for(int i=0; i<k; i++) {   
    	   st = new StringTokenizer(br.readLine());
    	   v = Integer.parseInt(st.nextToken());
    	   e = Integer.parseInt(st.nextToken());
    	   
    	   list = new ArrayList(v+1);
    	   visit = new int[v+1];
    	   
    	   for(int l=0; l<v+1; l++) {
    		   list.add(new ArrayList<>());
    	   }
    	   for(int j=0; j<e; j++) {
    		   st = new StringTokenizer(br.readLine());
    		   int a = Integer.parseInt(st.nextToken());
    		   int b = Integer.parseInt(st.nextToken());
    		   list.get(a).add(b);
    		   list.get(b).add(a);
    	   }
    	   for(int j=1; j<=v; j++) {  //모든 정점을 dfs. 
    		   if(visit[j]==0) {      //이유: (1,2) (1,3) (4,5) (4,6) (5,6)의 경우 원래 하던 것 처럼 dfs(1)을 하면 4,5,6,은 방문x 
    			   dfs(j, 1);
    		   }
    	   }
    	   for(int n=1; n<=v; n++) {    //모든 정점을 탐색해가며 자신과 인접정점이 같은 색인 경우 false
    		   for(int m=0; m<list.get(n).size(); m++) {
    			   if(visit[n]==visit[list.get(n).get(m)]) {
    				   answerArr[i]="NO";
    				   break;
    			   }
    		   }
    	   }
    	   if(answerArr[i]!="NO")
    		   answerArr[i]="YES";
       }
       for(int i=0; i<k; i++)
    	   System.out.println(answerArr[i]);
    }
    }

 

BFS

import java.util.*;
import java.io.*;

public class Main{
static int v,e;
static int[] visit;
static ArrayList<ArrayList<Integer>> list;

static String bfs() {
	Queue<Integer> q = new LinkedList<>();
	for(int i=1; i<=v; i++) {       //전체를 다 탐색하는 이유: ex) (1,2) (1,3) (4,5) (4,6) 의 경우 평소처럼 1을 시작으로 진행하면 4,5,6 부분은 탐색을 안함.
		if(visit[i]==0) {           // 그래서 YES를 출력함. 
			q.offer(i);
			visit[i] = 1;
		}
	while(!q.isEmpty()) {
		int now = q.poll();
		for(int j=0; j<list.get(now).size(); j++) {
			int news = list.get(now).get(j);
			
			if(visit[now]==visit[news]) {      //현재 정점과 그 하위 정점이 같은 숫자면 false
				return "NO";
			}
			if(visit[news]==0) {
				if(visit[now]==1)
					visit[news]=-1;
				if(visit[now]==-1)
					visit[news]=1;
				
				q.offer(news);
			}
			
		}
	}
	}
	return "YES";
}

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st;
       int k = Integer.parseInt(br.readLine());
       String[] answerArr = new String[k];
       for(int i=0; i<k; i++) {   
    	   st = new StringTokenizer(br.readLine());
    	   v = Integer.parseInt(st.nextToken());
    	   e = Integer.parseInt(st.nextToken());
    	   
    	   list = new ArrayList(v+1);
    	   visit = new int[v+1];
    	   
    	   for(int l=0; l<v+1; l++) {
    		   list.add(new ArrayList<>());
    	   }
    	   for(int j=0; j<e; j++) {
    		   st = new StringTokenizer(br.readLine());
    		   int a = Integer.parseInt(st.nextToken());
    		   int b = Integer.parseInt(st.nextToken());
    		   list.get(a).add(b);
    		   list.get(b).add(a);
    	   }
    	   
    	  answerArr[i]= bfs();;
       }
       for(int i=0; i<k; i++)
    	   System.out.println(answerArr[i]);
    }
    }

 

시간 복잡도

O(V+E)