Python Program to Check if Undirected Graph is Bipartite using DFS

«
»

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

Problem Description

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

Problem Solution

1. Create classes for Graph and Vertex.
2. Create a function is_bipartite_helper that takes a Vertex object v, a set visited and a dictionary colour 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 adding v to visited.
5. For each neighbour of v that has not been visited, its colour is set to the colour opposite of v’s colour and is_bipartite_helper on the neighbour is called to see whether it returns False. If so, the graph is not bipartite and False is returned.
6. If a neghbour has already been visited, then it is checked to see whether the colour of the neighbour is opposite to the colour of v. If not, False is returned.
7. After the loop is finished, True is returned to indicate that the graph is bipartite.
8. Create a function is_bipartite that takes a Vertex object v and an empty set visited as arguments.
9. It creates a dictionary colour with v mapped to 0. The values 0 and 1 are used to represent the two different colours.
10. It calls is_bipartite_helper with v, the set visited and the dictionary colour. Its returned value is the return value of this function.
11. Thus, this function returns True if the connected component containing v is bipartite and puts all vertices reachable from v in the set visited.

Program/Source Code

Here is the source code of a Python program to find if an undirected graph is bipartite using DFS. 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
 
 
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}
    return is_bipartite_helper(vertex, visited, colour)
 
 
def is_bipartite_helper(v, visited, colour):
    """Return True if component containing vertex is bipartite and put all
    vertices in its component in set visited. Uses dictionary colour to keep
    track of colour of each vertex."""
    visited.add(v)
    next_colour = 1 - colour[v] # switch colour
    for dest in v.get_neighbours():
        if dest not in visited:
            colour[dest] = next_colour
            if not is_bipartite_helper(dest, visited, colour):
                return False
        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
Program Explanation

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
Runtime Test Cases
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 edge 1 2
What would you like to do? bipartite
Graph is bipartite.
What would you like to do? add edge 3 2
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
 
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? add vertex 5
What would you like to do? add vertex 6
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? bipartite
Graph is bipartite.
What would you like to do? add edge 5 1
What would you like to do? add edge 6 4
What would you like to do? bipartite
Graph is bipartite.
What would you like to do? add edge 6 5
What would you like to do? bipartite
Graph is bipartite.
What would you like to do? add edge 6 2
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

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.