Implement the bipartiteGraphCheck method that checks whether a graph can be divided into two valid groups.
The input represents an undirected graph with nodes vertices and an edge list edges.
Your task is to check whether the graph is bipartite. A graph is bipartite when its nodes can be divided into two groups so that every edge connects nodes from different groups.
For example, a simple chain such as 0-1-2-3 is bipartite, but a triangle such as 0-1-2-0 is not because it forces two connected nodes into the same group.
Example 1
4[[0,1],[1,2],[2,3]]3trueExample 2
3[[0,1],[1,2],[2,0]]3falseExample 3
2[[0,1]]1trueUse graph coloring with two colors.
Start from each unvisited node and assign it one color. Then visit its neighbours and assign the opposite color. If you ever find an edge where both connected nodes already have the same color, the graph is not bipartite.
This check must be started from every uncolored node because the graph may have more than one connected component.
Pseudocode:
function bipartiteGraphCheck(nodes, edges, size):
graph = create adjacency list
for each edge [u, v] in edges:
add v to graph[u]
add u to graph[v]
color = array filled with -1
for node from 0 to nodes - 1:
if color[node] == -1:
if bfsColor(node) == false:
return false
return true
function bfsColor(start):
queue = empty queue
color[start] = 0
push start into queue
while queue is not empty:
current = remove front from queue
for each nextNode in graph[current]:
if color[nextNode] == -1:
color[nextNode] = 1 - color[current]
push nextNode into queue
else if color[nextNode] == color[current]:
return false
return true