Interview Question

Software Engineer Interview

-New Haven, CT

Google

Given a graph as input, write a java method returning boolean true if the graph is bipartitie, else false.

AnswerAdd Tags

Interview Answer

1 Answer

0

iterate through all vertices, coloring each vertex one color, all of its neighbors an alternate color, and all the neighbors of those neighbors the initial color. upon completion, re-iterate through the graph and return false if any vertex has a neighbor of the same color. if re-iteration goes to completion, return true.

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.