Find if Path Exists in Graph

Q: Berapa kompleksitas waktu untuk mencari tahu apakah ada jalur dalam graf?

BFS atau DFS membutuhkan waktu dan ruang O(n + m) untuk n node dan m edge. Union-find dengan union berdasarkan ukuran dan path halving membutuhkan waktu O(n + m·α(n)) dan ruang O(n) , dan α(n) merupakan konstanta kecil dalam praktiknya.

Q: Apa fungsi kompresi jalur dan union berdasarkan ukuran dalam union-find?

Mereka menjaga pohon tetap dangkal agar find tetap cepat. Union berdasarkan ukuran menempatkan pohon yang lebih kecil di bawah pohon yang lebih besar, sehingga kedalaman sebuah node bertambah hanya ketika grupnya setidaknya menjadi dua kali lipat, yang membatasi kedalaman hingga log n . Kompresi jalur, atau pembagian jalur, mempersingkat perjalanan menuju root setiap kali find dijalankan.

MudahGraf Union-find

+10

Sebuah graf tak berarah memiliki n simpul, bernomor dari 0 hingga n-1. Setiap entri [u, v] dalam edges menghubungkan simpul u dan v, dan kamu dapat melewati sisi dalam kedua arah. Kembalikan true jika kamu dapat berjalan dari source ke destination melalui sisi-sisi tersebut, dan false jika tidak. Sebuah simpul selalu dapat mencapai dirinya sendiri.

Fungsi

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

ninteger: jumlah node
edgesinteger-2d-array: sisi-sisinya, masing-masing berupa pasangan [u, v] dari simpul yang terhubung
sourceinteger: node tempat kamu memulai
destinationinteger: node yang ingin kamu capai
Mengembalikanboolean: apakah suatu jalur menghubungkan sumber dan tujuan

Batasan

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v] dengan 0 ≤ u, v ≤ n-1 dan u ≠ v
Tidak ada sisi yang muncul dua kali, dalam arah mana pun.
0 ≤ source, destination ≤ n-1

Contoh

Input: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
Output: true
Penjelasan: Lintasan 0 → 1 → 2 → 3 menggunakan tiga sisi, jadi simpul 3 dapat dijangkau. Simpul 4 dan 5 membentuk bagian terpisah yang tidak diperlukan dalam lintasan tersebut.

Input: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
Output: false
Penjelasan: Dari node 2, kamu mencapai 0 lalu 1, dan tidak ada yang lain. Node 4 hanya terhubung ke node 3, dan tidak ada sisi yang menghubungkan {0, 1, 2} dengan {3, 4}, jadi jawabannya adalah false.

Pertanyaan lanjutan

Misalkan sisi-sisinya hanya memiliki satu arah: [u, v] memungkinkan kamu berjalan hanya dari u ke v. Manakah dari tiga pendekatan yang masih berfungsi, dan apa yang perlu kamu ubah pada pendekatan tersebut?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Pertanyaannya adalah apakah source dan destination berada di bagian graf yang sama dan saling terhubung. Pencarian breadth-first pada adjacency list menjawabnya dengan menelusuri setiap node dan edge satu kali. Union-find menjawabnya dengan menggabungkan kelompok saat membaca edge, tanpa daftar tetangga sama sekali.

Sapukan bagian tepi sampai tidak ada yang berubah

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tandai source sebagai sudah dicapai, lalu telusuri daftar edge. Edge dengan satu ujung yang sudah ditandai memungkinkan kamu mencapai ujung lainnya, jadi tandai ujung itu. Ulangi sampai suatu penelusuran tidak menandai hal baru atau destination ditandai.

Node yang berjarak k dari source paling lambat akan ditandai pada penelusuran ke-k, dan node hanya ditandai melalui edge dari node yang sudah ditandai, jadi jawabannya benar. Biayanya bergantung pada urutan edge. Jika suatu jalur dicantumkan dari ujung yang jauh ke belakang, setiap penelusuran menandai satu node: jalur dengan 5000 edge membutuhkan 5000 penelusuran, dengan 2.5 × 10^7 pemeriksaan edge.

Algoritma

Buat reached dengan hanya source yang ditandai.
Periksa setiap edge [u, v]. Jika tepat satu ujung ditandai, tandai ujung lainnya dan catat bahwa ada perubahan.
Ulangi pemeriksaan selama ada perubahan dan destination masih belum ditandai.
Kembalikan apakah destination ditandai.

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]

Pencarian melebar dahulu

Intuisi

Penelusuran ini membaca ulang sisi yang ujung-ujungnya sudah lama ditetapkan. Sebagai gantinya, catat untuk setiap node semua node yang terhubung dengannya, dengan memasukkan setiap sisi ke dalam kedua daftar karena kamu bisa melewatinya dari kedua arah. Lalu telusuri ke luar dari source menggunakan antrean, dengan memasukkan setiap tetangga yang belum kamu kunjungi.

