Check if a graph is bipartite using a breadth-first search (BFS). Args: `graph`: Adjacency list representing the graph. Returns: ``True`` if bipartite, ``False`` otherwise. Check if the graph can be divided into two sets of vertices, such that no two vertices
(graph: dict[int, list[int]])
| 82 | |
| 83 | |
| 84 | def is_bipartite_bfs(graph: dict[int, list[int]]) -> bool: |
| 85 | """ |
| 86 | Check if a graph is bipartite using a breadth-first search (BFS). |
| 87 | |
| 88 | Args: |
| 89 | `graph`: Adjacency list representing the graph. |
| 90 | |
| 91 | Returns: |
| 92 | ``True`` if bipartite, ``False`` otherwise. |
| 93 | |
| 94 | Check if the graph can be divided into two sets of vertices, such that no two |
| 95 | vertices within the same set are connected by an edge. |
| 96 | |
| 97 | Examples: |
| 98 | |
| 99 | >>> is_bipartite_bfs({0: [1, 2], 1: [0, 3], 2: [0, 4]}) |
| 100 | True |
| 101 | >>> is_bipartite_bfs({0: [1, 2], 1: [0, 2], 2: [0, 1]}) |
| 102 | False |
| 103 | >>> is_bipartite_bfs({}) |
| 104 | True |
| 105 | >>> is_bipartite_bfs({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}) |
| 106 | True |
| 107 | >>> is_bipartite_bfs({0: [1, 2, 3], 1: [0, 2], 2: [0, 1, 3], 3: [0, 2]}) |
| 108 | False |
| 109 | >>> is_bipartite_bfs({0: [4], 1: [], 2: [4], 3: [4], 4: [0, 2, 3]}) |
| 110 | True |
| 111 | >>> is_bipartite_bfs({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: [0]}) |
| 112 | False |
| 113 | >>> is_bipartite_bfs({7: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: [0]}) |
| 114 | False |
| 115 | |
| 116 | >>> # FIXME: This test should fails with KeyError: 4. |
| 117 | >>> is_bipartite_bfs({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 9: [0]}) |
| 118 | False |
| 119 | >>> is_bipartite_bfs({0: [-1, 3], 1: [0, -2]}) |
| 120 | False |
| 121 | >>> is_bipartite_bfs({-1: [0, 2], 0: [-1, 1], 1: [0, 2], 2: [-1, 1]}) |
| 122 | True |
| 123 | >>> is_bipartite_bfs({0.9: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}) |
| 124 | True |
| 125 | |
| 126 | >>> # FIXME: This test should fails with |
| 127 | >>> # TypeError: list indices must be integers or... |
| 128 | >>> is_bipartite_bfs({0: [1.0, 3.0], 1.0: [0, 2.0], 2.0: [1.0, 3.0], 3.0: [0, 2.0]}) |
| 129 | True |
| 130 | >>> is_bipartite_bfs({"a": [1, 3], "b": [0, 2], "c": [1, 3], "d": [0, 2]}) |
| 131 | True |
| 132 | >>> is_bipartite_bfs({0: ["b", "d"], 1: ["a", "c"], 2: ["b", "d"], 3: ["a", "c"]}) |
| 133 | True |
| 134 | """ |
| 135 | visited: defaultdict[int, int] = defaultdict(lambda: -1) |
| 136 | for node in graph: |
| 137 | if visited[node] == -1: |
| 138 | queue: deque[int] = deque() |
| 139 | queue.append(node) |
| 140 | visited[node] = 0 |
| 141 | while queue: |