Linearer Zeitmarkierungsalgorithmus für einen Baum?

Ich habe einen ungerichteten Baum, dessen Eckpunkte ich beschriften möchte. Die Blattknoten sollten mit einem gekennzeichnet sein. Dann nehmen wir an, die Blätter wurden entfernt. In dem verbleibenden Baum sollten die Blätter mit zwei gekennzeichnet sein. Dieser Vorgang wird auf offensichtliche Weise fortgesetzt, bis alle Scheitelpunkte eine Beschriftung haben. Der Grund, warum ich das tue, ist, dass ich die Eckpunkte in einer Warteschlange speichern und sie "zuerst verlassen" möchte. Gibt es eine einfache Möglichkeit, diese $O(n+m)$ -Zeit durchzuführen?

Ich kann das Problem lösen, indem ich bei jedem Schritt ein BFS durchführe. Aber im schlimmsten Fall entferne ich bei jedem Schritt durch jeden Scheitelpunkt genau zwei Blätter und reihe sie ein. Ich glaube, das braucht quadratische Zeit.

Eine andere Idee war, zuerst alle Blätter zu finden und dann von jedem Blatt ein BFS durchzuführen. Das gibt mir nicht die gewünschte Lösung. Betrachten Sie beispielsweise eine Art "Kronendiagramm" wie in der folgenden Abbildung. Die gewünschte Lösung wird angezeigt. Wenn Sie jedoch ein BFS von jedem Blatt starten, werden nur zwei Etiketten verwendet.

Idealerweise wäre der lineare Zeitalgorithmus auch leicht zu erklären und zu implementieren.

Unbewurzelte Bäume

Sie können eine Prioritätswarteschlange verwenden, um dies in zu lösen :$O(E+V\log V)$

• Stellen Sie alle Eckpunkte in eine Prioritätswarteschlange, wobei ihre Priorität der Grad ist.
• Während die Warteschlange nicht leer ist:
  • Entfernen Sie einen Scheitelpunkt mit minimaler Priorität, der 1 (oder ganz am Ende 0 ) sein muss.$v$$1$$0$
  • Sei , wobei u über alle ursprünglichen Nachbarn von v geht .$\sigma(v) = 1 + \max \sigma(u)$$u$$v$
  • Subtrahieren Sie von der Priorität des eindeutigen verbleibenden Nachbarn von u (falls vorhanden).$1$$u$

Tatsächlich brauchen wir keine Prioritätswarteschlange, und dieser Algorithmus kann unter Verwendung einer einfachen Warteschlange in der Zeit implementiert werden :$O(E+V)$

• Initialisieren Sie ein Array der Länge mit den Graden aller Scheitelpunkte.$V$
• Initialisiere ein anderes Array der Länge mit "lebendig".$V$
• Gehen Sie einmal durch das erste Array und verschieben Sie alle Scheitelpunkte des Grades in eine Warteschlange.$1$
• Während die Warteschlange nicht leer ist:
  • Pop ein Scheitelpunkt .$v$
  • Sei , wobei u über alle ursprünglichen Nachbarn von v geht .$\sigma(v) = 1 + \max \sigma(u)$$u$$v$
  • Markiere als "tot".$v$
  • Wenn einen "lebendigen" Nachbarn u hat , subtrahiere 1 von dem Grad von u .$v$$u$$1$$u$
  • Wenn der neue Grad der ist 1 , Push u in die Warteschlange.$u$$1$$u$

Verwurzelte Bäume

Verwenden Sie stattdessen DFS. Hier ist eine Skizze des Algorithmus.

• Bei einem gegebenen Knoten , wenn v ein Blatt ist , Set D ( v ) = 1 .$v$$v$$d(v) = 1$
• Wenn kein Blatt ist, führen Sie den Algorithmus für alle seine Kinder aus und lassen Sie dann d ( v ) = 1 + max d ( u ) , wobei u die Menge aller Kinder überschreitet.$v$$d(v) = 1 + \max d(u)$$u$

Sie führen diesen Algorithmus im Stammverzeichnis aus.

Eine einfache Antwort lautet wie folgt:

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

• Topologisch sortieren Sie das Diagramm.

• $v$$v$

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