Is Graph Bipartite

Q: Grafın iki parçalı olup olmadığını belirlemenin zaman karmaşıklığı nedir?

Genişlik öncelikli veya derinlik öncelikli renklendirme, m kenar için O(n + m) sürede çalışır: her düğüm bir kez renklendirilir ve her kenar her iki ucundan birer kez karşılaştırılır. Komşuluk listeleri ve renkler O(n + m) alan kaplar. Birleşim-bulma yapısı aynı sonuca O(n + m α(n)) sürede ulaşır.

OrtaGraflar Kuyruk

+10

Bir grafın n düğümü vardır ve bunlar 0 ile n-1 arasında etiketlenmiştir. edges içindeki her [a, b] çifti, a düğümü ile b düğümü arasındaki yönsüz bir kenardır. Graf birkaç ayrı parçaya ayrılmış olabilir ve bazı düğümlerin hiç kenarı olmayabilir.

Bir graf, düğümlerini her kenar bir gruptaki düğümü diğer gruptaki bir düğüme bağlayacak şekilde iki gruba ayırabiliyorsanız iki parçalıdır. Graf iki parçalıysa true, değilse false döndürün.

Fonksiyon

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

ninteger: 0'dan n-1'e kadar numaralandırılmış düğüm sayısı
edgesinteger-2d-array: yönsüz kenarlar; her biri [a, b] çiftidir
Döndürürboolean: düğümler, her kenar iki grup arasında olacak şekilde iki gruba ayrılabiliyorsa true, aksi takdirde false

Kısıtlar

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] olmak üzere 0 ≤ a, b ≤ n-1 ve a ≠ b
Hiçbir kenar, hangi yönde olursa olsun, iki kez görünmez.

Örnekler

Girdi: n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Çıktı: true
Açıklama: 0 ve 2 düğümlerini bir gruba, 1 ve 3 düğümlerini diğer gruba koyun. Dört kenarın her biri iki grubu birleştirir.

Girdi: n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Çıktı: false
Açıklama: [0, 1] kenarı sorunsuz bölünüyor ve 5 numaralı düğümün hiç kenarı yok, ancak 2, 3 ve 4 numaralı düğümler bir üçgen oluşturuyor. Başarısız olan tek bir parça bile yanıtı false yapmaya yeter.

Ek soru

Graf iki parçalı değilse, kanıt olarak düğümlerini sırasıyla listeleyerek tek sayıda kenarı olan bir döngü döndürebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bir düğüm için grup seçmek, onun bağlı bölümünün geri kalanını da belirler: bir komşu diğer gruba geçer. Her bölümü, iki rengi sırayla kullanan bir genişlik öncelikli aramayla renklendir; çizge, tam olarak hiçbir kenarın iki ucunda da aynı renk yoksa iki parçalıdır. Çizge bağlantısız olabilir, bu nedenle renklendirilmemiş her düğüm yeni bir arama başlatır.

Her bölmeyi dene

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Her bölmeyi dene. Her düğümün grubunu bir bit olarak ele al; böylece n bit bir ikili sayı oluşturur ve 0'dan 2^n-1'e kadar saymak her bölmeyi bir kez ziyaret eder. Her bölme için tüm kenarları kontrol et ve herhangi bir bölmede her kenar gruplar arasında kalıyorsa true döndür. Her düğümle birlikte bölme sayısı iki katına çıkar: 20 düğüm yaklaşık bir milyon bölme verir.

Algoritma

0'dan 2^n-1'e kadar her sayı için, i düğümünü i bitinin belirttiği gruba koyun.
Her kenar iki grubu birleştiriyorsa true döndürün.
Hiçbir bölme işe yaramıyorsa false döndürün.

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

Her düğümün komşuları üzerinde union-find

Sezgi

Bir düğüm hangi gruba düşerse düşsün, tüm komşuları diğer gruba düşer; böylece aynı grubu paylaşırlar. Her düğüm için tüm komşularını bir union-find kümesinde birleştir; böylece küme, aynı tarafta bulunmaya zorlanan düğümleri içerir. Her iki ucu da aynı kümede olan bir kenar bir grubun içinde kalmak zorundadır; dolayısıyla grafik iki parçalı değildir.

Bu kontrol tüm başarısızlıkları yakalar. Tek uzunluklu bir çevrimde, ikişer kenarı birleştirmek ilk düğümünü son düğümüne bağlar ve çevrimi kapatan kenar da bu ikisini birleştirir. Tek uzunluklu çevrim yoksa her birleştirme, aralarındaki mesafe çift olan ve dolayısıyla aynı tarafta bulunan iki düğümü birleştirir. Bir düğümün ilk komşusu olan sabitleyici, komşularının kümesini belirler; böylece kenarlar akış hâlindeyken, komşuluk listeleri olmadan birleştirme yaparsın. Boyuta göre birleştirme ve yol yarılama ile 2m birleştirme ve m kontrol O(m α(n)) maliyetindedir.

Algoritma

Her düğüm için parent[x] = x ve anchor[x] = -1 değerlerini ayarla.
Her [u, v] kenarı için, henüz bir çapası yoksa her uca diğer ucu çapa olarak ata.
v düğümünü anchor[u] düğümünün kümesine, u düğümünü de anchor[v] düğümünün kümesine birleştir.
Bir kenarın iki ucu da aynı kümedeyse false, aksi hâlde true döndür.

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

Her parçanın genişlik öncelikli iki renkle boyanması

Sezgi

Bir çelişki kesindir. Bir parçadaki ilk renk serbestçe seçilir ve onu değiştirmek parçanın tamamındaki renkleri değiştirir; diğer tüm renkler bir kenar tarafından belirlenir. Arama, düğümleri başlangıçtan uzaklıklarının çift ya da tek olmasına göre renklendirir; bu nedenle iki komşu yalnızca parçada tek uzunluklu bir döngü varsa aynı rengi alır ve o durumda da hiçbir bölme mümkün değildir.

Bir arama yalnızca kendi parçasını görür; bu yüzden tüm düğümleri dolaş ve hâlâ renklendirilmemiş olanların her birinden yeni bir arama başlat. Üçüncü örnekte, 0 düğümünden başlayan arama 0 ve 1 düğümlerini renklendirir. 2 düğümünden başlayan arama, 2 düğümüne 0 rengini, 3 ve 4 düğümlerine 1 rengini verir; ardından her iki ucunda da 1 rengi bulunan [3, 4] kenarını bulur: false. Her düğüm bir kez renklendirilip kuyruğa eklenir ve 2m liste girdisinin her biri bir kez karşılaştırılır: O(n + m) zaman ve alan.

Algoritma

Her kenarı iki ucun altında da listeleyerek komşuluk listeleri oluşturun ve her rengin değerini -1 olarak ayarlayın.
Sırayla, renklendirilmemiş her düğüme 0 rengini verin ve onu bir kuyruğa ekleyin.
Bir düğümü kuyruktan çıkarın. Renklendirilmemiş her komşuya zıt rengi verip kuyruğa ekleyin; bir komşu aynı renge sahipse false döndürün.
Her bileşen renklendirildikten sonra true döndürün.

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

Tuzaklar ve uç durumlar

Yalnızca 0 düğümünden arama yapmak. Üçüncü örnek, 0 düğümünün çevresinde sorunsuz çalışır ve 2, 3 ve 4 düğümleri arasında başarısız olur.
Her kenarı yalnızca bir listeye eklemek. [1, 0] ve [2, 0] kenarlarıyla 0 düğümü 0 rengini alır ve hiçbir komşu görmez; ardından 1 düğümü de 0 rengini alır ve 0 düğümüne giden kenarı, yol sorunsuz biçimde ayrılsa da bir çakışma gibi görünür.
Bir düğümü kuyruktan çıkardığında renklendirmek. Böylece bir düğüm kuyruğa iki kez girebilir ve ikinci ziyaret ilk rengin üzerine yazar. Düğümü kuyruğa eklerken renklendir.
İki parçalı olmayı döngüsüz olmakla karıştırmak. Kare bir döngü içerir ve iki parçalıdır; yalnızca tek uzunluklu döngüler ayrımı bozar.

Sıkça sorulan sorular3

Grafın iki parçalı olup olmadığını belirlemenin zaman karmaşıklığı nedir?

Genişlik öncelikli veya derinlik öncelikli renklendirme, m kenar için O(n + m) sürede çalışır: her düğüm bir kez renklendirilir ve her kenar her iki ucundan birer kez karşılaştırılır. Komşuluk listeleri ve renkler O(n + m) alan kaplar. Birleşim-bulma yapısı aynı sonuca O(n + m α(n)) sürede ulaşır.

Tek sayılı uzunluktaki bir döngü, bir grafı neden iki parçalı olmaktan çıkarır?

Çevrim boyunca ilerlediğinizde gruplar sırayla değişmelidir: birinci, ikinci, birinci, ikinci. Tek sayıda kenarı olan bir çevrim, tek sayıda geçişten sonra sizi başlangıç noktasına geri getirir; bu durumda başlangıç noktası her iki grupta da olmak zorunda kalır. Bir çizge, ancak ve ancak tek uzunluklu bir çevrimi yoksa iki parçalıdır.

Bölümlemeli olup olmadığını kontrol etmek için BFS mi yoksa DFS mi kullanmalısınız?

İkisi de işe yarar: renklendirme kuralı aynıdır, yalnızca ziyaret sırası değişir. Büyük graflarda DFS’yi açık bir yığın kullanarak yaz; çünkü özyinelemeli bir sürüm her düğüm için bir çağrı derinliğine ulaşabilir.

def isBipartite(n, edges):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

true

Is Graph Bipartite

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her bölmeyi dene

Her düğümün komşuları üzerinde union-find

Her parçanın genişlik öncelikli iki renkle boyanması

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler