Is Graph Bipartite

+10

Ein Graph hat n Knoten, die von 0 bis n-1 nummeriert sind. Jedes Paar [a, b] in edges stellt eine ungerichtete Kante zwischen den Knoten a und b dar. Der Graph kann in mehrere getrennte Teile zerfallen, und einige Knoten haben möglicherweise überhaupt keine Kante.

Ein Graph ist bipartit, wenn du seine Knoten in zwei Gruppen aufteilen kannst, sodass jede Kante einen Knoten aus der einen Gruppe mit einem Knoten aus der anderen verbindet. Gib true zurück, wenn der Graph bipartit ist, andernfalls false.

Funktion

isBipartite(n: integer, edges: integer-2d-array) → boolean

ninteger: die Anzahl der Knoten, nummeriert von 0 bis n-1
edgesinteger-2d-array: die ungerichteten Kanten, jeweils ein Paar [a, b]
Gibt zurückboolean: true, wenn die Knoten in zwei Gruppen aufgeteilt werden können, wobei jede Kante zwischen den Gruppen verläuft, andernfalls false

Einschränkungen

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] mit 0 ≤ a, b ≤ n-1 und a ≠ b
Keine Kante kommt zweimal vor, auch nicht in umgekehrter Richtung.

Beispiele

Eingabe: n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Ausgabe: true
Erklärung: Ordne die Knoten 0 und 2 einer Gruppe und die Knoten 1 und 3 der anderen Gruppe zu. Jede der vier Kanten verbindet die beiden Gruppen.

Eingabe: n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Ausgabe: false
Erklärung: Die Kante [0, 1] lässt sich problemlos aufteilen und Knoten 5 hat keine Kanten, aber die Knoten 2, 3 und 4 bilden ein Dreieck. Ein fehlerhafter Teil reicht aus, damit die Antwort false lautet.

Weiterführende Frage

Wenn der Graph nicht bipartit ist, kannst du als Beweis einen Zyklus ungerader Länge zurückgeben und seine Knoten der Reihe nach auflisten?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Wahl einer Gruppe für einen Knoten legt die Gruppe für den Rest seines zusammenhängenden Teils fest: Ein Nachbar kommt in die andere Gruppe. Färbe jeden Teil mit einer Breitensuche, die zwischen zwei Farben wechselt; der Graph ist genau dann bipartit, wenn keine Kante an beiden Enden dieselbe Farbe hat. Der Graph kann unzusammenhängend sein, daher beginnt jeder ungefärbte Knoten eine neue Suche.

Probiere jede Aufteilung aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Probiere jede Aufteilung aus. Behandle die Gruppe jedes Knotens als ein Bit, sodass die n Bits eine Binärzahl bilden und das Zählen von 0 bis 2^n-1 jede Aufteilung genau einmal durchläuft. Prüfe bei jeder Aufteilung jede Kante und gib true zurück, wenn es eine Aufteilung gibt, bei der jede Kante zwischen den Gruppen verläuft. Mit jedem Knoten verdoppelt sich die Anzahl der Aufteilungen: 20 Knoten ergeben etwa eine Million.

Algorithmus

Ordne für jede Zahl von 0 bis 2^n-1 den Knoten i der Gruppe zu, die durch Bit i angegeben wird.
Wenn jede Kante die beiden Gruppen verbindet, gib true zurück.
Wenn keine Aufteilung funktioniert, gib false zurück.

def isBipartite(n, edges):
    side = [0] * n  # side[x] is 0 or 1: the group of node x in the current split
    while True:
        # Does every edge cross between the two groups?
        if all(side[u] != side[v] for u, v in edges):
            return True
        # Move to the next split, counting in binary over side.
        i = 0
        while i < n and side[i] == 1:
            side[i] = 0
            i += 1
        if i == n:
            return False  # all 2^n splits have been tried
        side[i] = 1

Union-Find auf den Nachbarn jedes Knotens

Idee

In welcher Gruppe auch immer ein Knoten landet, alle seine Nachbarn landen in der anderen, sodass sie sich eine Gruppe teilen. Vereinige für jeden Knoten alle seine Nachbarn zu einer Union-Find-Menge; eine Menge enthält dann Knoten, die auf derselben Seite bleiben müssen. Eine Kante, deren beide Enden in derselben Menge liegen, muss innerhalb einer Gruppe bleiben, also ist der Graph nicht bipartit.

Die Prüfung erkennt jeden Fehler. Bei einem ungeraden Zyklus verbindet das Vereinigen von jeweils zwei Kanten den ersten Knoten mit dem letzten, und die schließende Kante verbindet diese beiden. Ohne einen ungeraden Zyklus verbindet jede Vereinigung zwei Knoten mit einem geraden Abstand, die auf derselben Seite liegen. Der erste Nachbar eines Knotens, sein Anker, bezeichnet die Menge seiner Nachbarn. Daher kannst du die Vereinigungen vornehmen, während die Kanten vorbeiströmen, ganz ohne Adjazenzlisten. Bei Vereinigung nach Größe und Pfadhalbierung benötigen die 2m Vereinigungen und m Prüfungen O(m α(n)).

Algorithmus

Setze parent[x] = x und anchor[x] = -1 für jeden Knoten.
Gib bei jeder Kante [u, v] jedem Endpunkt den anderen als Anker, falls er noch keinen hat.
Füge v mit der Menge von anchor[u] und u mit der Menge von anchor[v] zusammen.
Gib false zurück, wenn eine Kante beide Endpunkte in derselben Menge hat, andernfalls true.

