👀 Views: 31 💬 Answers: 1 📅 Created: 2025-06-12

algorithm graph-theory cpp C++

I've been working on this all day and I'm testing a new approach and This might be a silly question, but I am working on implementing a graph coloring algorithm to determine if a bipartite graph can be colored using two colors... However, I am encountering unexpected output when testing with specific input cases. For instance, my function is returning false for a valid bipartite graph, and I suspect the issue may stem from how I'm traversing the graph. Here is a simplified version of my code: ```cpp #include <iostream> #include <vector> #include <queue> bool isBipartiteUtil(int src, std::vector<int>& color, const std::vector<std::vector<int>>& graph) { std::queue<int> q; q.push(src); color[src] = 1; // Start coloring with color 1 while (!q.empty()) { int u = q.front(); q.pop(); for (int v : graph[u]) { if (color[v] == -1) { // Assign alternate color to this adjacent vertex color[v] = 1 - color[u]; q.push(v); } else if (color[v] == color[u]) { return false; // A conflict in colors } } } return true; } bool isBipartite(const std::vector<std::vector<int>>& graph) { int V = graph.size(); std::vector<int> color(V, -1); // Initialize colors as -1 for (int i = 0; i < V; i++) { if (color[i] == -1) { if (!isBipartiteUtil(i, color, graph)) { return false; } } } return true; } int main() { std::vector<std::vector<int>> graph = { {1, 3}, {0, 2}, {1, 3}, {0, 2} }; if (isBipartite(graph)) { std::cout << "Graph is Bipartite" << std::endl; } else { std::cout << "Graph is NOT Bipartite" << std::endl; } return 0; } ``` I have tested my implementation with various bipartite graphs, but it fails on the following case: ```cpp std::vector<std::vector<int>> graph = { {1, 2}, {0, 3}, {0, 3}, {1, 2} }; ``` For this input, it outputs that the graph is not bipartite, but it clearly is. I've checked my queue management, and it seems fine. I've also confirmed that the adjacency list is constructed correctly. I'm using C++14, and I would appreciate any insights on what I might be missing or doing incorrectly, especially regarding my color assignment logic. Any help would be greatly appreciated!