Reprezentacja ukorzenionego drzewa

0

Cześć,
Szukam prostej i efektywnej metody (takiej, którą potem można szybko odtworzyć w krótkim czasie) aby przekształcić wejście takie jak poniżej (często spotykane w zadaniach algorytmicznych) na ukorzenione drzewo. Pierwsza linijka wejścia to ilość węzłów n, a w kolejnych n-1 linijkach opisy połączeń.


8
1 2
2 3
2 4
5 4
4 6
7 6
8 7


Każdy węzeł może mieć dowolną ilość synów. Jaki jest standardowy sposób podejścia do tego?

0

Boost Graph Library będzie OK, czy za ciężkie działo jak dla Ciebie?

1

To zależy, co potem na takim drzewie będziesz robić, zwykle wystarczy wskaźnik na węzeł, który jest korzeniem. Sam węzeł to struktura z kluczem i listą dzieci. Można tez wszystko trzymać w hashmapie, zależy jaki algorytm potem chcesz zastosować.

1

Boost Graph Library będzie OK

Będzie super cool:), ale może być tak, że nie można używać Boost'a, wtedy trza zaimplementować drzewko i dodać metodę czytającą z pliku/stdin.

EDYCJA: A nawet już wiadomo, że nie można:)

0

Załóżmy, że chcę przechodzić po drzewie od liści do korzenia. Co będzie najlepsze do tego celu?

0

Co znaczy od liści do korzenia, od każdego liścia do korzenia, tyle razy ile jest liści? Wygląda mi to na XY, napisz co naprawdę Chcesz zrobić.

0

Od każdego liścia do korzenia (tyle razy ile jest liści). To jest dokładnie to, co chcę zrobić.
Tak na marginesie, to jest cokolwiek złego w używaniu w takich sytuacjach listy sąsiedztwa jak do innych grafów? Co prawda teoretycznie nie ma wyróżnionego korzenia, ale można sobie zapisać w każdym elemencie na jakiej głębokości się znajduje i w ten sposób oznaczyć liście i korzeń.

0

Najkrótszą? Pewnie tak, nie wiem czy to najkrótsza, ale najprościej mieć pointer na matkę i iść za nim, aż węzeł będzie rootem.

0

Najkrótszą w sensie ścieżką? Przecież o ile się nie mylę cechą drzewa jest istnienie w nim tylko jednej ścieżki od korzenia do każdego wierzchołka. Czyli sobie zrobić jakąś strukturę z listą synów i ojcem i wpakować to w jakąś tablicę?

0

Przy gęstych grafach, zazwyczaj najlepszą implementacją jest macierz (więc std::array, jak się trzymamy tylko biblioteki standardowej). Przy drzewach (lub ogólnie, grafach rzadkich) już coś dynamicznego: robisz sobie strukturę z id węzła (typowo std::uint_fast_??_t), wektorem wskaźników (najlepiej std::shared_pointer lub std::unique_pointer, w zależności od potrzeb) na potomków (lub par [wskaźnik, waga], jeśli tego potrzebujesz) i zawartością, którą chcesz w nich trzymać.

Jak od razu wiesz, że będziesz potrzebował coś więcej, to dorzuć coś więcej: na przykład jak chcesz iść „pod górę”, od liści do korzenia, to trzymaj też i wskaźnik na rodzica (czy wektor wskaźników na rodziców, jeśli to potrzebne, itd.)

Wielkiej filozofii w tym nie ma, jedyne co jest ciężkie, to efektywne zarządzanie pamięcią, żeby nie mieć miliona alokacji małych obiektów. Ale najpierw opanuj „naiwną” metodę, zanim będziesz w memory poole i inne cuda. No chyba że o to właśnie pytałeś — ale to jest pytanie wymagające poznania właściwie całej specyfikacji, by móc coś sensownie doradzić.

0

Dzięki. Mam jeszcze pytanie, czy te smart pointery nie spowolnią mi programu? W zadaniach znaczenie mają milisekundy.

0

Przy drzewach (lub ogólnie, grafach rzadkich) już coś dynamicznego: robisz sobie strukturę z id węzła (typowo std::uint_fast_??_t), wektorem >wskaźników (najlepiej std::shared_pointer lub std::unique_pointer, w zależności od potrzeb)

A czemu nie std::vector dzieci?

Najkrótszą w sensie ścieżką? Przecież o ile się nie mylę cechą drzewa jest istnienie w nim tylko jednej ścieżki od korzenia do każdego wierzchołka. Czyli sobie zrobić jakąś strukturę z listą synów i ojcem i wpakować to w jakąś tablicę?

Tak, Masz rację; co do pytania, nie, Masz zaimplementować dynamiczną wskaźnikową strukturę danych, której node będzie miał wskaźniki na matkę i wektor dzieci, albo tak jak pisze @Althorion

0

W drzewie faktycznie tak lepiej, ale przy nie-drzewach problemem będą cykle.

0
licealista napisał(a):

Dzięki. Mam jeszcze pytanie, czy te smart pointery nie spowolnią mi programu? W zadaniach znaczenie mają milisekundy.

Nie wiem — sprawdź. Są tylko trzy metody na ocenę szybkości działania programów:

  1. Benchmark.
  2. Benchmark.
  3. Benchmark.
0

OK, temat wyczerpany. Dziękuję za pomoc.

1 użytkowników online, w tym zalogowanych: 0, gości: 1