[c++] 그래프 컬러링 알고리즘

08 Dec 2023

그래프 컬러링은 그래프 이론의 한 분야로, 각 정점이 서로 다른 색으로 칠해져 있는 그래프에서 모든 정점이 서로 다른 색으로 칠해지도록 하는 문제를 다루는 알고리즘입니다. 이 문제는 주로 지도 색칠 문제나 시간표 작성 등 다양한 분야에서 활용됩니다.

그래프 컬러링 알고리즘의 기본 아이디어

그래프 컬러링 알고리즘은 다음과 같은 순서로 동작합니다.

인접한 정점은 서로 다른 색으로 칠해져야 합니다.
가능한 적은 수의 색을 사용하여 모든 정점을 칠하는 것이 목표입니다.

그래프 컬러링 알고리즘 종류

그래프 컬러링 알고리즘에는 여러 가지 종류가 있지만, 대표적으로 다음과 같은 알고리즘이 있습니다.

1. 그리디 알고리즘

그리디 알고리즘은 각 정점을 순차적으로 방문하면서 가능한 적은 수의 색으로 칠해나가는 방식입니다. 이 때문에 항상 최적의 해를 찾지는 못할 수 있지만, 간단하고 빠른 처리 속도를 가지고 있습니다.

2. 백트래킹 알고리즘

백트래킹 알고리즘은 가능한 모든 경우의 수를 탐색하면서 최적의 해를 찾는 방식입니다. 이 때문에 그리디 알고리즘보다는 시간이 오래 걸릴 수 있지만, 더욱 정확한 결과를 얻을 수 있습니다.

그래프 컬러링 알고리즘의 구현

#include <iostream>
#include <vector>
using namespace std;

// 인접행렬을 이용한 그래프 구현
vector<vector<int>> graph;
vector<int> colors;

// 그래프 컬러링 알고리즘 (그리디 알고리즘)
void graphColoring(int v, int numColors) {
    for (int i = 1; i <= v; ++i) {
        colors[i] = 1; // 모든 정점을 초기에 1번 색으로 칠함
        for (int j = 1; j <= v; ++j) {
            if (graph[i][j] && colors[i] == colors[j]) {
                colors[i]++; // 현재 정점과 이웃한 정점의 색이 같으면 다음 색으로 변경
            }
        }
    }
}

// 그래프 컬러링 알고리즘 (백트래킹 알고리즘)
void graphColoringBacktrack(int v, int numColors, int vertex) {
    if (vertex == v + 1) { // 그래프의 모든 정점을 다 칠했을 때
        for (int i = 1; i <= v; ++i) {
            cout << "Vertex " << i << " is colored with " << colors[i] << " color" << endl;
        }
        return;
    }

    for (int c = 1; c <= numColors; ++c) {
        bool isAvailable = true;
        for (int i = 1; i <= v; ++i) {
            if (graph[vertex][i] && colors[i] == c) {
                isAvailable = false; // 주변 정점의 색과 현재 색이 같으면 칠할 수 없는 색
                break;
            }
        }
        if (isAvailable) {
            colors[vertex] = c;
            graphColoringBacktrack(v, numColors, vertex + 1); // 다음 정점으로 이동
        }
    }
}

결론

그래프 컬러링 알고리즘은 다양한 문제에 유용하게 활용될 수 있는 중요한 알고리즘입니다. 여러 가지 알고리즘을 적절히 선택하여 문제에 적합한 해결책을 찾을 수 있습니다.

더 많은 내용은 다음 링크를 참고해 주세요.

Graph Coloring - GeeksforGeeks