Graph coloring problem

mail@pastecode.io avatarunknown
plain_text
12 days ago
1.3 kB
1
Indexable
Never
#include <iostream>
#include <vector>
#include <unordered_set>
#include <map>

using namespace std;

void addEdge(vector<vector<int>> &graph, int u, int v)
{
    graph[u].push_back(v);
    graph[v].push_back(u);
}
map<int, int> greedyGraphColoring(vector<vector<int>> &graph)
{
    map<int, int> colorMap;
    unordered_set<int> availableColors; 

    int V = graph.size(); 

    for (int v = 0; v < V; ++v)
    {
        availableColors.clear();

        for (int adj : graph[v])
        {
            if (colorMap.find(adj) != colorMap.end())
            {
                availableColors.insert(colorMap[adj]);
            }
        }

        int color = 0;
        while (availableColors.find(color) != availableColors.end())
        {
            color++;
        }

        colorMap[v] = color;
    }

    return colorMap;
}

int main()
{
    int V = 6;
    vector<vector<int>> graph(V);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 5);

    map<int, int> colorMap = greedyGraphColoring(graph);

    for (auto it = colorMap.begin(); it != colorMap.end(); ++it)
    {
        cout << "Vertex " << it->first << " is colored with color " << it->second << endl;
    }

    return 0;
}