bipartite graphs using coloring technique python implementation with BFS

bipartite_graph.py

from typing import List


# This is an undirected graph.
# _graph[u] = list of all elements parallel to u (e.g. _graph[u] = [v])
# Also _graph[v] = [u] Since undirected graph the opposite edge is also present

def isBipartite(_graph: List[List[int]]) -> bool:
    # we are already given the adjacency matrix, so we can start BFS

    # Maintains visited + color
    # Our Colors --> True and False
    color = dict()
    current_color = False

    for node in range(len(_graph)):
        if color.get(node) is not None:
            # The node has already been visited.
            continue

        bucket_list = [node]

        while bucket_list:
            next_year_list = []
            current_color = not current_color  # Toggle colors for each level in BFS

            for visiting_node in bucket_list:
                print("Visiting : ", visiting_node)
                color[visiting_node] = current_color  # Color it

                for adjacent_node in _graph[visiting_node]:
                    adjacent_node_color = color.get(adjacent_node)

                    # Node is uncolored.
                    if adjacent_node_color is None:
                        next_year_list.append(adjacent_node)
                        continue
                    else:
                        if adjacent_node_color == current_color:
                            print(color)
                            # Graph is not bipartite since adjacent nodes have same color
                            return False

            bucket_list = next_year_list
    return True


if __name__ == '__main__':
    adj_matrix = [[3, 4, 6], [3, 6], [3, 6], [0, 1, 2, 5], [0, 7, 8], [3], [0, 1, 2, 7], [4, 6], [4], []]
    answer = isBipartite((adj_matrix))
    print(answer)