Reprezentacja ukorzenionego drzewa

Odpowiedz Nowy wątek
2020-03-26 16:16

Rejestracja: 8 miesięcy temu

Ostatnio: 1 miesiąc temu

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?

edytowany 1x, ostatnio: licealista, 2020-03-26 16:17

Pozostało 580 znaków

2020-03-26 19:00

Rejestracja: 3 lata temu

Ostatnio: 56 sekund temu

Przy drzewach (lub ogólnie, grafach rzadkich) już coś dynamicznego: robisz sobie strukturę z id węzła (typowo std::uintfast??_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


edytowany 3x, ostatnio: lion137, 2020-03-26 19:05

Pozostało 580 znaków

2020-03-26 19:05

Rejestracja: 4 lata temu

Ostatnio: 1 dzień temu

0

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

Pozostało 580 znaków

2020-03-26 19:07

Rejestracja: 4 lata temu

Ostatnio: 1 dzień temu

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.

Pozostało 580 znaków

2020-03-26 19:25

Rejestracja: 8 miesięcy temu

Ostatnio: 1 miesiąc temu

0

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

Pozostało 580 znaków

Odpowiedz

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