Bipartite checking using Graph Colouring and Breadth First Search (BFS)

A Bipartite Graph is one whose vertices can be divided into disjoint and independent sets, say U and V, such that every edge has one vertex in U and the other in V. The algorithm to determine whether a graph is bipartite or not uses the concept of graph colouring and BFS and finds it in O(V+E) time complexity on using an adjacency list and O(V^2) on using adjacency matrix.

Read this article to understand Bipartite checking using Graph Colouring and Breadth First Search (BFS) in depth

Have a doubt or thought? Join the discussion now


This is a companion discussion topic for the original entry at http://iq.opengenus.org/bipartite-checking-bfs/