Membandingkan dua struktur pohon

13

Saya mengalami kesulitan mencoba menggambarkan ini dalam istilah yang benar sehingga saya hanya akan memberikan sedetail mungkin dan semoga seseorang tahu apa yang saya coba lakukan = -)

Saya mencoba membandingkan dua pohon simpul untuk menentukan seberapa mirip / berbeda mereka secara struktur. Dalam diagram saya di bawah, kedua contoh memiliki jumlah anak, cucu, dan sebagainya yang sama. Dalam contoh 1, Root memiliki anak dengan dua anak, tetapi dalam contoh dua, root tidak.

Saya mungkin bisa mencari cara untuk mengulang secara berulang dan menghitung berapa banyak setiap level yang ada dan membandingkannya, memberi saya gambaran betapa miripnya pohon-pohon itu, tetapi hanya melakukannya dengan cara itu, akan terlihat seperti mereka identik, tetapi sebenarnya mereka tidak.

Adakah yang tahu tentang ini? Atau bahkan apa istilah teknis untuk apa ini?

Sunting: Juga, ini ada di C # dan saya menggunakan Daftar untuk menyimpan benda-benda ini dan anak-anak mereka.

Contoh 1

masukkan deskripsi gambar di sini

Contoh 2

masukkan deskripsi gambar di sini

algorithm data-structure Mungoid
sumber
1
Apa yang sebenarnya ingin Anda capai? Ini terdengar seperti masalah XY .
msell
Cara terbaik yang bisa saya jelaskan adalah untuk membandingkan struktur 'molekul' yang dibuat pengguna satu molekul pada suatu waktu. Contoh 1 akan menjadi struktur yang dibuat pengguna dan contoh 2 bisa menjadi bagian dari daftar struktur yang telah ditentukan untuk membantu menentukan apakah pengguna membuat struktur yang benar. Isomorfisma pohon akar tampaknya adalah apa yang saya cari = -)
Mungoid

Jawaban:

11

Apa yang Anda cari adalah Rooted Tree Isomorphism, yang merupakan versi khusus dari Graph Isomorphism , kecuali untuk pohon dan simpul akar sudah diperbaiki.

Penjelasan yang diberikan dalam tugas ini menggunakan dua properti:

  • Memiliki jumlah level yang sama (jarak antara node root dan leaf)
  • Setiap level memiliki jumlah node yang sama

Dengan menggunakan dua properti ini, lanjutkan perjalanan Anda dari daun ke akar, beri label setiap node dengan jumlah anak, dalam urutan leksikografis. Misalnya, Root Anda dalam Contoh 1 akan diberi label (0, 0, (0, 1)) - ia memiliki tiga anak, yang pertama / kedua memiliki 0 anak, dan yang ketiga memiliki 2 anak yang masing-masing memiliki 0 dan 1 anak. Akhirnya Anda hanya membandingkan label root untuk melihat apakah pohonnya sama.

Saya belum melakukan subjek semacam ini dan saya hanya membaca makalah ini beberapa menit yang lalu jadi saya tidak bisa menjamin kebenarannya; semoga ini membantu.

congusbongus
sumber
Luar biasa, itu persis seperti apa yang saya cari! Saya harus mencobanya. Terima kasih!
Mungoid
Saya pikir ini hanya bekerja jika Anda memiliki simpul root, tetapi dalam kasus ini yang mungkin terjadi: D +1
Roy T.
Jika simpul root tidak diberikan, Anda masih dapat menggunakan teknik ini tetapi cobalah setiap root. Saat membandingkan dua pohon, ini berarti pengulangan hingga n kali.
congusbongus
Ya itu bekerja seperti pesona. Butuh sedikit waktu untuk memahaminya tetapi bekerja dengan sempurna = -)
Mungoid
Terima kasih untuk ini, sepertinya sesuatu yang bisa saya gunakan juga, saya suka algoritma untuk menemukan Center of a Tree. Sangat pintar.
oodavid
4

Masalah untuk melihat apakah dua grafik secara logis sama disebut Graph Isomorphishm sehingga Anda mungkin ingin jadi mulai dari sana.

Perhatikan bahwa masalah umum Graph Isomorphism ada di NP tetapi untuk kasus khusus ini mungkin ada jalan pintas, saya tidak yakin karena tampaknya logis bahwa untuk mengetahui perbedaan Anda harus memeriksa apakah mereka sama.

Roy T.
sumber
Ya itulah yang saya butuhkan. Tidak akan pernah tahu apa namanya. Terima kasih = -)
Mungoid