Find if Path Exists in Graph

Q: Bir grafikte bir yol olup olmadığını bulmanın zaman karmaşıklığı nedir?

BFS veya DFS ile, n düğüm ve m kenar için zaman ve bellek karmaşıklığı O(n + m) olur: her düğüm bir kez ziyaret edilir ve her kenar her iki ucundan kontrol edilir. Boyuta göre birleştirme ve yol kısaltma kullanan union-find, O(n + m·α(n)) zaman ve O(n) bellek gerektirir; burada α o kadar yavaş büyür ki pratikte küçük bir sabittir.

Q: BFS neden ziyaret edilmiş bir diziye ihtiyaç duyar?

Bu olmadan, 0 → 1 → 2 → 0 gibi bir döngü aramanın sonsuza kadar sürmesine neden olur; döngüler olmasa bile, birkaç komşusu olan bir düğüm her komşusu için kuyruğa eklenir. Her düğümü kuyruğa eklendiği anda işaretlemek, düğümün yalnızca bir kez işlenmesini garanti eder; işin O(n + m) ile sınırlanmasını sağlayan da budur.

Q: Birleşim-bulma yapısında yol sıkıştırma ve boyuta göre birleştirme ne işe yarar?

Ağaçları sığ tutarlar, böylece find hızlı kalır. Boyuta göre birleştirme, küçük ağacı büyük ağacın altına bağlar; böylece bir düğümün derinliği yalnızca grubunun boyutu en az iki katına çıktığında artar ve derinlik log n ile sınırlanır. Yol sıkıştırma veya burada kullanılan yol yarılama, köke giden yolu her seferinde kısaltır. Birlikte, her işlemin maliyetini α(n) düzeyine indirirler.

KolayGraflar Union-find

+10

Yönsüz bir grafın n düğümü vardır; düğümler 0 ile n-1 arasında numaralandırılmıştır. edges dizisinin her [u, v] girdisi u ve v düğümlerini birbirine bağlar ve bir kenar üzerinde her iki yönde de ilerleyebilirsiniz. Kenarlar boyunca source düğümünden destination düğümüne ulaşabiliyorsanız true, aksi takdirde false döndürün. Bir düğüm her zaman kendisine ulaşabilir.

Fonksiyon

validPath(n: integer, edges: integer-2d-array, source: integer, destination: integer) → boolean

ninteger: düğüm sayısı
edgesinteger-2d-array: kenarlar; her biri, birbirine bağlı düğümlerden oluşan bir [u, v] çifti
sourceinteger: başladığınız düğüm
destinationinteger: ulaşmak istediğin düğüm
Döndürürboolean: bir yolun kaynak ile hedefi birleştirip birleştirmediği

Kısıtlar

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v] olmak üzere 0 ≤ u, v ≤ n-1 ve u ≠ v
Hiçbir kenar, her iki yönde de iki kez görünmez.
0 ≤ source, destination ≤ n-1

Örnekler

Girdi: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
Çıktı: true
Açıklama: 0 → 1 → 2 → 3 yürüyüşü üç kenar kullanır; bu nedenle 3 düğümüne ulaşılabilir. 4 ve 5 düğümleri, yürüyüşün hiç ihtiyaç duymadığı ayrı bir parça oluşturur.

Girdi: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
Çıktı: false
Açıklama: 2. düğümden 0'a, ardından 1'e ulaşırsın ve başka hiçbir yere ulaşamazsın. 4. düğüm yalnızca 3. düğüme bağlıdır ve hiçbir kenar {0, 1, 2} kümesini {3, 4} kümesine bağlamaz; bu yüzden yanıt false olur.

Gönderirken +16 gizli test

Ek soru

Kenarların tek yönlü olduğunu varsayın: [u, v] yalnızca u'dan v'ye gitmenizi sağlar. Üç yaklaşımdan hangileri hâlâ işe yarar ve bunlarda neyi değiştirirsiniz?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Soru, source ve destination değerlerinin grafın aynı bağlantılı parçasında olup olmadığıdır. Yavaş yöntem, yeni hiçbir noktaya ulaşılamayana kadar kenar listesini yeniden tarar. Komşuluk listesi üzerinde yapılan bir genişlik öncelikli arama her düğümü ve kenarı bir kez inceler; birleşim-bulma ise kenarları okurken grupları birleştirerek aynı yanıtı verir ve hiç komşu listesi kullanmaz.

Kenarları artık hiçbir şey değişmeyene kadar süpür

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

Sezgi

Ulaşabileceğini bildiğin her düğümü, source ile başlayarak işaretle. Şimdi kenar listesini oku. Bir ucu işaretli, diğer ucu işaretsiz olan bir kenar, işaretsiz uca da ulaşabileceğin anlamına gelir; onu da işaretle. Bir geçişte yeni hiçbir şey işaretlenmeyene veya destination işaretlenene kadar tüm geçişi tekrarla.

Bu doğrudur: source noktasından uzunluğu k olan bir yol üzerindeki düğüm, en geç k. geçişte işaretlenir ve bir düğüm yalnızca işaretli bir düğümden kendisine bir kenar ulaştığında işaretlenir. İlk örnekte, liste sırasına göre yapılan bir geçiş 1, 2 ve 3'ü sırayla işaretler ve işlem tamamlanır.

Maliyet, kenarların sırasına bağlıdır. Yol uzak uçtan geriye doğru listelenirse, her geçişte yalnızca bir düğüm daha işaretlenir. 5001 düğümden geçen bir yol, 5000 kenar üzerinden 5000 geçiş gerektirir; bu da 2.5 × 10^7 kenar kontrolü demektir; komşu listesi üzerinde tek bir geçiş yeterli olabilecekken.

Algoritma

Yalnızca source işaretlenmiş şekilde reached oluşturun.
Her [u, v] kenarını gözden geçirin. Uçlardan tam olarak biri işaretliyse diğerini işaretleyin ve bir değişiklik olduğunu kaydedin.
Bir değişiklik olduğu ve destination hâlâ işaretlenmediği sürece bu işlemi tekrarlayın.
destination işaretli olup olmadığını döndürün.

def validPath(n, edges, source, destination):
    reached = [False] * n
    reached[source] = True
    changed = True
    while changed and not reached[destination]:
        changed = False
        for u, v in edges:
            # An edge with exactly one reached end pulls the other end in.
            if reached[u] != reached[v]:
                reached[u] = reached[v] = True
                changed = True
    return reached[destination]

Enine öncelikli arama

Sezgi

Bu tarama, uçları çoktan belirlenmiş kenarları tekrar okuyarak zaman kaybeder. Bunun yerine, her düğümün temas ettiği düğümleri listele. Her [u, v] kenarı her iki listeye de eklenir; çünkü kenar boyunca iki yönde de ilerleyebilirsin. Ardından source noktasından dışarı doğru keşfe başla: kuyruktan bir düğüm al ve henüz görmediğin her komşuyu kuyruğa ekle.

Bir düğümü kuyruktan çıkardığında değil, kuyruğa eklediğinde görülmüş olarak işaretle. Böylece hiçbir düğüm kuyruğa iki kez girmez ve 0 → 1 → 2 → 0 gibi döngüleri olan çizgelerde bile arama sona erer. destination kuyruktan çıkarılırsa bir yol vardır. Kuyruk önce boşalırsa, source noktasından erişilebilen her düğümü görmüşsündür ve destination bunların arasında değildir.

Her düğüm kuyruğa en fazla bir kez eklenir ve her kenar iki kez, her iki uçtan birer kez incelenir; bu nedenle m kenar için süre O(n + m) olur. Komşu listeleri O(n + m) alan kullanır. Özyineleme yerine kuyruk kullanmak, 5000 düğümlü bir yolun çağrı yığınını taşırmasını önler.

Algoritma

Komşuluk listesi oluştur: her [u, v] kenarı için v'yi u'nun listesine ve u'yu v'nin listesine ekle.
source'u ziyaret edilmiş olarak işaretle ve bir kuyruğa koy.
Öndeki düğümü al. Eğer destination ise true döndür.
Henüz ziyaret edilmemiş her komşuyu işaretle ve kuyruğa ekle.
Kuyruk boşaldığında false döndür.

from collections import deque


def validPath(n, edges, source, destination):
    # Each edge goes both ways, so list it under both of its ends.
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    seen = [False] * n
    seen[source] = True
    queue = deque([source])
    while queue:
        node = queue.popleft()
        if node == destination:
            return True
        for nxt in graph[node]:
            if not seen[nxt]:
                # Mark on push, so no node enters the queue twice.
                seen[nxt] = True
                queue.append(nxt)
    return False

Birleşim-bulma

Sezgi

Yola ihtiyacınız yok; yalnızca yolun var olup olmadığını bilmeniz yeterli. Bu yüzden grafiği birbirine bağlı düğüm grupları olarak ele alın. Başlangıçta her düğüm kendi başına bir gruptur. [u, v] kenarı, u ile v'nin birlikte olduğunu belirtir; bu nedenle gruplarını birleştirin. Tüm kenarlar işlendiğinde, source ve destination ancak aynı gruptalarsa birbirine bağlıdır.

Her grubu parent bağlantıları olan bir ağaç olarak saklayın; kök, grubun adını belirtir. find(x) köke kadar yukarı çıkar. Birleştirmek için köklerden birini diğerinin altına bağlayın. İkinci örnekte, [0, 1] ve [0, 2], {0, 1, 2} grubunu oluşturur; [3, 4] ise {3, 4} grubunu oluşturur; find(2) ve find(4) farklı kökler döndürdüğünden yanıt false olur.