Tandai sebuah node sebagai sudah dikunjungi saat kamu memasukkannya ke antrean. Dengan begitu, tidak ada node yang masuk ke antrean dua kali, dan pencarian berakhir bahkan pada siklus seperti 0 → 1 → 2 → 0. Jika antrean kosong sebelum destination keluar dari antrean, berarti kamu sudah mengunjungi setiap node yang dapat dijangkau oleh source. Setiap node dimasukkan ke antrean satu kali dan setiap sisi diperiksa dari kedua ujungnya: waktu dan ruang O(n + m) untuk m sisi.

Algoritma

Buat adjacency list: untuk setiap edge [u, v], tambahkan v ke dalam list milik u dan u ke dalam list milik v.
Tandai source sebagai sudah dikunjungi dan masukkan ke dalam queue.
Ambil sebuah node dari bagian depan. Jika node tersebut adalah destination, kembalikan true.
Tandai dan masukkan ke dalam queue setiap tetangga yang belum dikunjungi.
Jika queue kosong, kembalikan false.

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

Union-find

Intuisi

Kamu perlu mengetahui apakah suatu jalur ada, bukan seperti apa jalur itu. Mulailah dengan setiap simpul berada dalam kelompoknya sendiri. Sisi [u, v] menyatakan bahwa u dan v termasuk dalam kelompok yang sama, jadi gabungkan kelompok mereka. Setelah semua sisi diproses, source dan destination terhubung tepat ketika keduanya berada dalam kelompok yang sama.

Simpan setiap kelompok sebagai pohon tautan parent, akar menamai kelompok tersebut, dan find(x) menelusuri tautan ke atas hingga mencapai akar. Dalam contoh kedua, [0, 1] dan [0, 2] membentuk {0, 1, 2}, sedangkan [3, 4] membentuk {3, 4}, jadi find(2) dan find(4) mengembalikan akar yang berbeda.

Menempatkan pohon yang lebih kecil di bawah pohon yang lebih besar, lalu mengarahkan setiap simpul ke kakek-neneknya saat find, membuat pohon tetap datar. Biaya setiap operasi menjadi α(n), yaitu fungsi Ackermann invers, yang nilainya di bawah 5 untuk masukan nyata apa pun. Hanya parent dan size yang disimpan: ruang O(n).

Algoritma

Tetapkan parent[x] = x dan size[x] = 1 untuk setiap simpul.
Untuk setiap sisi [u, v], cari root a dan b dari kedua ujungnya.
Jika keduanya berbeda, gantungkan root kelompok yang lebih kecil di bawah kelompok lainnya dan jumlahkan ukurannya.
Kembalikan apakah find(source) sama dengan find(destination).

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)

Jebakan dan kasus tepi

Menambahkan setiap edge hanya dalam satu arah. Dengan edges = [[1, 0]], daftar satu arah tidak menemukan jalur dari 0 ke 1.
Menandai node sebagai sudah dikunjungi saat kamu mengeluarkannya dari queue. Node itu lalu masuk ke queue sekali untuk setiap tetangga yang diproses sebelumnya, hingga 2m entri, bukan n.
Melupakan bahwa source bisa sama dengan destination. Jawabannya adalah true, bahkan jika node itu tidak memiliki edge.
DFS rekursif pada jalur panjang. Jalur yang melewati 5000 node menghasilkan 5000 panggilan bertingkat, melebihi batas default Python sebesar 1000. Gunakan queue atau stack eksplisit.
Membandingkan parent[source] dengan parent[destination] dalam union-find. Hanya root yang menunjukkan sebuah grup, jadi bandingkan find(source) dengan find(destination).

Pertanyaan yang sering diajukan3

Apakah saya harus menggunakan BFS, DFS, atau union-find untuk memeriksa apakah ada jalur?

Ketiganya memiliki kompleksitas linear atau hampir linear. BFS dan DFS dapat berhenti begitu menemukan tujuan, dan dapat mengembalikan jalurnya. Union-find tidak memerlukan adjacency list dan cocok untuk banyak pertanyaan tentang konektivitas pada satu graf: setelah penggabungan, setiap pertanyaan membutuhkan dua pemanggilan find.

Berapa kompleksitas waktu untuk mencari tahu apakah ada jalur dalam graf?

BFS atau DFS membutuhkan waktu dan ruang O(n + m) untuk n node dan m edge. Union-find dengan union berdasarkan ukuran dan path halving membutuhkan waktu O(n + m·α(n)) dan ruang O(n), dan α(n) merupakan konstanta kecil dalam praktiknya.

Apa fungsi kompresi jalur dan union berdasarkan ukuran dalam union-find?

Mereka menjaga pohon tetap dangkal agar find tetap cepat. Union berdasarkan ukuran menempatkan pohon yang lebih kecil di bawah pohon yang lebih besar, sehingga kedalaman sebuah node bertambah hanya ketika grupnya setidaknya menjadi dua kali lipat, yang membatasi kedalaman hingga log n. Kompresi jalur, atau pembagian jalur, mempersingkat perjalanan menuju root setiap kali find dijalankan.

def validPath(n, edges, source, destination):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

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

Output yang diharapkan

true

Find if Path Exists in Graph

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Sapukan bagian tepi sampai tidak ada yang berubah

Pencarian melebar dahulu

Union-find

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa