Saya mencari cara untuk mempertahankan pohon rentang yang relatif seimbang dari grafik, karena saya menambahkan node / tepi baru ke grafik.
Saya memiliki grafik tidak terarah yang dimulai sebagai satu simpul, "root".
Pada setiap langkah, saya menambahkan grafik baik simpul baru dan tepi yang menghubungkannya ke grafik, atau hanya tepi baru, menghubungkan dua node lama. Saat saya menumbuhkan grafik, saya memelihara pohon yang merentang. Sebagian besar waktu, ini berarti bahwa ketika saya menambahkan node dan edge baru, saya menetapkan node baru untuk menjadi anak dari node lama yang terhubung dengannya.
Saya tidak memiliki kontrol atas urutan di mana node baru ditambahkan, sehingga algoritma pembangunan pohon di atas jelas dapat menyebabkan pohon spanning tidak seimbang.
Adakah yang tahu heuristik online yang akan membuat spanning tree "relatif seimbang", sambil meminimalkan jumlah pekerjaan yang dilakukan dalam re-treeing? Saya memiliki kendali penuh atas struktur pohon. Yang tidak saya kendalikan adalah konektivitas grafik, atau urutan penambahan node baru.
Perhatikan bahwa respons Google standar terhadap istilah seperti "seimbang" "rentang" dan "pohon" tampaknya adalah pohon biner dan pohon-B, yang keduanya tidak berlaku. Node grafik saya dapat memiliki jumlah tetangga, sehingga simpul pohon dapat memiliki jumlah anak, bukan 2 seperti pohon biner. B-tree menjaga keseimbangan dengan mengubah daftar kedekatan mereka, dan saya tidak dapat mengubah konektivitas grafik.
sumber
Jawaban:
Setiap kali Anda menambahkan simpul baru dengan tepi, Anda tidak memiliki opsi. Setiap kali Anda menambahkan tepi baru, jika jarak saat ini ke root lebih besar dari jarak melalui tepi baru, Anda menghapus tepi lama di jalur terpendek lama dan menambahkan yang baru. Jika tidak, Anda hanya membiarkan pohon Anda tidak berubah. Saya pikir dengan cara ini Anda mendapatkan sesuatu yang sangat mirip dengan pohon BFS dalam arti bahwa tingkat pohon akan berisi simpul yang sama dan jarak dari simpul ke root akan sama dengan jarak di pohon BFS (dan di grafik), tapi saya tidak tahu apakah itu cukup untuk memenuhi kondisi "spanning tree ideal" Anda.
sumber
Saya akhirnya melakukan hal berikut:
Jawaban Vinicius Santos adalah bagian pertama. Seperti yang dia katakan, pada frame mana pun saya menambahkan node baru dan edge parent-child yang menghubungkannya, atau hanya menambahkan cross-edge antara dua node yang ada. Tepi orangtua-anak tidak menawarkan peluang untuk mengubah struktur pohon, hanya tepian silang yang melakukannya. Pertimbangkan untuk menambahkan cross-edge E antara node A dan B, di mana B memiliki kedalaman pohon yang lebih besar. Jika (A.depth + 1) <B.depth, maka kita dapat mengurangi B.depth dengan menjadikannya anak A.
Setelah mengurangi kedalaman B, kita sekarang harus memeriksa tetangga B, untuk melihat apakah mereka dapat mengurangi kedalaman B dengan menjadi anak-anak dari B. Oleh karena itu kami melakukan lintasan traversal pertama dari B, yang melintasi tepi dari X ke Y jika X. mendalam + 1 <Y.depth, dan menetapkan Y menjadi anak X.
sumber