Bagaimana cara menemukan jumlah tepi tambahan minimum yang diperlukan untuk menyelesaikan koneksi?

Katakanlah kita telah diberi jumlah node dan edge, masing-masing N dan M. Dan kemudian kita diberikan node mana yang terhubung. Bagaimana kita menemukan jumlah minimum edge tambahan yang diperlukan untuk menyelesaikan koneksi, sehingga Anda dapat mengunjungi setiap node? Dengan menemukan jawabannya, Anda harus dapat melintasi setiap node, baik secara langsung maupun melalui node lain untuk mencapai tujuan.

Contoh masukan:

4 2 (Node dan tepi)

0 1 (simpul 0 dan simpul 1 terhubung)

2 3 (simpul 2 dan simpul 3 terhubung)

Yang kemudian akan memberi kita jawaban 1, kita memerlukan satu sisi tambahan untuk menyelesaikan koneksi.


graph algorithm traversal
person Geir    schedule 14.01.2016    source sumber
comment
Yang Anda maksud adalah edge (koneksi, begitulah sebutannya), karena menambahkan simpul tambahan tidak masuk akal.   -  person Selçuk Cihan    schedule 14.01.2016
comment
Ya, maaf, maksud saya pinggirannya.   -  person Geir    schedule 14.01.2016

Jawaban (2)


arrow_upward
3
arrow_downward

Yang Anda butuhkan hanyalah:

1) Temukan komponen yang terhubung. Hal ini dapat dilakukan dengan dfs atau bfs. Dalam contoh Anda, komponen ini masing-masing adalah 0, 1 dan 2, 3.

2) Kemudian Anda perlu mengulangi semua komponen dan menghubungkan dua titik mana pun untuk setiap dua komponen yang berurutan. Dengan cara ini Anda menghubungkan komponen pertama dan kedua, lalu komponen kedua dan ketiga dan seterusnya... Dalam contoh Anda, Anda dapat menghubungkan simpul mana pun 0, 1 dengan simpul mana pun 2, 3. Misalnya, Anda dapat menghubungkan simpul 0 dan 2.

Sangat mudah untuk melihat bahwa jika jumlah komponen sama dengan C maka jawabannya adalah C - 1 sisi tambahan.

person Edgar Rokjān    schedule 14.01.2016
comment
Mengapa saya perlu menggunakan BFS/DFS? Bukankah dari inputnya kita sudah tahu komponen apa saja yang terhubung? - person Geir; 14.01.2016
comment
@Geir Seperti yang saya mengerti, kami memiliki grafik masukan yang berubah-ubah. Jadi kita tidak tahu apa-apa tentang komponen yang terhubung. Itu sebabnya kita memerlukan semacam pencarian seperti dfs. - person Edgar Rokjān; 14.01.2016
comment
Ah oke! Saya mengerti sekarang. Namun sepertinya saya tidak bisa menyelesaikan semua kasus pengujian dengan kode saya dengan solusi yang Anda berikan... Apakah Anda melihat sesuatu yang dapat ditingkatkan? pastebin.com/NMEUdswV . - person Geir; 14.01.2016
comment
Saya memeriksa kode Anda tanpa memeriksa detailnya. Hal utama yang ingin saya sampaikan adalah kode ini berlebihan. Sebenarnya Anda tidak perlu membuat dfs mengembalikan bool. Anda dapat memeriksa semua simpul seperti yang Anda lakukan sekarang, mulai dfs dari simpul yang belum dikunjungi dan tandai semua simpul yang dapat dijangkau sebagai telah dikunjungi. Jadi, jika Anda memulai dfs dari simpul yang belum dikunjungi, Anda menandai satu komponen utuh. - person Edgar Rokjān; 14.01.2016
comment
Terima kasih banyak atas bantuannya! Saya sekarang menemukan apa yang membuat kode saya sedikit lebih lambat dari yang seharusnya :D - person Geir; 14.01.2016
comment
Apakah sekarang ia lulus semua ujian? - person Edgar Rokjān; 14.01.2016

arrow_upward
0
arrow_downward

Jumlah minimum koneksi yang diperlukan agar grafik Anda dapat terhubung adalah N-1. Tapi ini berlaku jika tidak ada node dengan 0 koneksi.

Coba bayangkan jalur yang menyerupai desain daftar terhubung. Setiap simpul mempunyai derajat tepat 2, kecuali pada kedua ujungnya. Dengan begitu (misalkan koneksi Anda tidak terarah), mulai dari node mana pun, Anda dapat mencapai target Anda hanya dengan mengunjungi node berikutnya yang belum dikunjungi.

Jika M>N-1 maka Anda dapat mencari node yang memiliki koneksi lebih dari yang dibutuhkan dan melanjutkan dari sana.

Coba hitung sambungan tambahan dan bandingkan dengan jumlah minimum yang dibutuhkan (N-1).

person 0gap    schedule 14.01.2016