Guest User

Untitled

a guest
Jan 23rd, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.35 KB | None | 0 0
  1. class Graph():
  2. def isBipartite(self, src, V):
  3.  
  4. #contruct the graph based on V
  5. graph = [[0 for column in range(V)] for row in range(V)]
  6. #construct the color array
  7. colorArr = [-1] * V
  8. # Assign the color to source
  9. colorArr[src] = 1
  10. # Create a queue of vertex numbers and enqueue source vertex for BFS traversal
  11. # enqueue source vertex for BFS traversal
  12. queue = []
  13. queue.append(0)
  14.  
  15. #BFS
  16. while queue:
  17.  
  18. u = queue.pop()
  19. # Return false if there is a self-loop
  20.  
  21. if graph[u][u] == 1:
  22. return False;
  23.  
  24. for v in range(V):
  25. # An edge from u to v exists and destination v is not colored
  26. if graph[u][v] == 1 and colorArr[v] == -1:
  27.  
  28. # color v in the opposite color of u
  29. colorArr[v] = 1 - colorArr[u]
  30. #append the node into the queue
  31. queue.append(v)
  32.  
  33. # An edge from u to v exists and destination v is colored with same color as u
  34. elif graph[u][v] == 1 and colorArr[v] == colorArr[u]:
  35. return False
  36.  
  37. return True
  38.  
  39. if __name__ == "__main__":
  40.  
  41. if Graph().isBipartite(0,4):
  42. print "isBipartite"
  43. else :
  44. print "notBipartite"
Add Comment
Please, Sign In to add comment