Porównanie dwóch struktur drzewiastych

Trudno mi opisać to w prawidłowy sposób, więc podam jak najwięcej szczegółów i mam nadzieję, że ktoś wie, co próbuję zrobić = -)

Próbuję porównać dwa drzewa węzłów, aby ustalić, jak podobne / różne są pod względem struktury. Na moich poniższych schematach oba przykłady mają tę samą liczbę dzieci, wnuków itp. W przykładzie 1 Root ma dziecko z dwójką dzieci, ale w przykładzie drugim root nie.

Prawdopodobnie mógłbym wymyślić, jak rekurencyjnie przejść przez pętlę i policzyć, ile jest poszczególnych poziomów, i porównać to, dając mi wyobrażenie o tym, jak podobne są drzewa, ale robiąc to w ten sposób, będzie wyglądało, jakby były identyczne, ale w rzeczywistości nie są.

Czy ktoś się o tym dowie? A nawet jaki jest techniczny termin na to, co to jest?

Edycja: To także jest w C # i używam list do przechowywania tych obiektów i ich dzieci.

Przykład 1

wprowadź opis zdjęcia tutaj

Przykład 2

wprowadź opis zdjęcia tutaj

algorithm data-structure

— Mungoid
źródło

Co tak naprawdę próbujesz osiągnąć? Brzmi trochę jak problem XY .

— sprzedać

Najlepszym sposobem, w jaki mogę to opisać, jest porównanie struktur „molekularnych”, w których użytkownik tworzy jedną cząsteczkę na raz. Przykład 1 byłby strukturą utworzoną przez użytkownika, a przykład 2 mógłby być częścią listy predefiniowanych struktur, aby pomóc ustalić, czy użytkownik utworzył poprawną strukturę. Najwyraźniej szukałem izomorfizmu drzewa korzeniowego = -)

— Mungoid

Odpowiedzi:

To czego szukasz to Izomorfizm Rooted Tree, który jest wyspecjalizowaną wersją Graph Isomorphism , z wyjątkiem drzew i węzła głównego.

Wyjaśnienie podane w tym zadaniu wykorzystuje dwie właściwości:

Mają tę samą liczbę poziomów (odległość między węzłami korzenia i liści)
Każdy poziom ma tę samą liczbę węzłów

Korzystając z tych dwóch właściwości, przejdź od liści do korzenia, oznaczając każdy węzeł liczbą dzieci w kolejności leksykograficznej. Na przykład Twój katalog główny w przykładzie 1 będzie oznaczony (0, 0, (0, 1)) - ma troje dzieci, pierwsze / drugie ma 0 dzieci, a trzecie ma 2 dzieci, które mają odpowiednio 0 i 1 dziecko. Na koniec porównujesz po prostu etykiety główne, aby sprawdzić, czy drzewa są takie same.

Nie zrobiłem tego rodzaju tematu i przeczytałem ten artykuł zaledwie kilka minut temu, więc nie mogę ręczyć za jego poprawność; mam nadzieję, że i tak to pomoże.

— congusbongus
źródło

Niesamowite, to jest dokładnie to, czego szukam! Będę musiał spróbować. Dzięki!

— Mungoid

Myślę, że to działa tylko wtedy, gdy masz węzeł główny, ale w tym przypadku może tak być: D +1

— Roy T.

Jeśli węzeł główny nie został podany, nadal możesz użyć tej techniki, ale wypróbuj każdy root. Porównując dwa drzewa, oznacza to powtarzanie do n razy.

— congusbongus

Tak, działało to jak urok. Trochę czasu

— zajęło

Dzięki za to, wygląda na coś, czego mógłbym użyć, uwielbiam algorytm znajdujący Centrum Drzewa. Bardzo mądry.

— oodavid

Problem polegający na sprawdzeniu, czy dwa wykresy są logicznie takie same, nazywa się Graph Isomorphishm, więc warto zacząć od tego.

Zauważ, że ogólny problem z izomorfizmem grafów dotyczy NP, jednak w tym szczególnym przypadku może istnieć skrót, nie jestem pewien, ponieważ wydaje się logiczne, że aby poznać różnice, musisz sprawdzić, czy są równe.

— Roy T.
źródło

Tak, to jest to, czego potrzebuję. Nigdy nie wymyśliłbym, jak to się nazywa. Dzięki = -)

— Mungoid