Part of Microsoft
Engaged Employer
LinkedIn Interview Question
Design a function to determine whether a graph is bipartite.
Interview Answer
Anonymous
Mar 19, 2012
User BFS for same, while traversing through nodes label the first visited node as 0, label its neighbors as 1. if you get a label 1 node, label its unlabelled neighbors as 0. at any point if you get an already labelled neighbor as 0 - 0 ( you get label 0 neighbor from label 0 node) or 1 - 1(respectively) the graph is not bipartite