Ağaçları dengeli tutmak için iki alışkanlık işe yarar. Küçük grubu büyük grubun altına bağlayın ve find sırasında her düğümü büyük ebeveynine bağlayarak yolu yarıya indirin. Birlikte, her işlemin maliyetini α(n) olan ters Ackermann fonksiyonuna indirirler; bu değer, görebileceğiniz herhangi bir girdi için 5'in altında kalır. Kenarlar yalnızca bir kez okunur ve sadece parent ile size saklanır: O(n) alan kullanılır ve komşu listeleri oluşturmaya gerek kalmaz.

Algoritma

Her düğüm için parent[x] = x ve size[x] = 1 ayarlayın.
Her [u, v] kenarı için, her iki ucun a ve b köklerini bulun.
Farklılarsa, küçük grubun kökünü diğerinin altına bağlayın ve boyutları toplayın.
find(source) ile find(destination) değerlerinin eşit olup olmadığını döndürün.

def validPath(n, edges, source, destination):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    def find(x):
        # Walk up to the group's 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)
        if a != b:
            # Hang the smaller group under the larger one.
            if size[a] < size[b]:
                a, b = b, a
            parent[b] = a
            size[a] += size[b]
    return find(source) == find(destination)

Tuzaklar ve uç durumlar

Grafik küçük, ancak birkaç ayrıntı aramanın tamamlanıp doğru yanıt vermesini belirler.

Her kenarı yalnızca tek yönde eklemek. Grafik yönsüz olduğundan [1, 0], 0'dan 1'e de gitmenizi sağlamalıdır. Tek yönlü bir komşuluk listesi, bir kenarın ters yönde kullanıldığı yolları kaçırır.
Düğümleri kuyruğa eklerken değil, kuyruktan çıkarırken görüldü olarak işaretlemek. Böylece bir düğüm, kendisinden önce işlenen her komşu için kuyruğa bir kez girer; bu nedenle kuyruk en fazla n giriş yerine 2m giriş tutabilir.
source değerinin destination değerine eşit olabileceğini unutmak. Bu düğümün hiç kenarı olmasa bile yanıt true olur.
Uzun bir yolda özyinelemeli DFS kullanmak. 5000 düğümden geçen bir yol, iç içe 5000 çağrı demektir ve Python'un varsayılan 1000 sınırını aşar. Bir kuyruk veya açık bir yığın kullanın.
Birleşim-bul yapısında parent[source] ile parent[destination] değerlerini karşılaştırmak. Bir grubu yalnızca kökler temsil eder; her zaman find(source) ile find(destination) değerlerini karşılaştırın.
Dizileri 1'den başlatan Lua ve R'deki kaydırmayı unutmak: x düğümü x+1 dizininde bulunur.

Sıkça sorulan sorular4

Bir yolun var olup olmadığını kontrol etmek için BFS, DFS veya union-find kullanmalı mıyım?

Üçü de doğrusaldır veya buna yakındır. BFS ve DFS hedefe ulaştıkları anda durabilir ve yolun kendisini döndürebilir. Union-find bitişiklik listesi gerektirmez, her kenarı bir kez okur ve aynı graf için çok sayıda bağlantılılık sorusu sorulduğunda öne çıkar; çünkü birleştirmelerden sonra her soru iki find çağrısına mal olur.

Bir grafikte bir yol olup olmadığını bulmanın zaman karmaşıklığı nedir?

BFS veya DFS ile, n düğüm ve m kenar için zaman ve bellek karmaşıklığı O(n + m) olur: her düğüm bir kez ziyaret edilir ve her kenar her iki ucundan kontrol edilir. Boyuta göre birleştirme ve yol kısaltma kullanan union-find, O(n + m·α(n)) zaman ve O(n) bellek gerektirir; burada α o kadar yavaş büyür ki pratikte küçük bir sabittir.

BFS neden ziyaret edilmiş bir diziye ihtiyaç duyar?

Bu olmadan, 0 → 1 → 2 → 0 gibi bir döngü aramanın sonsuza kadar sürmesine neden olur; döngüler olmasa bile, birkaç komşusu olan bir düğüm her komşusu için kuyruğa eklenir. Her düğümü kuyruğa eklendiği anda işaretlemek, düğümün yalnızca bir kez işlenmesini garanti eder; işin O(n + m) ile sınırlanmasını sağlayan da budur.

Birleşim-bulma yapısında yol sıkıştırma ve boyuta göre birleştirme ne işe yarar?

Ağaçları sığ tutarlar, böylece find hızlı kalır. Boyuta göre birleştirme, küçük ağacı büyük ağacın altına bağlar; böylece bir düğümün derinliği yalnızca grubunun boyutu en az iki katına çıktığında artar ve derinlik log n ile sınırlanır. Yol sıkıştırma veya burada kullanılan yol yarılama, köke giden yolu her seferinde kısaltır. Birlikte, her işlemin maliyetini α(n) düzeyine indirirler.

Python

def validPath(n, edges, source, destination):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Girdi

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

Beklenen

true

Find if Path Exists in Graph

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Kenarları artık hiçbir şey değişmeyene kadar süpür

Enine öncelikli arama

Birleşim-bulma

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler