Algorytm liniowego oznaczania czasu dla drzewa?

Mam drzewo bezkierunkowe, którego wierzchołki chcę opisać. Węzły liści powinny być oznaczone jako jeden. Następnie załóżmy, że liście zostały usunięte. W drzewie, które pozostaje, liście powinny być oznaczone jako dwa. Proces ten trwa w oczywisty sposób, dopóki wszystkie wierzchołki nie będą miały etykiety. Powodem tego jest to, że chcę przechowywać wierzchołki w kolejce i przechodzić przez nie „najpierw wychodzi”. Czy istnieje prosty sposób na wykonanie tego czasu $O(n+m)$ ?

Mogę rozwiązać problem, wykonując BFS na każdym kroku. Ale w najgorszym przypadku na każdym kroku przechodzę przez każdy wierzchołek, usuwam dokładnie dwa liście i umieszczam je w kolejce. Uważam, że zajmuje to kwadratowy czas.

Innym pomysłem było najpierw znaleźć wszystkie liście, a następnie wykonać BFS z każdego liścia. To nie daje mi pożądanego rozwiązania. Rozważmy na przykład rodzaj „wykresu korony”, jak na poniższym rysunku. Pokazane jest pożądane rozwiązanie, ale uruchomienie BFS z każdego liścia spowoduje użycie tylko dwóch etykiet.

wprowadź opis zdjęcia tutaj

Idealnie algorytm czasu liniowego byłby również łatwy do wyjaśnienia i wdrożenia.

algorithms trees

— Bob Whiz
źródło

Nieukorzenione Drzewa

Aby rozwiązać ten problem w możesz użyć kolejki priorytetowej : $O(E+V\log V)$

Umieść wszystkie wierzchołki w kolejce priorytetowej, a ich priorytetem będzie stopień.
Gdy kolejka nie jest pusta:
- Usuń wierzchołek o minimalnym priorytecie, który musi wynosić (lub na samym końcu). $v$ $1$ $0$
- $\sigma(v) = 1 + \max \sigma(u)$ $u$ $v$
- Odejmij od priorytetu unikalnego pozostałego sąsiada (jeśli istnieje). $1$ $u$

W rzeczywistości tak naprawdę nie potrzebujemy kolejki priorytetowej, a ten algorytm można zaimplementować za pomocą prostej kolejki w czasie : $O(E+V)$

Zainicjuj tablicę o długości ze stopniami wszystkich wierzchołków. $V$
Zainicjuj kolejną tablicę o długości „żywy”. $V$
Przejdź raz przez pierwszą tablicę i popchnij wszystkie wierzchołki stopnia do kolejki. $1$
Gdy kolejka nie jest pusta:
- Pop wierzchołek . $v$
- Niech , gdzie przechodzi przez wszystkich oryginalnych sąsiadów . $\sigma(v) = 1 + \max \sigma(u)$ $u$ $v$
- Oznacz jako „martwy”. $v$
- Jeśli ma jakiegoś „żywego” sąsiada , odejmij od stopnia . $v$ $u$ $1$ $u$
- Jeśli nowy stopień wynosi , popchnij do kolejki. $u$ $1$ $u$

Ukorzenione drzewa

Zamiast tego użyj DFS. Oto szkic algorytmu.

Biorąc pod uwagę węzeł , jeśli jest liściem, ustaw . $v$ $v$ $d(v) = 1$
Jeśli nie jest liściem, uruchom algorytm na wszystkich jego elementach potomnych, a następnie pozwól , gdzie $v$ $d(v) = 1 + \max d(u)$ $u$ przekracza zbiór wszystkich dzieci.

Ten algorytm uruchamiasz w katalogu głównym.

— Yuval Filmus
źródło

Czy to jest poprawne? Zastanów się nad drzewem 1-> 2-> 3-> 4-> 5, gdzie 1 jest korzeniem. 2 powinno otrzymać etykietę 1, ale dajesz 3? Czy przez dzieci masz na myśli sąsiadów? Z którego węzła uruchamiamy dfs?

— Knoothe

Moja implementacja jest „wyłączana przez jednego”, ale zgodnie z twoim opisem powinno otrzymać etykietę , ponieważ musisz usunąć , potem , a następnie , a dopiero wtedy staje się liściem.

2

$2$

4

$4$

5

$5$

4

$4$

3

$3$

2

$2$

— Yuval Filmus

Nie zadałem pytania :-). Zinterpretowałem to jako: drzewo bezkierunkowe. Oznacz wszystkie liście. Usuń ich. Powtórz na powstałym drzewie. W takim przypadku drzewo to tak naprawdę 1-2-3-4-5, krok 1, usuwasz 1 i 5, następnie 2 i 4, a następnie 3. Zobacz akapit o „wykresie korony”. Jest to jeden z klasycznych algorytmów służących do znajdowania środka drzewa.

— Knoothe

1 nie jest liściem. Jest bardzo daleki od bycia liściem, jest to korzeń. Zinterpretowałem to pytanie jako ukierunkowane na ukorzenione drzewa. Być może powinniśmy poczekać na odpowiedź PO.

— Yuval Filmus

@YuvalFilmus, aby wrzucić moje 2 centy, czy nie powinno to być

? Liście mają wartość

, jeśli je usuniesz, nowe liście powinny mieć wartość

, więc jest to rodzaj pomiaru liczby warstw, które musisz usunąć, zanim wierzchołek stanie się liściem. W przypadku min każdy wierzchołek przylegający do liścia ma wartość 2, ale nie może stać się liściem po usunięciu liści. W tym zdaniu było za dużo liści. Potrzebuję miotły.

1 + m a x {d (u)}

$1+max\{d(u)\}$

1

$1$

2

$2$

— Luke Mathieson

Prosta odpowiedź jest następująca:

$(u,v)$ $u$ $v$
Topologicznie posortuj wykres.
$v$ $v$

$O(n+m)$ $O(n+m)$

— DW
źródło