Graph coloring problem
unknown
plain_text
2 years ago
1.3 kB
17
Indexable
#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;
}
Editor is loading...