이분 그래프 판별하는 알고리즘 분석

1. 문제

 

그래프의 정점의 집합을 둘로 분할하는데 각 집합에 속하는 정점끼리는 서로 간선이 존재하지 않도록 분할하고 싶다.

 

이것이 가능한지를 판별하는 프로그램을 작성해본다면?

 

 

2. DFS 알고리즘

 

무방향 그래프라고 가정함

 

어떤 정점을 방문하면서 방문한 정점에 그룹 1을 할당

 

인접한 정점을 순회하면서, 인접한 정점이 방문하지 않은 정점이면 그룹 -1을 할당하고 방문

 

하지만 인접한 정점이 이미 방문한 정점이라면, 현재 정점의 그룹(현재 그룹이 할당됨)과 이미 방문한 정점(이미 그룹이 할당됨)이 서로 같은 그룹이면 이분 그래프가 아니다

 

 

3. 예를 들어서 생각해보기

 

다음과 같은 그래프가 이분 그래프인지 생각해보자

 

 

임의의 정점 아무거나 하나를 선택하고 방문을 시도

 

방문하면서 파란색을 부여한다

 

 

 

 

현재 방문한 정점과 인접한 정점을 찾아 방문했는지 안했는지 검사

 

 

위 동그라미 부분은 인접한 정점인데 방문하지 않았으므로 방문을 시도

 

이미 방문한 정점과 다른 색을 부여해야한다. 현재 파란색을 부여했으니 인접한 정점은 빨간색을 부여

 

 

 

다음 다시 인접한 정점을 순회하는데, 이제는 인접한 정점이 2가지가 있다

 

 

 

왼쪽에 파란색으로 칠해진 정점은 이미 방문한 정점인데 이미 방문한 정점의 색(파란색)과 현재 정점(빨간색)을 비교하고

 

서로 다르기 때문에 아직 이분 그래프 가능성이 있다

 

색이 칠해지지 않은 정점은 방문하지 않은 정점이므로 방문을 시도

 

현재 사용한 빨간색과는 다른색을 사용

 

 

 

다시 인접한 정점을 순회하는데 이번에는 3가지가 있다

 

방문하지 않은 정점 2가지는 파란색과는 다른 색을 부여하면서 색을 부여함

 

이미 방문한 정점은 색을 서로 비교. 빨간색과 파란색으로 서로 다르므로 이분 그래프 가능성이 있다

 

 

 

위와 같은 방식으로 계속해서 탐색해본다면...?

 

 

DFS로 여기까지 왔을때, 더 이상 방문할 정점은 없는데, 인접한 정점을 순회하면서 이미 방문한 정점들과 색을 비교하는데

 

현재 서로 다른 색이므로 이분 그래프 가능성이 있다

 

DFS로 끝까지 왔으니까 뒤로 돌아가면서 방문하지 않은 정점을 다시 찾아가야함

 

 

 

 

모든 정점을 탐색하면서 단 1번도 인접한 정점이 서로 같은 색이 아니었으므로 이 그래프는 이분 그래프로 나눌 수 있다

 

하지만 위 그래프는 임의의 하나의 정점에서 시작해서 모든 정점을 방문할 수 있는 연결 그래프이다

 

연결 그래프 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

연결 그래프 - 위키백과, 우리 모두의 백과사전

 

그렇기 때문에 임의의 어떤 정점 단 하나에서만 스타트하더라도 단 1번에 이분 그래프인지 아닌지를 판별할 수 있었다

 

하지만 비연결 그래프라면? 

 

어딘가에서 스타트하면 어딘가에서 끊기겠지

 

 

 

 

위 그래프를 생각해보자

 

아무데서나 일단 시작을 할거야

 

 

 

 

 

위 점에서 시작을 한다고 해보자. DFS로 계속 탐색을 진행하면서 인접한 정점이 방문한 정점이면 서로 다른 색인지 비교하고

 

방문하지 않은 정점이면 다른 색을 부여하면서 방문을 수행

 

 

아직은 이분 그래프 가능성이 있으니까 계속 탐색

 

 

 

여전히 가능성이 있으니까 계속 탐색 수행

 

 

 

근데 여기까지 오니까... 더 이상 인접한 정점 중에서는 방문할 정점이 존재하지 않아

 

그러면 다음 방문이 끊기겠지

 

그러므로 처음 시작에 비연결 그래프에서는 모든 정점을 순회하면서 방문했는지, 방문안했는지 조사를 하고

 

방문을 안한 정점이라면 시작 정점으로 삼고 탐색하는 작업을 여러번 수행해줘야한다

 

 

 

방문이 끊겨가지고 다시 방문하지 않은 정점을 찾다가 위와 같은 정점을 하나 찾아가지고 방문을 시작

 

아무 색이나 하나 부여하면 되겠다. 파란색을 부여하고 다음 방문할 정점을 찾는다

 

아직 방문하지 않은 정점이라면 다른 색으로 칠해주고

 

 

그러면 위와 같이 모든 정점을 방문해보니 한번도 인접한 정점이 서로 같은색이 되지 않는다

 

따라서 이분 그래프가 가능하다

 

 

4. DFS 구현 예시

 

