What is Bipartite Graph? How to detect one?

Technology CommunityCategory: Data StructuresWhat is Bipartite Graph? How to detect one?
VietMX Staff asked 3 years ago

A graph is bipartite when the graph vertices are parted into two disjoint sets; no two adjacent vertices would reside in the same set. A bipartite graph must not contain odd cycle (a cycle with an odd number of vertices).

bipartite-graph

 

  • BFS (Breadth First Search) can be used in detecting a bipartite graph.
  • Another method of checking a bipartite graph is to check the occurrence of an odd cycle in the graph.