What would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix?

Category: QuestionsWhat would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix?
Editor">Editor Staff asked 4 weeks ago

What would the  time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix?
 
(a) O(E*E)
 
(b) O(V*V)
 
(c) O(E)
 
(d) O(V)
 
The origin of the question is Undirected Graph in portion Graph of Data Structures & Algorithms I
 
I have been asked this question during an interview for a job.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Correct answer is (b) O(V*V)
 
The best I can explain: A graph can be checked for being Bipartite by seeing if it is 2-colorable or not, which can be obtained with the help of BFS.