Graph coloring problem
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; }