Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

2색 알고리즘으로 그래프가 이분 그래프인지 확인하는 C++ 프로그램

이분 그래프란?

이분 그래프(bipartite graph)는 그래프의 모든 정점을 두 가지 색으로 색칠할 수 있는 그래프를 의미합니다. 좀 더 엄밀히 말하면, 정점 집합을 서로 겹치지 않는 두 집합으로 나누었을 때 모든 간선이 두 집합 사이에만 존재하고 같은 집합 내부에는 간선이 없는 그래프입니다. 즉, 인접한 정점끼리는 항상 다른 색을 갖게 됩니다.

이 글에서는 2색 알고리즘과 백트래킹(backtracking) 기법을 활용하여 주어진 그래프가 이분 그래프인지 아닌지를 판별하는 C++ 프로그램을 소개합니다.

함수 구성 및 의사 코드

알고리즘은 세 가지 구성 요소로 이루어집니다.

  • isSafe() : 현재 정점 v에 특정 색을 할당해도 되는지, 즉 해당 색이 이미 인접 정점에서 사용 중인지 검사합니다.
  • graphColoringUtil() : 백트래킹을 통해 정점 하나씩 색을 할당하며, 해를 찾지 못하면 이전 선택을 되돌립니다.
  • graphColoring() : 색 배열을 초기화하고 탐색을 시작하는 진입점 역할을 합니다.

의사 코드

Begin
    1. isSafe() 함수를 작성하여 현재 색 배치가 정점 v에게 안전한지 확인한다.
       즉, 간선이 존재하는지 검사하고, 간선이 있다면 새 정점에 채우려는
       색이 이미 인접 정점에서 사용 중인지 확인한다.
    2. 함수 graphColoringUtil(bool g[V][V], int k, int col[], int v):
         g[V][V] : 그래프의 정점 개수가 V인 2차원 배열
         k       : 사용할 수 있는 최대 색상 수
         col[]   : 1부터 m까지의 숫자를 저장해야 하는 색상 배열
       if v == V
           return true
       for c = 1 to k
           if (isSafe(v, g, col, c))
               col[v] = c
               if (graphColoringUtil(g, k, col, v + 1) == true)
                   return true
               col[v] = 0
       return false
    3. 함수 graphColoring(bool g[V][V], int k):
       for i = 0 to V-1
           color[i] = 0
       if (graphColoringUtil(g, k, color, 0) == false)
           return false
       return true

C++ 전체 예제 코드

아래 예제는 4개의 정점을 가진 그래프를 2색으로 색칠하여 이분 그래프 여부를 확인합니다.

#include <iostream>
#include <cstdio>
#define V 4
using namespace std;

// m 색 문제: 정점 v에 색 c를 할당해도 되는지 검사
bool isSafe(int v, bool g[V][V], int col[], int c)
{
    for (int i = 0; i < V; i++)
        if (g[v][i] && c == col[i])
            return false;   // 인접 정점이 이미 같은 색을 사용 중이면 실패
    return true;
}

// 백트래킹으로 정점 v부터 차례대로 색칠을 시도
bool graphColoringUtil(bool g[V][V], int k, int col[], int v)
{
    if (v == V)             // 모든 정점에 색이 할당되면 성공
        return true;
    for (int c = 1; c <= k; c++)   // 정점 v에 여러 색을 하나씩 시도
    {
        if (isSafe(v, g, col, c))  // 색 c의 할당이 유효한지 검사
        {
            col[v] = c;
            if (graphColoringUtil(g, k, col, v + 1))  // 나머지 정점에 대한 재귀 호출
                return true;
            col[v] = 0;     // 색 c로는 해를 찾지 못하므로 되돌림(백트래킹)
        }
    }
    return false;
}

// 색 배열 초기화 후 탐색 시작
bool graphColoring(bool g[V][V], int k)
{
    int col[V];
    for (int i = 0; i < V; i++)
        col[i] = 0;
    if (graphColoringUtil(g, k, col, 0) == false)
        return false;
    return true;
}

int main()
{
    // 4개의 정점을 가진 예제 그래프 (인접 행렬)
    bool g[V][V] = {
        { 0, 1, 0, 1 },
        { 1, 0, 1, 0 },
        { 0, 1, 0, 1 },
        { 1, 0, 1, 0 }
    };
    int k = 2;   // 사용 가능한 색의 수: 2색

    if (graphColoring(g, k))
        cout << "그래프는 이분 그래프입니다." << endl;
    else
        cout << "그래프는 이분 그래프가 아닙니다." << endl;

    return 0;
}

실행 결과

그래프는 이분 그래프입니다.

동작 원리 정리

  1. 모든 정점의 색을 0(미할당 상태)으로 초기화합니다.
  2. 첫 번째 정점부터 순서대로 1번부터 k번까지의 색을 하나씩 대입해 봅니다.
  3. isSafe() 검사를 통과하면 해당 색을 할당하고 다음 정점으로 재귀 호출을 진행합니다.
  4. 이후 정점들에서 어떤 색으로도 진행할 수 없게 되면 직전 정점의 색을 0으로 되돌리고(백트래킹) 다른 색을 시도합니다.
  5. 모든 정점에 성공적으로 색이 할당되면 이 그래프는 2색으로 색칠 가능하므로 이분 그래프입니다.

복잡도 및 참고 사항

이 백트래킹 알고리즘은 최악의 경우 각 정점마다 k개의 색을 모두 시도해야 하므로 지수형 시간 복잡도를 가집니다. 한편, 단순히 이분 그래프 여부만 판별하는 것이 목적이라면 BFS나 DFS로 그래프를 탐색하면서 인접 정점에 반대 색을 칠하는 방법을 사용하면 O(V + E) 시간에 판별할 수 있습니다.