위 알고리즘을 그대로 구현해본다

 

#DFS로 이분 그래프를 판별하는 알고리즘

#이분그래프 판별

def dfs(v,group):
    
    visited[v] = group #방문한 정점에 그룹 할당

    for i in graph[v]: #현재 정점과 인접한 정점을 순회하여..
        
        if visited[i] == 0: #방문하지 않은 정점이라면...
            
            if not dfs(i,-group): #서로 다른 그룹을 부여하면서 방문을 시도
                
                return False # 재귀적 호출 결과가 False라면... 이분 그래프가 아니다

        elif visited[i] == visited[v]: #이미 방문한 정점인데, 현재 정점과 그룹이 같다면

            return False #이분 그래프가 아니다

    return True #모든 정점을 순회했더니 이상이 없으면 이분 그래프이다 

#정점의 수와 간선의 수
v,e = map(int,input().split())

#정점이 1~v인 그래프 생성
graph = [[] for _ in range(v+1)]

#방문한 정점을 체크하는 배열
visited = [0]*(v+1)

#간선을 입력받아 그래프 생성

for _ in range(e):
    
    a,b = map(int,input().split())

    graph[a].append(b)
    graph[b].append(a) #무방향 그래프

bipartite = True #이분 그래프 여부

#연결그래프, 비연결그래프를 모두 고려하여
#모든 정점을 순회하면서
for i in range(1,v+1):
    
    #아직 방문한 정점이 아니라면 시작 정점으로 삼는다
    if visited[i] == 0:
        
        bipartite = dfs(i,1)
        
        #이분 그래프가 아니라면, 반복을 종료
        if not bipartite:
            
            break

print(bipartite)
"""
9 11
1 2
2 3
3 4
3 5
4 6
5 6
5 7
7 8
6 8
9 8
5 9
True
"""

 

 

5. BFS 알고리즘

 

DFS와 다를 것은 전혀 없다

 

비연결 그래프와 연결 그래프를 모두 고려해서 정점을 모두 순회하여 방문하지 않은 정점이면 시작점으로 삼고 탐색 스타트

 

시작 정점을 큐에 담고, 방문 처리로 그룹 할당

 

그 후 BFS로 큐가 빌때까지 수행

 

큐에서 정점 하나 빼고 인접한 정점을 순회하여 아직 방문하지 않은 정점이라면... 큐에 모두 담고

 

큐에 담을때마다 방문 처리를 수행한다

 

방문 처리를 수행할때, 현재 뺀 정점 v와는 다른 색을 부여해야한다.. visited에 색이 부여되어 있으니까

 

다른 색으로 visited[w] = -visited[v]로 반대의 색을 부여함

 

하지만 이미 방문했던 정점이라면 현재 정점 v와 다른 색인지 아닌지를 비교 

 

visited[w] 와 visited[v]가 같다면.. 이분 그래프가 아니다 

 

#BFS로 이분 그래프를 판별하는 알고리즘

from collections import deque

def bfs(v,group):
    
    queue = deque([v]) #BFS 큐 생성

    visited[v] = group #방문 처리로 현재 그룹 할당

    while queue:
        
        v = queue.popleft() #탐색 시작

        for w in graph[v]: #인접한 정점을 순회하면서..
            
            if visited[w] == 0: #아직 방문하지 않은 정점이라면...
                
                queue.append(w) #다음 방문을 수행하기 위해 큐에 담고

                visited[w] = -visited[v] #현재 정점과는 다른 색을 부여함
            
            elif visited[w] == visited[v]: #이미 방문한 정점이라면...
                
                return False #이분 그래프가 아니다
    
    return True #False를 return하지 않는다면 현재 점에서는 이분그래프 가능성이 있다

#정점의 수와 간선의 수를 입력받는다

v,e = map(int,input().split())

#정점이 1~v인 그래프를 생성

graph = [[] for _ in range(v+1)]

#방문 여부 체크하는 배열

visited = [0]*(v+1)

#간선을 입력받는다

for _ in range(e):
    
    a,b = map(int,input().split())

    graph[a].append(b)
    graph[b].append(a)


#연결그래프와 비연결그래프를 모두 고려하여 
#모든 정점을 순회하면서 방문하지 않은 정점이라면
#방문을 시작

for i in range(1,v+1):
    
    if visited[i] == 0: #아직 방문하지 않은 정점이라면..
        
        bipartite = bfs(i,1) #bfs 탐색을 시작

        if bipartite == False: #이분 그래프가 아니라면
            
            break #반복 종료

print(bipartite)

"""
9 11
1 2
2 3
3 4
3 5
4 6
5 6
5 7
7 8
6 8
9 8
5 9
True
"""

 

 

07)이분 그래프 판별(Bipartite Graph Distinction) (tistory.com)

07)이분 그래프 판별(Bipartite Graph Distinction)

 

 

[알고리즘] 이분 그래프(bipartite graph) 판별하기 (tistory.com)

[알고리즘] 이분 그래프(bipartite graph) 판별하기

 

 

시험에 나왔는데 손도 못댔다 ㅡㅡ

 

사실 다른 문제에 이미 멘탈이 나가서 포기하고 시도 못한건 안비밀