Bipartite Graph Concept & Pattern

🧠 Concept

Problem Domain

Two-color problem. DFS every vertex.

• A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

• Undirected graph

• 

• Real life scenario

  • Movies to actors

  • 生活中不少实体的关系都能自然地形成二分图结构，所以在某些场景下图结构也可以作为存储键值对的数据结构