Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Graph():
- def isBipartite(self, src, V):
- #contruct the graph based on V
- graph = [[0 for column in range(V)] for row in range(V)]
- #construct the color array
- colorArr = [-1] * V
- # Assign the color to source
- colorArr[src] = 1
- # Create a queue of vertex numbers and enqueue source vertex for BFS traversal
- # enqueue source vertex for BFS traversal
- queue = []
- queue.append(0)
- #BFS
- while queue:
- u = queue.pop()
- # Return false if there is a self-loop
- if graph[u][u] == 1:
- return False;
- for v in range(V):
- # An edge from u to v exists and destination v is not colored
- if graph[u][v] == 1 and colorArr[v] == -1:
- # color v in the opposite color of u
- colorArr[v] = 1 - colorArr[u]
- #append the node into the queue
- queue.append(v)
- # An edge from u to v exists and destination v is colored with same color as u
- elif graph[u][v] == 1 and colorArr[v] == colorArr[u]:
- return False
- return True
- if __name__ == "__main__":
- if Graph().isBipartite(0,4):
- print "isBipartite"
- else :
- print "notBipartite"
Add Comment
Please, Sign In to add comment