Sponsored
Sponsored
This approach uses breadth-first search (BFS) to try and color the graph using two colors, validating its bipartiteness. By starting at any unvisited node and attempting to color it with one color, you color all its neighbors with an alternating color. If at any point a neighbor is found to already have the same color, then the graph cannot be bipartite.
The time complexity is O(V + E) where V is the number of vertices and E is the number of edges, as each edge and vertex is visited once in BFS. The space complexity is O(V) due to the storage needed for the color array and the BFS queue.
1function bfsCheck(start, graph, colors) {
2 let queue = [start];
3 colors[start] = 0;
4
5 while (queue.length > 0) {
6 let node = queue.shift();
7
8 for (let neighbor of graph[node]) {
9 if (colors[neighbor] === -1) {
10 colors[neighbor] = 1 - colors[node];
11 queue.push(neighbor);
12 } else if (colors[neighbor] === colors[node]) {
13 return false;
14 }
15 }
16 }
17 return true;
18}
19
20function isBipartite(graph) {
21 let n = graph.length;
22 let colors = Array(n).fill(-1);
23
24 for (let i = 0; i < n; i++) {
25 if (colors[i] === -1) {
26 if (!bfsCheck(i, graph, colors)) {
27 return false;
28 }
29 }
30 }
31 return true;
32}
33
34// Example usage:
35let graph = [[1, 3], [0, 2], [1, 3], [0, 2]];
36console.log(isBipartite(graph));JavaScript employs similar logic with the use of an Array for BFS and two-coloring strategy. The sequence operates via maintaining an evolving queue of nodes to visit, stopping immediately once any node is confirmed to have conflicting adjacent color information.
The depth-first search (DFS) approach is an alternative to BFS for examining bipartiteness. You use DFS recursively to color the graph and check for conflicts. The method still involves checking whether adjacent nodes have opposing colors, iterating through components one by one as needed.
The time complexity is O(V + E), and the space complexity is O(V) due to recursive depth stack space utilization.
1#include <vector>
using namespace std;
bool dfsCheck(int node, int c, vector<vector<int>>& graph, vector<int>& colors) {
colors[node] = c;
for (int neighbor : graph[node]) {
if (colors[neighbor] == -1) {
if (!dfsCheck(neighbor, 1 - c, graph, colors)) return false;
} else if (colors[neighbor] == colors[node]) {
return false;
}
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> colors(n, -1);
for (int i = 0; i < n; ++i) {
if (colors[i] == -1) {
if (!dfsCheck(i, 0, graph, colors)) {
return false;
}
}
}
return true;
}
int main() {
vector<vector<int>> graph = {{1,3}, {0,2}, {1,3}, {0,2}};
cout << (isBipartite(graph) ? "true" : "false") << endl;
return 0;
}This C++ solution utilizes DFS with a recursive function to check bipartiteness. Each node is colored and its neighbors are recursively visited and attempted to be colored oppositely. The backtrack mechanism inherently helps deal with any invalid coloring from base layer conflicts.