Algoritma pelabelan waktu linier untuk pohon?

Saya memiliki pohon tidak berarah yang simpulnya ingin saya beri label. Node daun harus diberi label satu. Lalu, anggap daunnya sudah dibuang. Di pohon yang tersisa, daunnya harus diberi label dua. Proses ini berlanjut dengan cara yang jelas sampai semua simpul memiliki label. Alasan saya melakukan ini adalah saya ingin menyimpan simpul dalam antrian, dan pergi melalui mereka "pergi dulu". Apakah ada cara mudah untuk melakukan ini waktu? $O(n+m)$

Saya dapat memecahkan masalah dengan melakukan BFS di setiap langkah. Tetapi dalam kasus terburuk, pada setiap langkah saya melalui setiap titik, menghapus tepat dua daun dan enqueue mereka. Saya percaya ini membutuhkan waktu kuadratik.

Gagasan lain adalah pertama-tama menemukan semua daun, dan kemudian melakukan BFS dari setiap daun. Ini tidak memberi saya solusi yang diinginkan. Misalnya, perhatikan semacam "grafik mahkota" seperti pada gambar di bawah ini. Solusi yang diinginkan ditampilkan, tetapi meluncurkan BFS dari masing-masing daun akan menghasilkan hanya dua label yang digunakan.

masukkan deskripsi gambar di sini

Idealnya, algoritma waktu linear juga mudah dijelaskan dan diimplementasikan.

algorithms trees Bob Whiz
sumber

Jawaban:

Pohon yang Tidak Tumbang

$O(E+V\log V)$

Masukkan semua simpul dalam antrian prioritas, dengan prioritas mereka adalah gelar mereka.
Sementara antrian tidak kosong:
- $v$ $1$ $0$
- $\sigma(v) = 1 + \max \sigma(u)$ $u$ $v$
- Kurangi dari prioritas tetangga unik yang tersisa (jika ada). $1$ $u$

Faktanya, kita tidak benar-benar membutuhkan antrian prioritas, dan algoritma ini dapat diimplementasikan menggunakan antrian sederhana dalam waktu : $O(E+V)$

Inisialisasi larik panjang dengan derajat semua simpul. $V$
Inisialisasi array lain dengan panjang dengan "hidup". $V$
Pergi sekali melalui array pertama, dan dorong semua simpul derajat ke antrian. $1$
Sementara antrian tidak kosong:
- Pop a vertex . $v$
- Biarkan , di mana memeriksa semua tetangga asli . $\sigma(v) = 1 + \max \sigma(u)$ $u$ $v$
- Tandai sebagai "mati". $v$
- Jika memiliki beberapa "hidup" tetangga , kurangi dari derajat . $v$ $u$ $1$ $u$
- Jika derajat baru adalah , dorong ke antrian. $u$ $1$ $u$

Pohon Berakar

Gunakan DFS sebagai gantinya. Berikut ini adalah sketsa algoritma.

Diberikan simpul , jika adalah daun, set . $v$ $v$ $d(v) = 1$
Jika bukan selembar daun, jalankan algoritme pada semua anak-anaknya, lalu biarkan , di mana memeriksa set semua anak. $v$ $d(v) = 1 + \max d(u)$ $u$

Anda menjalankan algoritma ini di root.

Yuval Filmus
sumber

Apakah ini benar? Pertimbangkan pohon 1-> 2-> 3-> 4-> 5, di mana 1 adalah akarnya. 2 seharusnya mendapatkan label 1, tetapi Anda memberi 3? Atau dengan anak-anak yang Anda maksud tetangga? Node mana yang kita mulai dari dfs saat itu?

Knoothe

Implementasi saya "tidak aktif", tetapi menurut uraian Anda, harus mendapatkan label , karena Anda harus menghapus , lalu , lalu , dan hanya kemudian menjadi lembaran.

2

$2$

4

$4$

5

$5$

4

$4$

3

$3$

2

$2$

Yuval Filmus

Saya tidak mengajukan pertanyaan :-). Saya menafsirkan pertanyaan itu sebagai: Pohon yang tidak terarah. Labeli semua daun. Hapus mereka. Berulang pada pohon yang dihasilkan. Jika demikian, pohon tersebut sebenarnya 1-2-3-4-5, Langkah 1, Anda menghapus 1 dan 5, lalu 2 dan 4 dan kemudian 3. Lihat paragraf tentang "grafik mahkota". Ini adalah salah satu algoritma klasik untuk menemukan pusat pohon.

Knoothe

1 bukan daun. Sangat jauh dari menjadi daun, itu adalah akar. Saya menafsirkan pertanyaan sebagai penargetan pohon berakar. Mungkin kita harus menunggu OP merespons.

Yuval Filmus

@YuvalFilmus, hanya untuk memasukkan 2 sen saya, bukankah seharusnya ? Daunnya , jika Anda menghapusnya maka daun yang baru seharusnya , jadi itu adalah ukuran berapa banyak lapisan yang harus Anda hapus sebelum simpul menjadi daun. Dengan min, setiap simpul yang berdekatan dengan daun mendapat 2, tetapi itu mungkin tidak menjadi daun ketika daun dihapus. Kalimat itu mengandung terlalu banyak dedaunan. Saya butuh sapu.

1 + m a x {d (u)}

$1+max\{d(u)\}$

1

$1$

2

$2$

Luke Mathies

Jawaban langsung adalah sebagai berikut:

Ubah ini menjadi grafik terarah, di mana kita memiliki edge dari setiap node ke induknya . Perhatikan bahwa Anda mendapatkan dag (grafik asiklik langsung). $(u,v)$ $u$ $v$
Urutkan grafik secara topologis.
Pindai simpul, dalam urutan terurut. Labeli setiap titik dengan satu lebih dari label terbesar pada pendahulunya. Karena kita memindai dalam urutan topologis, semua pendahulu akan sudah menerima label sebelum kita mencoba memberi label . $v$ $v$

Setiap langkah ini dapat dilakukan dalam waktu , sehingga total waktu berjalan adalah . Saya menyebutkan pendekatan alternatif ini hanya jika Anda merasa secara konsepsi lebih mudah dipahami daripada jawaban Yuval. $O(n+m)$ $O(n+m)$

DW
sumber