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
Przykład 2
źródło
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:
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.
źródło
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.
źródło