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.

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

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ć 1 (lub 0 na samym końcu).$v$$1$$0$
  • u $\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 .u $\sigma(v) = 1 + \max \sigma(u)$$u$$v$
  • Oznacz jako „martwy”.$v$
  • Jeśli ma jakiegoś „żywego” sąsiada , odejmij od stopnia .u 1 $v$$u$$1$$u$
  • Jeśli nowy stopień wynosi , popchnij do kolejki.1 $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 d ( v ) = $v$$v$$d(v) = 1$
• Jeśli nie jest liściem, uruchom algorytm na wszystkich jego elementach potomnych, a następnie pozwól , gdzied ( v ) = 1 + max d ( u ) $v$$d(v) = 1 + \max d(u)$$u$ przekracza zbiór wszystkich dzieci.

Ten algorytm uruchamiasz w katalogu głównym.

Prosta odpowiedź jest następująca:

• $(u,v)$$u$$v$

• Topologicznie posortuj wykres.

• $v$$v$

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