check bipartite graph bfs Algorithm
The check bipartite graph BFS (Breadth-First Search) algorithm is a graph traversal technique used to determine if a given graph is bipartite or not. A bipartite graph is a graph in which the vertex set can be divided into two disjoint sets, U and V, such that every edge in the graph connects a vertex in set U to a vertex in set V. In other words, a graph is bipartite if its vertices can be colored with two colors in such a way that no two adjacent vertices have the same color. The algorithm uses the breadth-first search approach to traverse the graph and assign colors to the vertices while ensuring no two adjacent vertices have the same color.
The check bipartite graph BFS algorithm starts with an arbitrary vertex and assigns it a color, say red. It then visits all the neighboring vertices of the starting vertex and assigns them the opposite color, in this case, blue. The algorithm continues this process, traversing the graph in a breadth-first manner, visiting all vertices and assigning colors alternately. If at any point, the algorithm encounters a vertex that has already been visited and has the same color as the current vertex, it concludes that the graph is not bipartite. Otherwise, if all vertices are visited and the coloring constraints are satisfied, the graph is considered bipartite.
# Check whether Graph is Bipartite or Not using BFS
# A Bipartite Graph is a graph whose vertices can be divided into two independent sets,
# U and V such that every edge (u, v) either connects a vertex from U to V or a vertex
# from V to U. In other words, for every edge (u, v), either u belongs to U and v to V,
# or u belongs to V and v to U. We can also say that there is no edge that connects
# vertices of same set.
def checkBipartite(graph):
queue = []
visited = [False] * len(graph)
color = [-1] * len(graph)
def bfs():
while queue:
u = queue.pop(0)
visited[u] = True
for neighbour in graph[u]:
if neighbour == u:
return False
if color[neighbour] == -1:
color[neighbour] = 1 - color[u]
queue.append(neighbour)
elif color[neighbour] == color[u]:
return False
return True
for i in range(len(graph)):
if not visited[i]:
queue.append(i)
color[i] = 0
if bfs() is False:
return False
return True
if __name__ == "__main__":
# Adjacency List of graph
print(checkBipartite({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}))
