Pada artikel ini, saya akan menganalisis -secara detail- bagaimana masalah diameter pohon dapat diselesaikan dengan dua traversal Breadth-first search (BFS). Salah satu alasan mengapa solusi ini menarik adalah meskipun intuitif, masih sulit untuk menjelaskan mengapa solusi ini berhasil! Alasan lainnya adalah pemahaman ini memperdalam pemahaman kita tentang “pembuktian melalui kontradiksi”.
Pertama, sebelum melanjutkan ke solusinya, izinkan saya meninjau secara singkat apa yang dimaksud dengan masalah diameter pohon dan konsep-konsep yang diperlukan yang perlu diselesaikan.
Graf adalah kumpulan simpul (disebut juga simpul) dan sisi yang menghubungkan simpul-simpul tersebut.
Pohon adalah jenis grafik tertentu. Ciri utama tipe ini adalah tidak mempunyai siklus (artinya tidak mungkin mengunjungi suatu node lebih dari satu kali dalam satu jalur, ini juga berarti paling banyak terdapat satu jalur antara dua node mana pun).
Diameter pohon adalah tentang menemukan jalur terpanjang dalam sebuah pohon. Ada dua solusi waktu linier yang populer untuk masalah ini; yang pertama didasarkan pada pemrograman dinamis (“lebih detail”), dan yang kedua didasarkan pada algoritma “breadth-first search” (BFS). BFS merupakan algoritma traversal grafik yang bekerja dengan cara melintasi grafik secara level demi level. Perhatikan urutan setiap node yang dikunjungi di sini:
Algoritma BFS diameter pohon
Algoritma ini memanfaatkan BFS sebagai berikut:
- Pilih node acak mana saja (sebut saja X).
- Buat traversal BFS dari node ini.
- Pilih node terjauh dari X (sebut saja node ini A).
- Jalankan BFS lagi tetapi dari node A.
- Pilih node terjauh dari A (sebut saja node ini B).
- Kembalikan A dan B sebagai titik akhir diameter pohon.
Saya yakin Anda merasa bahwa algoritme tersebut terdengar intuitif, namun sayangnya, tidak jelas mengapa algoritme tersebut berhasil. Sebelum menjelaskan alasannya, mari kita nyatakan apa yang akan menjadi dasar pemahaman kita.
- Mengingat A dan B merupakan titik ujung diameter, maka kita juga mengetahui bahwa antara A dan B hanya ada satu jalur, hal ini disebabkan oleh ciri-ciri grafik pohon yang telah kita bahas sebelumnya.
- Untuk menyederhanakan, kita akan berasumsi bahwa hanya ada satu diameter pohon dalam grafik, hal ini memungkinkan kita untuk berkonsentrasi pada masalah utama, daripada mengalihkan fokus kita pada kasus sudut (memperluasnya hingga mencakup beberapa diameter berukuran sama tidaklah tepat). meskipun menantang).
- Jika kita memiliki satu titik akhir (A atau B), maka titik akhir lainnya akan cukup mudah untuk dijangkau. Kita hanya perlu menemukan jalur terpanjang dari titik akhir ini (jalankan BFS) yang akan mengantarkan kita ke titik akhir lainnya. Mengapa hal ini benar? karena jika tidak, kita akan mempunyai jalur yang lebih panjang (yaitu lebih panjang dari A ke B, diameter pohon) yang merupakan suatu kontradiksi.
Dari poin terakhir, kita kemudian dapat mengurangi masalah kita menjadi:
Temukan salah satu titik akhir diameternya.
Untuk mengatasi masalah yang berkurang ini, kita perlu membuktikan bahwa menggunakan BFS dari node mana pun sudah cukup untuk menemukan titik akhir diameter mana pun. Untuk menguji pendekatan ini kita perlu melihat dua skenario:
Skenario 1: node awal X berada di dalam jalur diameter (antara A dan B).
Dalam skenario ini, jika kita menjalankan BFS dari node X ini, menurut Anda node mana yang paling jauh?
Node terjauh harus menjadi salah satu titik akhir diameter karena kita dapat melihat situasi ini seolah-olah kita membagi diameter pohon menjadi dua jalur, Ahingga X dan X hingga B (seperti yang ditunjukkan pada contoh di bawah).
dan jika simpul terjauh bukan titik akhir diameter (katakanlah A*),
kemudian kita dapat memperluas jalur “ X ke A ” ke “ X ke A* ”, yang berarti kita dapat menemukan diameter yang lebih panjang “ B ke A* ” (yang merupakan kontradiksi).
Skenario 2: node awal X berada di luar jalur diameter (antara A dan B).
Skenario ini memiliki dua kasus menarik:
Kasus 1: Jalur terpanjang dari X menyentuh diameter pohon.
Nah, saat jalur terpanjang menyentuh diameter pohon (di simpul T), kita dapat mengulangi skenario 1 dengan mengasumsikan bahwa titik awal kita adalah T. Setelah itu, simpul terpanjang dari X harus memenuhi persamaan ini:
Berdasarkan pembahasan kita pada skenario 1, simpul terjauh dari T akan menjadi titik akhir diameter.
Kasus 2: Jalur terpanjang dari X tidak menyentuh diameter pohon.
Ini berarti kita memiliki dua jalur panjang yang tidak berpotongan pada pohon, satu adalah diameter pohon “A ke B” dan yang lainnya adalah “X ke Y”.
Di sini kami memperkenalkan dua node baru i dan j, ini adalah node yang pada akhirnya akan menghubungkan kedua jalur (harus ada node seperti itu karena pohonnya harus terhubung).
Dalam grafik ini, mari kita asumsikan bahwa jarak dari X ke j adalah ≤ jarak dari j ke Y. Kita dapat berasumsi demikian dengan aman karena jika tidak, kita dapat menukar nama X dan Y agar dapat berfungsi. Selain itu, karena tidak menjadi masalah titik akhir diameter mana yang paling jauh dari simpul i, anggap saja titik akhir tersebut adalah simpul A.
Sejauh ini, dengan melihat grafik di atas, kita dapat mengambil beberapa kesimpulan:
- Node terjauh dari node i sekarang menjadi A (berdasarkan skenario 1).
- Node terjauh dari node j adalah Y. Jika tidak, X tidak akan memilih Y sebagai node terjauhnya.
Karena “j ke Y” › “j ke A”, maka simpul i dapat mengambil langkah lebih banyak untuk mencapai Y daripada A, karena simpul tersebut dapat berpindah ke j dan kita telah mengetahui bahwa simpul terjauh dari j adalah Y. Hal ini membawa kita ke a kontradiksi karena simpul terjauh dari i seharusnya A bukan Y.
Saya harap gambar berikut menggambarkan kontradiksi ini:
Saya harap analisis ini cukup untuk memberikan bukti informal yang cukup baik yang meyakinkan Anda mengapa solusi dua-BFS berhasil. Tolong beri tahu saya di komentar pendapat Anda dan jika ada bagian yang tidak jelas.
