Is Graph Bipartite
Sebuah graf memiliki n simpul, berlabel dari 0 hingga n-1. Setiap pasangan [a, b] dalam edges adalah sisi tak berarah antara simpul a dan simpul b. Graf dapat terbagi menjadi beberapa bagian terpisah, dan beberapa simpul mungkin tidak memiliki sisi sama sekali.
Graf disebut bipartit jika simpul-simpulnya dapat dibagi menjadi dua kelompok sehingga setiap sisi menghubungkan simpul dari satu kelompok dengan simpul dari kelompok lainnya. Kembalikan true jika graf tersebut bipartit dan false jika tidak.
Fungsi
- ninteger
- jumlah node, bernomor dari 0 hingga n-1
- edgesinteger-2d-array
- sisi tak berarah, masing-masing berupa pasangan [a, b]
- Mengembalikanboolean
- true jika simpul dapat dibagi menjadi dua kelompok dengan setiap sisi berada di antara kedua kelompok tersebut, false jika tidak
Batasan
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [a, b]dengan0 ≤ a, b ≤ n-1dana ≠ b- Tidak ada sisi yang muncul dua kali, dalam arah mana pun.
Contoh
- Input
- n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
- Output
- true
- Penjelasan
- Masukkan node 0 dan 2 ke dalam satu grup, lalu node 1 dan 3 ke dalam grup lainnya. Keempat edge menghubungkan kedua grup tersebut.
- Input
- n = 3edges = [[0, 1], [1, 2], [2, 0]]
- Output
- false
- Penjelasan
- Node 0 dan 1 harus berada di grup yang berbeda, dan node 2 harus berbeda dari keduanya, tetapi hanya ada dua grup. Siklus yang terdiri dari tiga sisi tidak mungkin dibagi.
- Input
- n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
- Output
- false
- Penjelasan
- Sisi
[0, 1]terbagi dengan baik dan simpul 5 tidak memiliki sisi, tetapi simpul 2, 3, dan 4 membentuk segitiga. Satu bagian yang gagal sudah cukup untuk membuat jawaban menjadifalse.
Pertanyaan lanjutan
Jika graf tidak bipartit, bisakah kamu mengembalikan satu siklus dengan panjang ganjil sebagai bukti, dengan mencantumkan simpul-simpulnya secara berurutan?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Masukkan node 0 ke grup pertama. Ke mana setiap tetangganya harus ditempatkan? Lalu, bagaimana dengan tetangga dari tetangga tersebut?
Setelah satu node dari bagian yang terhubung ditempatkan, semua node lain di bagian itu tidak punya pilihan: kedua ujung sebuah edge masuk ke grup yang berlawanan. Graph hanya gagal ketika penempatan yang dipaksakan ini menempatkan kedua ujung suatu edge dalam satu grup, yang terjadi tepat ketika bagian tersebut memiliki siklus dengan panjang ganjil.
Warnai dengan pencarian breadth-first: beri node pertama suatu bagian warna 0, beri setiap tetangga yang belum diwarnai warna yang berlawanan dengan node saat ini, dan kembalikan
falsejika tetangga sudah memiliki warna yang sama. Mulai pencarian baru dari setiap node yang masih belum diwarnai agar tidak ada bagian yang terlewat.
Solusi
Memilih kelompok untuk satu simpul memaksa pilihan untuk bagian lain yang terhubung dengannya: simpul tetangga masuk ke kelompok lainnya. Warnai setiap bagian dengan pencarian melebar yang menggunakan dua warna secara bergantian; graf bersifat bipartit tepat ketika tidak ada sisi yang memiliki warna sama di kedua ujungnya. Graf bisa saja tidak terhubung, jadi setiap simpul yang belum diwarnai memulai pencarian baru.
Coba setiap pemisahan
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Coba setiap pembagian. Anggap grup setiap simpul sebagai satu bit, sehingga n bit membentuk bilangan biner, dan menghitung dari 0 hingga 2^n-1 akan mengunjungi setiap pembagian satu kali. Untuk setiap pembagian, periksa setiap sisi, lalu kembalikan true jika ada pembagian yang membuat setiap sisi melintasi grup. Jumlah pembagian berlipat ganda untuk setiap simpul: 20 simpul menghasilkan sekitar satu juta.
Algoritma
- Untuk setiap bilangan dari 0 hingga 2^n-1, masukkan simpul
ike dalam grup yang ditentukan oleh biti. - Jika setiap sisi menghubungkan kedua grup, kembalikan
true. - Jika tidak ada pembagian yang berhasil, kembalikan
false.
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] = 1Union-find pada tetangga setiap node
Intuisi
Kelompok mana pun yang ditempati sebuah simpul, semua tetangganya menempati kelompok lainnya, jadi mereka berbagi kelompok. Untuk setiap simpul, gabungkan semua tetangganya ke dalam satu set union-find; sebuah set kemudian memuat simpul-simpul yang harus berada di sisi yang sama. Sisi dengan kedua ujung berada dalam satu set harus tetap berada di dalam satu kelompok, jadi graf tersebut bukan bipartit.
Pemeriksaan ini mendeteksi setiap kegagalan. Di sekitar siklus ganjil, menggabungkan dua sisi sekaligus menyatukan simpul pertama dengan simpul terakhirnya, lalu sisi penutup menyatukan keduanya. Tanpa siklus ganjil, setiap penggabungan menyatukan dua simpul yang berjarak genap, yang berada di sisi yang sama. Tetangga pertama sebuah simpul, yaitu jangkarnya, menentukan set tetangga-tetangganya, jadi kamu menggabungkan simpul saat sisi-sisinya mengalir, tanpa daftar ketetanggaan. Dengan union by size dan path halving, 2m penggabungan dan m pemeriksaan memerlukan biaya O(m α(n)).
Algoritma
- Tetapkan
parent[x] = xdananchor[x] = -1untuk setiap node. - Untuk setiap edge
[u, v], jadikan masing-masing ujung sebagai anchor ujung lainnya jika belum memilikinya. - Gabungkan
vke dalam setanchor[u], danuke dalam setanchor[v]. - Kembalikan
falsejika ada edge yang kedua ujungnya berada dalam satu set, jika tidak, kembalikantrue.
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 TruePewarnaan dua warna secara melebar pada setiap bagian
Intuisi
Konflik bersifat final. Warna pertama dalam sebuah komponen bebas dipilih, dan membaliknya akan membalik seluruh komponen; setiap warna lainnya ditentukan oleh sebuah sisi. Penelusuran mewarnai simpul berdasarkan apakah jaraknya dari titik awal genap atau ganjil, jadi dua tetangga hanya memiliki warna yang sama jika komponen tersebut memiliki siklus dengan panjang ganjil, dan jika demikian, tidak ada pemisahan yang mungkin.
Penelusuran hanya melihat komponennya sendiri, jadi telusuri semua simpul dan mulai penelusuran baru dari setiap simpul yang belum diwarnai. Pada contoh ketiga, penelusuran dari simpul 0 mewarnai simpul 0 dan 1. Penelusuran dari simpul 2 memberi simpul 2 warna 0 dan simpul 3 serta 4 warna 1, lalu menemukan [3, 4] dengan warna 1 di kedua ujungnya: false. Setiap simpul diwarnai dan dimasukkan ke antrean sekali, dan setiap entri list yang berjumlah 2m dibandingkan sekali: waktu dan ruang O(n + m).
Algoritma
- Buat daftar adjacency dengan setiap edge dicatat pada kedua ujungnya, lalu atur semua warna menjadi -1.
- Untuk setiap node yang belum diwarnai secara berurutan, beri warna 0 dan masukkan ke dalam queue.
- Keluarkan sebuah node. Beri setiap neighbour yang belum diwarnai warna yang berlawanan dan masukkan ke dalam queue; jika sebuah neighbour memiliki warna yang sama, kembalikan
false. - Setelah semua bagian diwarnai, kembalikan
true.
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
Jebakan dan kasus tepi
- Hanya mencari mulai dari node 0. Contoh ketiga berjalan baik di sekitar node 0, tetapi gagal di antara node 2, 3, dan 4.
- Menambahkan setiap edge hanya ke satu list. Dengan edge
[1, 0]dan[2, 0], node 0 mendapat warna 0 dan tidak melihat tetangga; node 1 lalu juga mendapat warna 0, dan edge-nya ke node 0 terlihat seperti bentrok, meskipun jalurnya terbagi dengan baik. - Mewarnai node saat kamu mengeluarkannya dari antrean. Node kemudian dapat masuk ke antrean dua kali, dan kunjungan kedua menimpa kunjungan pertama. Warnai node saat kamu memasukkannya.
- Menyamakan bipartit dengan tanpa siklus. Persegi memiliki siklus dan bersifat bipartit; hanya siklus ganjil yang merusak pembagian tersebut.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu dari Is Graph Bipartite?
Pewarnaan breadth-first atau depth-first berjalan dalam O(n + m) untuk m sisi: setiap simpul diwarnai sekali, dan setiap sisi dibandingkan sekali dari masing-masing ujungnya. adjacency list dan warna menggunakan ruang O(n + m). Union-find mendapatkan hasil yang sama dalam O(n + m α(n)).
Mengapa siklus ganjil membuat sebuah graf tidak bipartit?
Telusuri siklusnya, dan kelompok-kelompoknya harus bergantian: pertama, kedua, pertama, kedua. Siklus dengan jumlah sisi ganjil akan membawamu kembali ke titik awal setelah jumlah pergantian yang ganjil, sehingga titik awal harus berada di kedua kelompok. Sebuah graf bipartit jika dan hanya jika tidak memiliki siklus dengan panjang ganjil.
Apakah kamu sebaiknya menggunakan BFS atau DFS untuk memeriksa apakah sebuah graf bipartit?
Keduanya bisa digunakan: aturan pewarnaannya sama dan hanya urutan kunjungannya yang berubah. Untuk graf besar, tulis DFS dengan stack eksplisit, karena versi rekursif bisa membuat satu pemanggilan untuk setiap node.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def isBipartite(n, edges):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
n = 4 edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Output yang diharapkan
true