Graph Valid Tree

Q: Graph Valid Tree'nin zaman karmaşıklığı nedir?

Derinlik öncelikli aramayla O(n + m); burada m kenar sayısıdır. Union-find ile O(n + m α(n)). Her ikisi de önce kenar sayısını kontrol eder, bu nedenle yanlış sayıda kenarı olan bir grafik herhangi bir arama yapılmadan reddedilir.

OrtaUnion-find Graflar

+10

0 ile n-1 arasında numaralandırılmış n düğüm ve yönsüz kenarlardan oluşan bir edges listesi veriliyor. Her [a, b] çifti, a düğümüyle b düğümünü birbirine bağlar.

Kenarlar tüm n düğümü tek bir ağaç hâline getiriyorsa true döndürün: Her düğüm diğer tüm düğümlere ulaşabilmeli ve döngü olmamalıdır. Aksi takdirde false döndürün.

Fonksiyon

validTree(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: kenarlar tüm n düğümü tek bir ağaçta birleştiriyorsa true, aksi takdirde false

Kısıtlar

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

Örnekler

Girdi: n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Çıktı: true
Açıklama: 0. düğüm 1, 2 ve 3. düğümlere bağlanır; 4. düğüm ise 1. düğüme bağlıdır. Beş düğümün tamamını döngü olmadan dört kenar birleştirir, dolayısıyla bu bir ağaçtır.

Girdi: n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Çıktı: false
Açıklama: [1, 2], [2, 3] ve [1, 3] kenarları 1, 2, 3, 1 döngüsünü oluşturur. Beş düğüm üzerindeki beş kenar, bir ağacın sahip olabileceğinden bir fazladır.

Girdi: n = 4edges = [[0, 1], [1, 2], [2, 0]]
Çıktı: false
Açıklama: n-1 olan 3 kenar var, ancak bunlar 0, 1, 2, 0 döngüsünü oluşturuyor ve 3 numaralı düğümün hiç kenarı yok.

Ek soru

Graf bir ağaç olmadığında, onu ağaca dönüştürmek için kaç kenarı çıkarmanız ve kaç kenar eklemeniz gerekir? İkisini de tek geçişte sayabilir misiniz?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir ağaç bağlıdır ve döngü içermez. Tam olarak n-1 kenar olduğunda bunlar tek bir koşuldur: böyle bir çizge, ancak ve ancak döngü içermiyorsa bağlıdır. Bu yüzden önce kenar sayısını kontrol et, ardından bağlantılılığı bir kez ara ya da union-find'in zaten birbirine bağlı iki düğümü birleştiren bir kenarı yakalamasına izin ver.

Her kenardan önce bir yol ara

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

Sezgi

Kenarları teker teker ekle. [u, v] eklemeden önce, şimdiye kadar eklenen kenarları kullanarak u düğümünden arama yap. v düğümüne ulaşılabiliyorsa, yeni kenar bu düğümler arasında ikinci bir yol oluşturur ve ikinci örnekte [1, 3] kenarının yaptığı gibi bir döngüyü kapatır. Hiçbir kenar bir döngüyü kapatmıyorsa, grafik bir ormandır ve 0 numaralı düğümden yapılacak son bir arama bunun tek bir ağaç olup olmadığını gösterir.

Her kontrolde o ana kadar oluşturulmuş grafiğin tamamı aranır. Kenarları sırasıyla gelen 5001 düğümlü bir yolda aramalar 1 + 2 + ... + 5000 düğümü ziyaret eder; bu yaklaşık 12,5 milyondur.

Algoritma

Her düğüm için boş bir komşuluk listesiyle başlayın.
Her [u, v] kenarı için, şimdiye kadar eklenen kenarlar üzerinden u düğümünden arama yapın. v düğümüne ulaşırsa false döndürün.
Aksi takdirde kenarı her iki ucun listesine ekleyin.
Sonunda, 0 numaralı düğümden yapılan bir aramanın n düğümün tamamına ulaşıp ulaşmadığını döndürün.

def reachable(graph, start):
    # Every node a search from start can reach, using the edges added so far.
    seen = [False] * len(graph)
    seen[start] = True
    stack = [start]
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                stack.append(nxt)
    return seen


def validTree(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        # A path from u to v already exists, so this edge closes a cycle.
        if reachable(graph, u)[v]:
            return False
        graph[u].append(v)
        graph[v].append(u)
    # No cycle anywhere. A tree also needs every node reachable from node 0.
    return all(reachable(graph, 0))

Kenarları say, ardından bir kez ara

Sezgi

n ayrı düğümle başlayıp kenarları tek tek ekle. Her kenar ya iki grubu birleştirerek grup sayısını bir azaltır ya da bir grubun içinde kalıp bir döngü oluşturur. Tek bir gruba ulaşmak için n-1 birleştirme gerekir. Bu nedenle n-1'den az kenar grafiği bağlayamaz; daha fazla kenar ise bir döngü oluşturmak zorundadır: 5 düğüm üzerindeki 5 kenardan oluşan ikinci örnek, yalnızca kenar sayısı nedeniyle başarısız olur.

Tam olarak n-1 kenar olduğunda grafik ancak her kenar birleştirme yaptıysa, yani hiçbir kenar döngü oluşturmadıysa tek bir grup hâline gelir. Dolayısıyla sayı doğru olduğunda yalnızca bağlantılılığı kontrol et: 0 düğümünden yapılan tek bir arama, n düğümün tümüne ulaşmalıdır. Üçüncü örnekte yalnızca 0, 1 ve 2'ye ulaşır. m = n-1 olduğunda listeler ve arama O(n) maliyetlidir.

Algoritma

edges.length n-1 değilse false döndür.
Bir komşuluk listesi oluştur ve her kenarı iki ucunun da altına kaydet.
0 düğümünü bir yığına ekle ve ziyaret edildi olarak işaretle.
Düğümleri yığından çıkar; henüz ziyaret edilmemiş her komşuyu yığına eklerken işaretle ve say.
Sayının n'e eşit olup olmadığını döndür.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    # With n-1 edges, the graph is a tree exactly when it is connected.
    seen = [False] * n
    seen[0] = True
    stack = [0]
    reached = 1
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                reached += 1
                stack.append(nxt)
    return reached == n

Kenarları sayma ve birleşim-bulma

Sezgi

Birleşim-bulma, arama yapmadan her kenar için çevrim sorusunu yanıtlar. Her düğüm başlangıçta kendi grubundadır. Bir [u, v] kenarı için her iki ucun kökünü bul. Kökler farklıysa kenar iki parçayı birleştirir; dolayısıyla onları birleştir. Kökler aynıysa u ve v zaten birbirine bağlıdır ve kenar bir çevrim oluşturur. Tüm n-1 kenar birleştirme yaparsa, n grup sonunda tek bir grup olur: bir ağaç.

İki kural, ebeveyn zincirlerini kısa tutar. Birleştirme, küçük grubun kökünü büyük grubun köküne bağlar; böylece 10^4 düğümde hiçbir zincir 13 adımı geçmez. Bir bulma işlemi sırasında, geçtiğin her düğümü büyük ebeveynine bağla. Birlikte, m işlemin maliyetini O(m α(n)) yaparlar; burada α, ters Ackermann fonksiyonu, en fazla 4'tür. Alan kullanımı O(n)'dir.

Algoritma

edges.length, n-1 değilse false döndür.
Her düğüm için parent[x] = x olarak ayarla ve grup boyutunu 1 yap.
Her [u, v] kenarı için u ve v düğümlerinden köklerine kadar ebeveynleri takip et; geçtiğin her düğümü büyük ebeveynine bağla.
Kökler eşitse false döndür.
Kökler farklıysa küçük grubun kökünü diğerine bağla ve boyutunu ekle.
Her kenar iki grubu birleştirdiyse true döndür.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    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

    for u, v in edges:
        a, b = find(u), find(v)
        # The two ends are already joined: this edge closes a cycle.
        if a == b:
            return False
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    # n-1 merges with no cycle turn the n groups into one.
    return True

Tuzaklar ve uç durumlar

Yalnızca döngü olup olmadığını kontrol etmek. Altı düğümdeki üç ayrı kenar döngü oluşturmaz, ancak üç parça oluşturur.
Yalnızca kenar sayısını kontrol etmek. Üçüncü örnekte n-1 kenar vardır, ancak 0, 1, 2 döngüsü düğüm 3'ün ihtiyaç duyduğu kenarı tüketir.
Her kenarı yalnızca bir ucun altında saklamak. [1, 0] da 0 ve 1 düğümlerini birbirine bağlar ve 0 düğümünden yapılan aramada 1 düğümü atlanır.
Ebeveyni atlamayan bir derinlik öncelikli döngü testi. Her kenar doğrudan geldiğiniz düğüme geri döner; bu yüzden "ziyaret edilmiş bir komşuyla karşılaşıldı" durumu her ağaçta gerçekleşir.
Uzun bir yolda özyineleme kullanmak. 5001 düğümlü bir çizgi 5000 çağrı derinliğine ulaşır ve Python'ın varsayılan 1000 sınırını aşar; açık bir yığın kullanın.

Sıkça sorulan sorular3

Graph Valid Tree'nin zaman karmaşıklığı nedir?

Derinlik öncelikli aramayla O(n + m); burada m kenar sayısıdır. Union-find ile O(n + m α(n)). Her ikisi de önce kenar sayısını kontrol eder, bu nedenle yanlış sayıda kenarı olan bir grafik herhangi bir arama yapılmadan reddedilir.

n düğümlü bir ağaçta neden n-1 kenar vardır?

Ağacı bir düğümden başlayarak büyütün ve diğerlerini teker teker ekleyin. Her yeni düğüm tam olarak bir kenarla gelir: hiç kenarı olmazsa bağlantısı kesilir, iki kenarı olursa bir döngü oluşturur. Dolayısıyla n düğüm için n-1 kenar gerekir.

Yönsüz bir grafikte döngüyü nasıl tespit edersiniz?

Union-find'de, iki ucu zaten aynı kökü paylaşan bir kenar bir döngüyü kapatır. Derinlik öncelikli aramada döngü, geldiğin düğüm dışındaki ziyaret edilmiş bir komşudur; bu nedenle her düğümün ebeveynini takip edersin. Union-find için ebeveyn ya da komşuluk listesi gerekmez.

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

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

true

Graph Valid Tree

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her kenardan önce bir yol ara

Kenarları say, ardından bir kez ara

Kenarları sayma ve birleşim-bulma

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler