Vérifier qu'un graphe est biparti

On effectue un BFS en coloriant le sommet de départ en $0$, puis chaque voisin avec la couleur opposée à la sienne. Si l'on découvre une arête entre deux sommets de même couleur, le graphe n'est pas biparti.

from collections import deque

def est_biparti(G):
    couleur = {}
    for depart in G:
        if depart in couleur:
            continue
        couleur[depart] = 0
        file = deque([depart])
        while file:
            u = file.popleft()
            for v in G[u]:
                if v not in couleur:
                    couleur[v] = 1 - couleur[u]
                    file.append(v)
                elif couleur[v] == couleur[u]:
                    return False
    return True

print(est_biparti({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}))  # True
print(est_biparti({0: [1, 2], 1: [0, 2], 2: [0, 1]}))             # False

La complexité est $O(n+m)$.