def isBipartite(n, edges):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n
    anchor = [-1] * n  # the first neighbour seen for each node

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    # All neighbours of a node must sit on one side: the side opposite the node.
    for u, v in edges:
        if anchor[u] == -1:
            anchor[u] = v
        if anchor[v] == -1:
            anchor[v] = u
        union(anchor[u], v)  # v joins the other neighbours of u
        union(anchor[v], u)  # u joins the other neighbours of v
    # An edge whose two ends were forced onto one side cannot cross.
    for u, v in edges:
        if find(u) == find(v):
            return False
    return True

Breitensuche-basierte Zweifärbung jedes Teils

Idee

Ein Konflikt ist endgültig. Die erste Farbe in einer Komponente kann frei gewählt werden, und wenn man sie vertauscht, werden die Farben der gesamten Komponente vertauscht; alle anderen Farben werden durch eine Kante vorgegeben. Die Suche färbt Knoten danach, ob ihr Abstand zum Startknoten gerade oder ungerade ist. Zwei benachbarte Knoten haben also nur dann dieselbe Farbe, wenn die Komponente einen Zyklus ungerader Länge hat; dann gibt es keine Aufteilung.

Eine Suche betrachtet nur ihre eigene Komponente. Gehe daher alle Knoten durch und starte von jedem noch ungefärbten Knoten eine neue Suche. Im dritten Beispiel färbt die Suche von Knoten 0 die Knoten 0 und 1. Die Suche von Knoten 2 weist Knoten 2 die Farbe 0 und den Knoten 3 und 4 die Farbe 1 zu und findet dann [3, 4], bei dem beide Endpunkte die Farbe 1 haben: false. Jeder Knoten wird einmal gefärbt und in die Warteschlange aufgenommen, und jeder der 2m Listeneinträge wird einmal verglichen: Zeit- und Speicheraufwand O(n + m).

Algorithmus

Erstelle Adjazenzlisten, in denen jede Kante bei beiden Endpunkten eingetragen ist, und setze jede Farbe auf -1.
Gehe die ungefärbten Knoten der Reihe nach durch, weise ihnen die Farbe 0 zu und füge sie einer Warteschlange hinzu.
Entnimm einen Knoten. Weise jedem ungefärbten Nachbarn die entgegengesetzte Farbe zu und füge ihn der Warteschlange hinzu; hat ein Nachbar dieselbe Farbe, gib false zurück.
Sobald alle Teile eingefärbt sind, gib true zurück.

from collections import deque


def isBipartite(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    color = [-1] * n  # -1: not colored yet, otherwise 0 or 1
    for start in range(n):
        if color[start] != -1:
            continue
        # A new component: its first node can take either color.
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in graph[node]:
                if color[nxt] == -1:
                    # A neighbour must take the other color.
                    color[nxt] = 1 - color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False  # this edge stays inside one group
    return True

Stolperfallen und Grenzfälle

Nur von Knoten 0 aus suchen. Das dritte Beispiel funktioniert bei Knoten 0 und scheitert zwischen den Knoten 2, 3 und 4.
Jede Kante nur einer Liste hinzufügen. Bei den Kanten [1, 0] und [2, 0] erhält Knoten 0 die Farbe 0 und sieht keine Nachbarn; Knoten 1 erhält dann ebenfalls die Farbe 0, und seine Kante zu Knoten 0 sieht wie ein Konflikt aus, obwohl sich der Pfad problemlos aufteilen lässt.
Einen Knoten erst beim Entfernen aus der Warteschlange färben. Ein Knoten kann dann zweimal in die Warteschlange gelangen, und beim zweiten Besuch wird die erste Farbe überschrieben. Färbe ihn, wenn du ihn hinzufügst.
Bipartit mit azyklisch verwechseln. Das Quadrat hat einen Zyklus und ist bipartit; nur ungerade Zyklen verhindern die Aufteilung.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Is Graph Bipartite?

Eine Färbung mittels Breitensuche oder Tiefensuche läuft in O(n + m) für m Kanten: Jeder Knoten wird einmal gefärbt und jede Kante wird von jedem ihrer beiden Endpunkte aus einmal verglichen. Die Adjazenzlisten und Farben benötigen O(n + m) Speicherplatz. Union-Find erreicht dasselbe Ergebnis in O(n + m α(n)).

Warum ist ein Graph nicht bipartit, wenn er einen ungeraden Zyklus enthält?

Geht den Zyklus entlang, und die Gruppen müssen sich abwechseln: erste, zweite, erste, zweite. Bei einem Zyklus mit einer ungeraden Anzahl von Kanten kommt man nach einer ungeraden Anzahl von Wechseln zum Ausgangspunkt zurück, sodass der Ausgangspunkt zu beiden Gruppen gehören müsste. Ein Graph ist genau dann bipartit, wenn er keinen Zyklus ungerader Länge enthält.

Solltest du BFS oder DFS verwenden, um zu überprüfen, ob ein Graph bipartit ist?

Beides funktioniert: Die Färbungsregel ist dieselbe, nur die Besuchsreihenfolge ändert sich. Bei großen Graphen solltest du DFS mit einem expliziten Stack schreiben, da eine rekursive Version pro Knoten eine Aufrufebene tief gehen kann.

def isBipartite(n, edges):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

n = 4
edges = [[0, 1], [1, 2], [2, 3], [3, 0]]

Erwartete Ausgabe

true

Is Graph Bipartite

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jede Aufteilung aus

Union-Find auf den Nachbarn jedes Knotens

Breitensuche-basierte Zweifärbung jedes Teils

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben