Bipartite Graph

Definition of Bipartite Graph data-structure

Let's say you are coloring the graph nodes. You cannot color neighboring nodes with same color. If you can color the entire graph with only two colors, then the graph is defined as Bipartite Graph .

Bipartite Graph data-structure is used to express functions like $X \to Y$.

Bipartite Graph expressing $X \to Y$ function

Checking if it is Bipartite Graph

We can check if the given graph is Bipartite Graph using BFS, DFS graph-search algorithm.

In this post, I will use DFS algorithm.

Following code is solution for Baekjoon:#1707 problem.

I used DFS algorithm to color every nodes in the island. If every node in island is colored, then we move to the next island.

from collections import deque


class Graph:
    def __init__(self, V, E):
        self.V = V
        self.E = E
        self.data = dict()

    def add_edge(self, u, v):
        if u not in self.data:
            self.data[u] = [v]
        else:
            self.data[u].append(v)

        if v not in self.data:
            self.data[v] = [u]
        else:
            self.data[v].append(u)

    def neighbors(self, u):
        if u not in self.data:
            return []
        else:
            return self.data[u]
    
    def is_bipartite(self):
        # check if graph is bipartite using BFS algorithm
        is_visited = dict()


        # set vertex 1 as visited
        # number 0 means colored red
        # number 1 means colored blue

        for v in range(1, self.V+1):
            
            # use DFS to color all the island
            if v not in is_visited:
                next_to_color = deque()
                next_to_color.append((v, True))

                while len(next_to_color) != 0:
                    coloring_node, color = next_to_color.popleft()
                    if coloring_node not in is_visited:
                        is_visited[coloring_node] = color 
                    
                    # case if already colored
                    elif is_visited[coloring_node] == color:
                        continue 
                    else:
                        return False 

                    # add neighbor node of coloring_node to next_to_color 
                    for neighbor in self.neighbors(coloring_node):
                        next_to_color.append((neighbor, not color))
            else:
                pass 

        return True 

def main():
    K = int(input())
    # print(K)

    for _ in range(K):
        V, E = [int(x) for x in input().split()]
        graph = Graph(V, E)

        for _ in range(E):
            u, v = [int(x) for x in input().split()]
            graph.add_edge(u, v)
                       
        
        if graph.is_bipartite():
            print("YES")
        else:
            print("NO")
        


if __name__ == "__main__":
    main()