This is a Python program to find if an undirected graph is bipartite using BFS.

The program creates a graph object and allows the user to determine whether the graph is bipartite.

1. Create classes for Graph, Vertex and Queue.

2. Create a function is_bipartite that takes a Vertex object v and a set visited as arguments.

3. The function works by painting each vertex a colour opposite to the colour of its neighbours. If it is found not possible to do so, the graph is not bipartite.

4. The function begins by creating an empty set called visited and a Queue object, q.

5. It also creates a dictionary colour which maps each vertex to either 1 or 0 which represent two different colours. The Vertex object passed is mapped to 0.

6. It enqueues the passed Vertex object and also adds it to the set visited.

7. A while loop is created which runs as long as the queue is not empty.

8. In each iteration of the loop, the queue is dequeued and all of its neighbours are enqueued which have not already been visited.

9. In addition to enqueuing, they are also added to the set visited and the colour of each neighbour is set to the colour opposite to the colour of the dequeued element.

10. If a neighbour is found to be already visited and its colour is the same as that of the dequeued element, the graph is not bipartite and False is returned.

11. After the loop is finished, True is returned to indicate that the graph is bipartite.

12. Thus, the function returns True if the connected component containing v is bipartite. It also puts all nodes reachable from the source vertex in the set visited.

Here is the source code of a Python program to find if an undirected graph is bipartite using BFS. The program output is shown below.

class Graph: def __init__(self): # dictionary containing keys that map to the corresponding vertex object self.vertices = {} def add_vertex(self, key): """Add a vertex with the given key to the graph.""" vertex = Vertex(key) self.vertices[key] = vertex def get_vertex(self, key): """Return vertex object with the corresponding key.""" return self.vertices[key] def __contains__(self, key): return key in self.vertices def add_edge(self, src_key, dest_key, weight=1): """Add edge from src_key to dest_key with given weight.""" self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight) def add_undirected_edge(self, v1_key, v2_key, weight=1): """Add undirected edge (2 directed edges) between v1_key and v2_key with given weight.""" self.add_edge(v1_key, v2_key, weight) self.add_edge(v2_key, v1_key, weight) def does_undirected_edge_exist(self, v1_key, v2_key): """Return True if there is an undirected edge between v1_key and v2_key.""" return (self.does_edge_exist(v1_key, v2_key) and self.does_edge_exist(v1_key, v2_key)) def does_edge_exist(self, src_key, dest_key): """Return True if there is an edge from src_key to dest_key.""" return self.vertices[src_key].does_it_point_to(self.vertices[dest_key]) def __iter__(self): return iter(self.vertices.values()) class Vertex: def __init__(self, key): self.key = key self.points_to = {} def get_key(self): """Return key corresponding to this vertex object.""" return self.key def add_neighbour(self, dest, weight): """Make this vertex point to dest with given edge weight.""" self.points_to[dest] = weight def get_neighbours(self): """Return all vertices pointed to by this vertex.""" return self.points_to.keys() def get_weight(self, dest): """Get weight of edge from this vertex to dest.""" return self.points_to[dest] def does_it_point_to(self, dest): """Return True if this vertex points to dest.""" return dest in self.points_to class Queue: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def enqueue(self, data): self.items.append(data) def dequeue(self): return self.items.pop(0) def is_bipartite(vertex, visited): """Return True if component containing vertex is bipartite and put all vertices in its component in set visited.""" colour = {vertex: 0} visited.add(vertex) q = Queue() q.enqueue(vertex) while not q.is_empty(): current = q.dequeue() next_colour = 1 - colour[current] # switch colour for dest in current.get_neighbours(): if dest not in visited: visited.add(dest) colour[dest] = next_colour q.enqueue(dest) else: if colour[dest] != next_colour: return False return True g = Graph() print('Undirected Graph') print('Menu') print('add vertex <key>') print('add edge <vertex1> <vertex2>') print('bipartite') print('display') print('quit') while True: do = input('What would you like to do? ').split() operation = do[0] if operation == 'add': suboperation = do[1] if suboperation == 'vertex': key = int(do[2]) if key not in g: g.add_vertex(key) else: print('Vertex already exists.') elif suboperation == 'edge': v1 = int(do[2]) v2 = int(do[3]) if v1 not in g: print('Vertex {} does not exist.'.format(v1)) elif v2 not in g: print('Vertex {} does not exist.'.format(v2)) else: if not g.does_undirected_edge_exist(v1, v2): g.add_undirected_edge(v1, v2) else: print('Edge already exists.') elif operation == 'bipartite': bipartite = True visited = set() for v in g: if v not in visited: if not is_bipartite(v, visited): bipartite = False break if bipartite: print('Graph is bipartite.') else: print('Graph is not bipartite.') elif operation == 'display': print('Vertices: ', end='') for v in g: print(v.get_key(), end=' ') print() print('Edges: ') for v in g: for dest in v.get_neighbours(): w = v.get_weight(dest) print('(src={}, dest={}, weight={}) '.format(v.get_key(), dest.get_key(), w)) print() elif operation == 'quit': break

1. An instance of Graph is created.

2. A menu is presented to the user to perform various operations on the graph.

3. To determine whether the graph is bipartite, is_bipartite is called with a vertex from the graph and an empty set visited.

4. If is_bipartite returns True, the graph is not bipartite. Otherwise, if not all vertices were visited, is_bipartite is called again with an unvisited source vertex.

5. This continues until all vertices have been visited or is_bipartite returns False.

6. If all vertices have been visited, the graph is bipartite.

Case 1: Undirected Graph Menu add vertex <key> add edge <vertex1> <vertex2> bipartite display quit What would you like to do? add vertex 1 What would you like to do? add vertex 2 What would you like to do? add vertex 3 What would you like to do? add vertex 4 What would you like to do? add vertex 5 What would you like to do? add vertex 6 What would you like to do? add vertex 7 What would you like to do? add edge 1 2 What would you like to do? add edge 2 3 What would you like to do? add edge 3 4 What would you like to do? add edge 5 6 What would you like to do? add edge 6 7 What would you like to do? bipartite Graph is bipartite. What would you like to do? add edge 7 1 What would you like to do? bipartite Graph is bipartite. What would you like to do? add edge 6 1 What would you like to do? bipartite Graph is not bipartite. What would you like to do? quit Case 2: Undirected Graph Menu add vertex <key> add edge <vertex1> <vertex2> bipartite display quit What would you like to do? add vertex 1 What would you like to do? add vertex 2 What would you like to do? add vertex 3 What would you like to do? add vertex 4 What would you like to do? bipartite Graph is bipartite. What would you like to do? add edge 1 2 What would you like to do? bipartite Graph is bipartite. What would you like to do? add edge 3 4 What would you like to do? bipartite Graph is bipartite. What would you like to do? add edge 1 4 What would you like to do? bipartite Graph is bipartite. What would you like to do? add edge 2 4 What would you like to do? bipartite Graph is not bipartite. What would you like to do? quit

**Sanfoundry Global Education & Learning Series – Python Programs.**

To practice all Python programs, __here is complete set of 150+ Python Problems and Solutions__.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Check Information Technology Books
- Practice Programming MCQs
- Apply for Programming Internship
- Check Python Books
- Apply for Python Internship