Today we are going to share a Python program to find out whether a given graph is Bipartite or not. If you are a python beginner and want to start learning the python programming, then keep your close attention in this tutorial as I am going to share a Python program to find out whether a given graph is Bipartite or not.
To increase your Python knowledge, practice all Python programs, here is a collection of 100+ Python problems with solutions.
Copy the below python program and execute it with the help of python compiler.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
class Graph(): def __init__(self, V): self.V = V self.graph = [[0 for column in range(V)] \ for row in range(V)] def isBipartite(self, src): colorArr = [-1] * self.V # Assign first color to source colorArr[src] = 1 queue = [] queue.append(src) while queue: u = queue.pop() # Return false if there is a self-loop if self.graph[u][u] == 1: return False; for v in range(self.V): # An edge from u to v exists and destination if self.graph[u][v] == 1 and colorArr[v] == -1: # Assign alternate color to this # adjacent v of u colorArr[v] = 1 - colorArr[u] queue.append(v) # An edge from u to v exists and destination # v is colored with same color as u elif self.graph[u][v] == 1 and colorArr[v] == colorArr[u]: return False # If we reach here, then all adjacent # vertices can be colored with alternate # color return True g = Graph(4) g.graph = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0] ] print "Yes" if g.isBipartite(0) else "No" |
Yes
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.
